New mulmod_bknp1

[David Harvey]

On Tue, 2022-02-22 at 23:23 +0100, Marco Bodrato wrote:
> Ciao David,
> 
> Il Mar, 22 Febbraio 2022 10:55 pm, David Harvey ha scritto:
> > On Tue, 2022-02-22 at 22:39 +0100, Marco Bodrato wrote:
> > > > E.g, in this case we could try a top-level B^66 - 1 product, split in
> > > > B^33+1 and B^33-1; then the former suits your new algorithm well, but
> > > > the former can't be recursively split (at least not on a B boundary).
> 
> > > I fully agree.
> 
> > What about
> > 
> > B^33 - 1 = (B^11 - 1)(B^22 + B^11 + 1)?
> 
> Actually, B is a number.
> 
> And if B is a power of 4 (there is an even number of bits in a limb, as
> usually happens, e.g. 32, or 64) then (B^n-1) and (B^2n+B^n+1) are not
> coprime, because both are divisible by 3. And we can not use CRT.

Yes good point.

But (N-1) and (N^2+N+1)/3 are relatively prime, where N = B^n, because

(N^2+N+1)/3 - (N-1) (N+2)/3 = 1.

So at least you can use CRT to get the answer mod (N^3-1)/3. Unfortunately
this is still not good enough, because N^3-1 is divisible by 9.

david