New mulmod_bknp1

[Niels Möller]

David Harvey <d.harvey at unsw.edu.au> writes:

> While N^2+N+1 is always divisible by 3, it is never divisible by 9. So maybe
> you could use the factorisation
>
> N^3 - 1 = (N^2+N+1)/3 * (3N-3).
>
> I think (?) the two factors on the right are always coprime.

I wonder if it could work to take out all the factors of 3, i.e.,

N^3-1 = (N^2+N+1)/3 * 3^{k+1} * (N-1)/3^k

Will that give us three co-prime factors (with proper value of k
depending on N)?

Could be implemented as one multiply each mod 2^N+N+1 and (N-1),
followed by reduction mod (N^2+N+1)/3 and (N-1)/3^k at the end; these
reductions correspond to small quotients and should be cheap (I
suspect we have to require canonical reduction for CRT reconstruction to
work out nicely, but I'm note really sure).

And then compute the final small product mod 3^{k+1}, which would also
go into the CRT. One might exclude N such that 3^{k+1} exceeds one limb.
Mod by constant single limb is pretty fast in GMP.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.