1 // m > 0, m = 2^m1 - 1 (m1 > 1)
5 class cl_heap_modint_ring_pow2m1 : public cl_heap_modint_ring {
6 SUBCLASS_cl_heap_modint_ring()
9 cl_heap_modint_ring_pow2m1 (const cl_I& m, uintL m1); // m = 2^m1 - 1
10 // Virtual destructor.
11 ~cl_heap_modint_ring_pow2m1 () {}
12 // Additional information.
16 static inline const cl_I pow2m1_reduce_modulo (cl_heap_modint_ring* _R, const cl_I& x)
18 var cl_heap_modint_ring_pow2m1* R = (cl_heap_modint_ring_pow2m1*)_R;
20 // If x>=0, split x into pieces of m1 bits and sum them up.
21 // x = x0 + 2^m1*x1 + 2^(2*m1)*x2 + ... ==>
22 // mod(x,m) = mod(x0+x1+x2+...,m).
23 // If x<0, apply this to -1-x, and use mod(x,m) = m-1-mod(-1-x,m).
25 var cl_boolean sign = minusp(x);
26 if (sign) { x = lognot(x); }
27 var const uintL m1 = R->m1;
28 if (x >= R->modulus) {
29 x = plus1(x); // avoid staying at x = m
31 var uintL xlen = integer_length(x);
32 var cl_I y = ldb(x,cl_byte(m1,0));
33 for (var uintL i = m1; i < xlen; i += m1)
34 y = y + ldb(x,cl_byte(m1,i));
36 } while (x > R->modulus);
40 if (sign) { x = R->modulus - 1 - x; }
44 static const _cl_MI pow2m1_canonhom (cl_heap_modint_ring* R, const cl_I& x)
46 return _cl_MI(R, pow2m1_reduce_modulo(R,x));
49 static const _cl_MI pow2m1_mul (cl_heap_modint_ring* _R, const _cl_MI& x, const _cl_MI& y)
51 var cl_heap_modint_ring_pow2m1* R = (cl_heap_modint_ring_pow2m1*)_R;
52 var const uintL m1 = R->m1;
53 var cl_I zr = x.rep * y.rep;
54 zr = ldb(zr,cl_byte(m1,m1)) + ldb(zr,cl_byte(m1,0));
55 return _cl_MI(R, zr >= R->modulus ? zr - R->modulus : zr);
58 static const _cl_MI pow2m1_square (cl_heap_modint_ring* _R, const _cl_MI& x)
60 var cl_heap_modint_ring_pow2m1* R = (cl_heap_modint_ring_pow2m1*)_R;
61 var const uintL m1 = R->m1;
62 var cl_I zr = square(x.rep);
63 zr = ldb(zr,cl_byte(m1,m1)) + ldb(zr,cl_byte(m1,0));
64 return _cl_MI(R, zr >= R->modulus ? zr - R->modulus : zr);
67 #define pow2m1_addops std_addops
68 static cl_modint_mulops pow2m1_mulops = {
82 inline cl_heap_modint_ring_pow2m1::cl_heap_modint_ring_pow2m1 (const cl_I& m, uintL _m1)
83 : cl_heap_modint_ring (m, &std_setops, &pow2m1_addops, &pow2m1_mulops), m1 (_m1) {}