Open fredrik-johansson opened 5 months ago
What algorithm do you have in mind for this?
Algorithm 9.2.13 in Crandall & Pomerance for example.
Note that both n and 1/n are sparse; one can essentially just take the existing preinvn reduction and replace the dense mpn multiplications by sparse multiplications.
The general algorithm (pseudo-code) looks like
while (B(x) > q)
{
y = floor(x / 2^q);
x = x mod 2^q;
x = x - c * y;
}
if (x == 0)
return x;
s = sgn(x);
x = abs(x);
if (x >= N)
x = x - N;
if (s < 0)
x = N - x;
return x;
We should have special-purpose code for division and modular reduction by $n = 2^e + c$ where
e >= 2 * FLINT_BITS
andc
fits in aslong
, say.