1 #ifndef MOD_STDOP_HPP
2 #define MOD_STDOP_HPP
3 
4 /* Functions for residues. Slow and clean
5   This class extends the Residue type of an existing Modulus type by adding
6   standard C++ operators for the modular arithmetic. For this to work, each
7   residue needs a reference to the modulus w.r.t. which it was declared, as
8   there is no other way of passing the modulus to the arithmetic operators.
9  */
10 template <typename T, typename = typename T::IsResidueType>
11 class ResidueStdOp : public T {
12   typedef T Residue;
13   typedef typename T::Modulus Modulus;
14   typedef typename T::Integer Integer;
15 private:
16   const Modulus &m;
assertValid(const ResidueStdOp & other MAYBE_UNUSED) const17   void assertValid(const ResidueStdOp &other MAYBE_UNUSED) const {ASSERT_EXPENSIVE(&m = &other.m);}
18 public:
ResidueStdOp(const Modulus & m)19   ResidueStdOp(const Modulus &m) : T(m), m(m) {}
ResidueStdOp(const Modulus & m,const Residue & s)20   ResidueStdOp(const Modulus &m, const Residue &s) : T(m), m(m) {m.set(*this, s);}
ResidueStdOp(const Modulus & m,const Integer & s)21   ResidueStdOp(const Modulus &m, const Integer &s) : T(m), m(m) {m.set(*this, s);}
ResidueStdOp(const Modulus & m,const uint64_t & s)22   ResidueStdOp(const Modulus &m, const uint64_t &s) : T(m), m(m) {m.set(*this, s);}
ResidueStdOp(const ResidueStdOp & s)23   ResidueStdOp(const ResidueStdOp &s) : Residue(s.m), m(s.m) {*this = s;}
ResidueStdOp(ResidueStdOp && s)24   ResidueStdOp(ResidueStdOp &&s) : Residue(s.m), m(s.m) {*this = s;}
25 
operator =(const ResidueStdOp & s)26   ResidueStdOp &operator=(const ResidueStdOp &s) {assertValid(s); m.set(*this, s); return *this;}
operator =(const uint64_t s)27   ResidueStdOp &operator=(const uint64_t s) {m.set(*this, s); return *this;}
operator =(const Integer & s)28   ResidueStdOp &operator=(const Integer &s) {m.set(*this, s); return *this;}
29 
operator ==(const ResidueStdOp & s) const30   bool operator==(const ResidueStdOp &s) const {assertValid(s); return m.equal(*this, s);}
operator !=(const ResidueStdOp & s) const31   bool operator!=(const ResidueStdOp &s) const {assertValid(s); return !m.equal(*this, s);}
is0() const32   bool is0() const {return m.is0(*this);}
is1() const33   bool is1() const {return m.is1(*this);}
34 
operator Integer()35   operator Integer() {Integer r; m.get(r, *this); return r;}
36 
operator -() const37   ResidueStdOp operator-() const {ResidueStdOp r = *this; m.neg(r, r); return r;}
38   /* Prefix ++ and -- */
operator ++()39   ResidueStdOp &operator++() {m.add1(*this, *this); return *this;}
operator --()40   ResidueStdOp &operator--() {m.sub1(*this, *this); return *this;}
41   /* Postfix ++ and -- */
operator ++(int)42   ResidueStdOp operator++(int) {ResidueStdOp r = *this; m.add1(*this, *this); return r;}
operator --(int)43   ResidueStdOp operator--(int) {ResidueStdOp r = *this; m.sub1(*this, *this); return r;}
44 
operator +(const ResidueStdOp & s) const45   ResidueStdOp operator+(const ResidueStdOp &s) const {assertValid(s); ResidueStdOp r(m); m.add(r, *this, s); return r;}
operator +(const uint64_t s) const46   ResidueStdOp operator+(const uint64_t s) const {ResidueStdOp r(m, s); m.add(r, *this, r); return r;}
operator +(const Integer & s) const47   ResidueStdOp operator+(const Integer &s) const {ResidueStdOp r(m, s); m.add(r, *this, r); return r;}
operator +=(const ResidueStdOp & s)48   ResidueStdOp &operator+=(const ResidueStdOp &s) {assertValid(s); m.add(*this, *this, s); return *this;}
operator +=(const uint64_t s)49   ResidueStdOp &operator+=(const uint64_t s) {ResidueStdOp t(m, s); m.add(*this, *this, t); return *this;}
operator +=(const Integer & s)50   ResidueStdOp &operator+=(const Integer &s) {ResidueStdOp t(m, s); m.add(*this, *this, t); return *this;}
operator +(const uint64_t s,const ResidueStdOp & t)51   friend ResidueStdOp operator+(const uint64_t s, const ResidueStdOp &t) {return t + s;}
operator +(const Integer & s,const ResidueStdOp & t)52   friend ResidueStdOp operator+(const Integer &s, const ResidueStdOp &t) {return t + s;}
operator +=(Integer & s,const ResidueStdOp & t)53   friend Integer &operator+=(Integer &s, const ResidueStdOp &t) {ResidueStdOp r(t.m, s); t.m.add(r, r, t); s = (Integer) r; return s;}
54 
operator -(const ResidueStdOp & s) const55   ResidueStdOp operator-(const ResidueStdOp &s) const {assertValid(s); ResidueStdOp r(m); m.sub(r, *this, s); return r;}
operator -(const uint64_t s) const56   ResidueStdOp operator-(const uint64_t s) const {ResidueStdOp r(m, s); m.sub(r, *this, r); return r;}
operator -(const Integer & s) const57   ResidueStdOp operator-(const Integer &s) const {ResidueStdOp r(m, s); m.sub(r, *this, r); return r;}
operator -=(const ResidueStdOp & s)58   ResidueStdOp &operator-=(const ResidueStdOp &s) {assertValid(s); m.sub(*this, *this, s); return *this;}
operator -=(const uint64_t s)59   ResidueStdOp &operator-=(const uint64_t s) {ResidueStdOp t(m, s); m.sub(*this, *this, t); return *this;}
operator -=(const Integer & s)60   ResidueStdOp &operator-=(const Integer &s) {ResidueStdOp t(m, s); m.sub(*this, *this, t); return *this;}
operator -(const uint64_t s,const ResidueStdOp & t)61   friend ResidueStdOp operator-(const uint64_t s, const ResidueStdOp &t) {return ResidueStdOp(t.m, s) - t;}
operator -(const Integer & s,const ResidueStdOp & t)62   friend ResidueStdOp operator-(const Integer &s, const ResidueStdOp &t) {return ResidueStdOp(t.m, s) - t;}
operator -=(Integer & s,const ResidueStdOp & t)63   friend Integer &operator-=(Integer &s, const ResidueStdOp &t) {return s = (Integer) (ResidueStdOp(t.m, s) - t);}
64 
operator *(const ResidueStdOp & s) const65   ResidueStdOp operator*(const ResidueStdOp &s) const {
66       assertValid(s);
67       ResidueStdOp r(m);
68       if (CONSTANT_P(this == &s) && this == &s) {
69           m.sqr(r, *this);
70       } else {
71         m.mul(r, *this, s);
72       }
73     return r;
74   }
operator *(const uint64_t s) const75   ResidueStdOp operator*(const uint64_t s) const {ResidueStdOp r(m, s); m.mul(r, *this, r); return r;}
operator *(const Integer & s) const76   ResidueStdOp operator*(const Integer &s) const {ResidueStdOp r(m, s); m.mul(r, *this, r); return r;}
operator *=(const ResidueStdOp & s)77   ResidueStdOp &operator*=(const ResidueStdOp &s) {assertValid(s); m.mul(*this, *this, s); return *this;}
operator *=(const uint64_t s)78   ResidueStdOp &operator*=(const uint64_t s) {ResidueStdOp t(m, s); m.mul(*this, *this, t); return *this;}
operator *=(const Integer & s)79   ResidueStdOp &operator*=(const Integer &s) {ResidueStdOp t(m, s); m.mul(*this, *this, t); return *this;}
operator *(const uint64_t s,const ResidueStdOp & t)80   friend ResidueStdOp operator*(const uint64_t s, const ResidueStdOp &t) {ResidueStdOp r(t.m, s); t.m.mul(r, r, t); return r;}
operator *(const Integer & s,const ResidueStdOp & t)81   friend ResidueStdOp operator*(const Integer &s, const ResidueStdOp &t) {ResidueStdOp r(t.m, s); t.m.mul(r, r, t); return r;}
operator *=(Integer & s,const ResidueStdOp & t)82   friend Integer &operator*=(Integer &s, const ResidueStdOp &t) {ResidueStdOp r(t.m, s); t.m.mul(r, r, t); s = r; return s;}
83 
operator /(const ResidueStdOp & s) const84   ResidueStdOp operator/(const ResidueStdOp &s) const {assertValid(s); ResidueStdOp r(m); m.inv(r, s); m.mul(r, *this, r); return r;}
operator /=(const ResidueStdOp & s)85   ResidueStdOp &operator/=(const ResidueStdOp &s) {assertValid(s); ResidueStdOp i(m); m.inv(i, s); m.mul(*this, *this, i); return *this;}
operator /(const uint64_t s) const86   ResidueStdOp operator/(const uint64_t s) const {
87       ResidueStdOp r(m);
88       if (CONSTANT_P(s) && s == 2) {
89           m.div2(r, *this);
90       } else if (CONSTANT_P(s) && s == 3) {
91           m.div3(r, *this);
92       } else if (CONSTANT_P(s) && s == 5) {
93           m.div5(r, *this);
94       } else if (CONSTANT_P(s) && s == 7) {
95           m.div7(r, *this);
96       } else if (CONSTANT_P(s) && s == 11) {
97           m.div11(r, *this);
98       } else if (CONSTANT_P(s) && s == 13) {
99           m.div13(r, *this);
100       } else {
101           ResidueStdOp r(m);
102           m.set(r, s);
103           m.inv(r, r);
104           m.mul(r, *this, r);
105       }
106       return r;
107   }
operator /=(const uint64_t s)108   ResidueStdOp &operator/=(const uint64_t s) {return *this /= ResidueStdOp(m, s);}
operator /(const uint64_t s,const ResidueStdOp & t)109   friend ResidueStdOp operator/(const uint64_t s, const ResidueStdOp &t) {
110       if (CONSTANT_P(s) && s == 1) { /* For 1/t, don't multiply by 1 */
111           ResidueStdOp r(t.m);
112           t.m.inv(r, t);
113           return r;
114       } else {
115           return ResidueStdOp(t.m, s) / t;
116       }
117   }
operator /(const Integer & s) const118   ResidueStdOp operator/(const Integer &s) const {return *this / ResidueStdOp(m, s);}
operator /=(const Integer & s)119   ResidueStdOp &operator/=(const Integer &s) {return *this /= ResidueStdOp(m, s);}
operator /(const Integer & s,const ResidueStdOp & t)120   friend ResidueStdOp operator/(const Integer &s, const ResidueStdOp &t) {return ResidueStdOp(t.m, s) / t;}
operator /=(Integer & s,const ResidueStdOp & t)121   friend Integer &operator/=(Integer &s, const ResidueStdOp &t) {return s = (Integer) (ResidueStdOp(t.m, s) / t);}
122 
pow(const uint64_t e)123   ResidueStdOp pow(const uint64_t e) {ResidueStdOp r(m); m.pow_u64(r, *this, e); return r;}
pow(const Integer & e)124   ResidueStdOp pow(const Integer &e) {ResidueStdOp r(m); m.pow(r, *this, e); return r;}
pow(const uint64_t * e,const size_t l)125   ResidueStdOp pow(const uint64_t *e, const size_t l) {ResidueStdOp r(m); m.pow(r, *this, e, l); return r;}
chebyshevV(const uint64_t e)126   ResidueStdOp chebyshevV(const uint64_t e) {ResidueStdOp r(m); m.V(r, *this, e); return r;}
chebyshevV(const Integer & e)127   ResidueStdOp chebyshevV(const Integer &e) {ResidueStdOp r(m); m.V(r, *this, e); return r;}
chebyshevV(const uint64_t * e,const size_t l)128   ResidueStdOp chebyshevV(const uint64_t *e, const size_t l) {ResidueStdOp r(m); m.V(r, *this, e, l); return r;}
129 
130   /* Should we call it index or gcd? I can't decide */
index() const131   Integer index() const {Integer g; m.gcd(g, *this); return g;}
gcd() const132   Integer gcd() const {Integer g; m.gcd(g, *this); return g;}
jacobi() const133   int jacobi() const {return m.jacobi(*this);}
134 };
135 
136 #endif /* MOD_STDOP_HPP */
137