Fast modular reduction for Z/nZ with sparse n

[fredrik-johansson]

We should have special-purpose code for division and modular reduction by $n = 2^e + c$ where e >= 2 * FLINT_BITS and c fits in a slong, say.

[albinahlback]

What algorithm do you have in mind for this?

[fredrik-johansson]

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.

[albinahlback]

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;