1 // m > 0, m = 2^m1 + 1 (m1 > 1)
3 class cl_heap_modint_ring_pow2p1 : public cl_heap_modint_ring {
4 SUBCLASS_cl_heap_modint_ring()
7 cl_heap_modint_ring_pow2p1 (const cl_I& m, uintL m1); // m = 2^m1 + 1
9 ~cl_heap_modint_ring_pow2p1 () {}
10 // Additional information.
15 #if !(defined(__GNUC__) && (__GNUC__ == 2) && (__GNUC_MINOR__ <= 90)) // workaround g++-2.7.2 and egcs-1.0.2-prerelease bug
18 const cl_I pow2p1_reduce_modulo (cl_heap_modint_ring* _R, const cl_I& x)
20 var cl_heap_modint_ring_pow2p1* R = (cl_heap_modint_ring_pow2p1*)_R;
22 // If x>=0, split x into pieces of m1 bits and sum them up.
23 // x = x0 + 2^m1*x1 + 2^(2*m1)*x2 + ... ==>
24 // mod(x,m) = mod(x0-x1+x2-+...,m).
25 // If x<0, apply this to -1-x, and use mod(x,m) = m-1-mod(-1-x,m).
27 var bool sign = minusp(x);
28 if (sign) { x = lognot(x); }
29 var const uintL m1 = R->m1;
30 while (x >= R->modulus) {
31 var uintL xlen = integer_length(x);
32 var cl_I y = ldb(x,cl_byte(m1,0));
33 for (var uintL i = m1; ; ) {
34 y = y - ldb(x,cl_byte(m1,i));
38 y = y + ldb(x,cl_byte(m1,i));
44 { sign = !sign; x = lognot(y); }
49 if (sign) { x = R->modulus - 1 - x; }
53 static const _cl_MI pow2p1_canonhom (cl_heap_modint_ring* R, const cl_I& x)
55 return _cl_MI(R, pow2p1_reduce_modulo(R,x));
58 static const _cl_MI pow2p1_mul (cl_heap_modint_ring* _R, const _cl_MI& x, const _cl_MI& y)
60 var cl_heap_modint_ring_pow2p1* R = (cl_heap_modint_ring_pow2p1*)_R;
61 var const uintL m1 = R->m1;
62 var cl_I zr = x.rep * y.rep;
63 // Now 0 <= zr <= 2^(2*m1).
64 zr = ldb(zr,cl_byte(1,2*m1)) - ldb(zr,cl_byte(m1,m1)) + ldb(zr,cl_byte(m1,0));
65 // Now -(2^m1-1) <= zr <= 2^m1.
66 return _cl_MI(R, minusp(zr) ? zr + R->modulus : zr);
69 static const _cl_MI pow2p1_square (cl_heap_modint_ring* _R, const _cl_MI& x)
71 var cl_heap_modint_ring_pow2p1* R = (cl_heap_modint_ring_pow2p1*)_R;
72 var const uintL m1 = R->m1;
73 var cl_I zr = square(x.rep);
74 // Now 0 <= zr <= 2^(2*m1).
75 zr = ldb(zr,cl_byte(1,2*m1)) - ldb(zr,cl_byte(m1,m1)) + ldb(zr,cl_byte(m1,0));
76 // Now -(2^m1-1) <= zr <= 2^m1.
77 return _cl_MI(R, minusp(zr) ? zr + R->modulus : zr);
80 #define pow2p1_addops std_addops
81 static cl_modint_mulops pow2p1_mulops = {
95 inline cl_heap_modint_ring_pow2p1::cl_heap_modint_ring_pow2p1 (const cl_I& m, uintL _m1)
96 : cl_heap_modint_ring (m, &std_setops, &pow2p1_addops, &pow2p1_mulops), m1 (_m1) {}