src/modinteger/cl_MI_rshift.cc

   1 // operator>> on cl_MI.
   2
   3 // General includes.
   4 #include "cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cln/modinteger.h"
   8
   9
  10 // Implementation.
  11
  12 #include "cln/integer.h"
  13 #include "cl_N.h"
  14 #include "cl_MI.h"
  15
  16 namespace cln {
  17
  18 const cl_MI operator>> (const cl_MI& x, sintL y) // assume 0 <= y < 2^31
  19 {
  20         if (y == 0)
  21                 return x;
  22         var const cl_modint_ring& R = x.ring();
  23         if (!oddp(R->modulus)) {
  24                 if (R->modulus == 2)
  25                         cl_error_division_by_0();
  26                 else
  27                         return (cl_MI_x)cl_notify_composite(R,2);
  28         }
  29         if (y == 1) // frequent case
  30                 return cl_MI(R, (evenp(x.rep) ? x.rep : x.rep + R->modulus) >> 1);
  31         // Method:
  32         // Algorithm 1: add a multiple of m to x.rep so that it becomes
  33         //              divisible by 2^y (2-adic division), then shift right.
  34         //              asymptotical cost: O(y * log m).
  35         // Algorithm 2: x * expt(2 mod m,-y) using modular integer operations.
  36         //              asymptotical cost: O(log y * (log m)^2).
  37         // Use algorithm 1 for small y, algorithm 2 for large y.
  38 #if 0
  39         if (y <= 2*R->bits)
  40                 cl_abort(); // not yet implemented
  41         else
  42 #endif
  43                 return R->div(x, expt_pos(R->canonhom(2), (cl_I)(long)y));
  44 }
  45
  46 }  // namespace cln