1 // operator>> on cl_MI.
7 #include "cl_modinteger.h"
12 #include "cl_integer.h"
16 const cl_MI operator>> (const cl_MI& x, sintL y) // assume 0 <= y < 2^31
20 var const cl_modint_ring& R = x.ring();
21 if (!oddp(R->modulus)) {
23 cl_error_division_by_0();
25 return (cl_MI_x)cl_notify_composite(R,2);
27 if (y == 1) // frequent case
28 return cl_MI(R, (evenp(x.rep) ? x.rep : x.rep + R->modulus) >> 1);
30 // Algorithm 1: add a multiple of m to x.rep so that it becomes
31 // divisible by 2^y (2-adic division), then shift right.
32 // asymptotical cost: O(y * log m).
33 // Algorithm 2: x * expt(2 mod m,-y) using modular integer operations.
34 // asymptotical cost: O(log y * (log m)^2).
35 // Use algorithm 1 for small y, algorithm 2 for large y.
38 cl_abort(); // not yet implemented
41 return R->div(x, expt_pos(R->canonhom(2), (cl_I)(long)y));