MathStuff/modular.rb at master · jedediah/MathStuff · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
class Integer
    def residue(p)
        Residue.new(self, p)
    end
end

class Residue
    attr :r, :p

    def initialize(r, p)
        @r = r % p
        @p = p
    end

    def inspect
        "#{r.inspect}#{p.inspect.to_subscript}"
    end

    def inspect_latex
        "#{r.inspect_latex}_{#{p.inspect_latex}}"
    end

    def to_i
        r
    end

    def _coerce(x)
        if x.is_a?(Residue) && p == x.p
            if p == x.p
                x
            else
                raise TypeError, "Cannot coerce from modulo #{p} to modulo #{x.p}"
            end
        else
            self.class.new(x, p)
        end
    end

    def coerce(a)
        return _coerce(a), self
    end

    def hash
        [r, p].hash
    end

    def eql?(b)
        b.is_a?(Residue) && r == b.r && p == b.p
    end

    def zero?
        r.zero?
    end

    def one?
        r.one?
    end

    def congruent?(b)
        if b.is_a? Residue
            r == b.r && p == b.p
        else
            r == b % p
        end
    end

    def _rep(x)
        if x.is_a? Residue
            if p == x.p
                x.r
            else
                raise TypeError, "Cannot coerce from modulo #{p} to modulo #{x.p}"
            end
        else
            x % p
        end
    end

    def -@
        self.class.new(-r, p)
    end

    def +(b)
        self.class.new(r + _rep(b), p)
    end

    def -(b)
        self.class.new(r - _rep(b), p)
    end

    def reciprocal
        t = p.class.zero
        t0 = p.class.one
        a = p
        a0 = r
        until a0.zero?
            a, q, a0 = a0, *a.divmod(a0)
            t, t0 = t0, t - q*t0
        end
        a.one? or raise TypeError, "#{inspect} has no multiplicative inverse"
        self.class.new(t, p)
    end

    def *(b)
        self.class.new(r * _rep(b), p)
    end

    def /(b)
        self.class.new(r * _coerce(b).reciprocal.r, p)
    end

    def **(n)
        n.integer? or raise ArgumentError, "Non-integer powers not implemented"
        if n < 0
            reciprocal**(-n)
        else
            self.class.new(r**n, p)
        end
    end

    class << self
        def modulo(p)
            (0...p).map{|r| new(r, p) }
        end
    end
end