New mulmod_bknp1

[Marco Bodrato]

Ciao Niels and David,

Il 2022-02-23 09:14 nisse at lysator.liu.se ha scritto:
> N^3-1 = (N^2+N+1)/3 * 3^{k+1} * (N-1)/3^k

> 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

Yes, there are many details that one needs to take into account to 
implement something like that...

Il 2022-02-22 22:55 David Harvey ha scritto:
> What about
> 
> B^33 - 1 = (B^11 - 1)(B^22 + B^11 + 1)?
> 
> Also, I suspect that some of these tricks are worth doing even if the
> factorisations cross the B boundaries. The extra shifting overhead is 
> only
> linear.

I do not, but if someone has the time to try to implement some 
extensions on the _bnm1 side (B^n-1), I'd suggest to try at first the 
"cross the B boundaries" strategy.

I mean, if we have H s.t. H^2 = B, I'd try to split
B^33 - 1 = (H^33 - 1)(H^33 + 1)


One more observation.

Currently, the library may require a product eg. mod B^72-1. The current 
_bnm1 code splits the computation into
B^72-1 = (B^36+1)(B^18+1)(B^9+1)(B^9-1)

I'd expect that more than half the time is spent computing mod B^36+1.
Less than 1/4 the time is spent mod B^18+1.
Less than 1/8 the time is spent for each of the two last factors B^9+1, 
and B^9-1.


... then maybe I was wrong when I wrote that we should not trade a 
factor 3 with a factor 2...

Ĝis,
m