src/modinteger/cl_MI_pow2m1.h

   1 // m > 0, m = 2^m1 - 1 (m1 > 1)
   2
   3 namespace cln {
   4
   5 class cl_heap_modint_ring_pow2m1 : public cl_heap_modint_ring {
   6         SUBCLASS_cl_heap_modint_ring()
   7 public:
   8         // Constructor.
   9         cl_heap_modint_ring_pow2m1 (const cl_I& m, uintC m1); // m = 2^m1 - 1
  10         // Destructor.
  11         ~cl_heap_modint_ring_pow2m1 () {}
  12         // Additional information.
  13         uintC m1;
  14 };
  15
  16 static inline const cl_I pow2m1_reduce_modulo (cl_heap_modint_ring* _R, const cl_I& x)
  17 {
  18         var cl_heap_modint_ring_pow2m1* R = (cl_heap_modint_ring_pow2m1*)_R;
  19         // Method:
  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).
  24  {      Mutable(cl_I,x);
  25         var bool sign = minusp(x);
  26         if (sign) { x = lognot(x); }
  27         var const uintC m1 = R->m1;
  28         if (x >= R->modulus) {
  29                 x = plus1(x); // avoid staying at x = m
  30                 do {
  31                         var uintC xlen = integer_length(x);
  32                         var cl_I y = ldb(x,cl_byte(m1,0));
  33                         for (var uintC i = m1; i < xlen; i += m1)
  34                                 y = y + ldb(x,cl_byte(m1,i));
  35                         x = y;
  36                 } while (x > R->modulus);
  37                 x = minus1(x);
  38         }
  39         // Now 0 <= x < m.
  40         if (sign) { x = R->modulus - 1 - x; }
  41         return x;
  42 }}
  43
  44 static const _cl_MI pow2m1_canonhom (cl_heap_modint_ring* R, const cl_I& x)
  45 {
  46         return _cl_MI(R, pow2m1_reduce_modulo(R,x));
  47 }
  48
  49 static const _cl_MI pow2m1_mul (cl_heap_modint_ring* _R, const _cl_MI& x, const _cl_MI& y)
  50 {
  51         var cl_heap_modint_ring_pow2m1* R = (cl_heap_modint_ring_pow2m1*)_R;
  52         var const uintC 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);
  56 }
  57
  58 static const _cl_MI pow2m1_square (cl_heap_modint_ring* _R, const _cl_MI& x)
  59 {
  60         var cl_heap_modint_ring_pow2m1* R = (cl_heap_modint_ring_pow2m1*)_R;
  61         var const uintC 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);
  65 }
  66
  67 #define pow2m1_addops std_addops
  68 static cl_modint_mulops pow2m1_mulops = {
  69         std_one,
  70         pow2m1_canonhom,
  71         pow2m1_mul,
  72         pow2m1_square,
  73         std_expt_pos,
  74         std_recip,
  75         std_div,
  76         std_expt,
  77         pow2m1_reduce_modulo,
  78         std_retract
  79 };
  80
  81 static void cl_modint_ring_pow2m1_destructor (cl_heap* pointer)
  82 {
  83         (*(cl_heap_modint_ring_pow2m1*)pointer).~cl_heap_modint_ring_pow2m1();
  84 }
  85
  86 cl_class cl_class_modint_ring_pow2m1 = {
  87         cl_modint_ring_pow2m1_destructor,
  88         cl_class_flags_modint_ring
  89 };
  90
  91 // Constructor.
  92 inline cl_heap_modint_ring_pow2m1::cl_heap_modint_ring_pow2m1 (const cl_I& m, uintC _m1)
  93         : cl_heap_modint_ring (m, &std_setops, &pow2m1_addops, &pow2m1_mulops), m1 (_m1)
  94 {
  95         type = &cl_class_modint_ring_pow2m1;
  96 }
  97
  98 }  // namespace cln