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