New mulmod_bknp1

[David Harvey]

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). If
> 
> I fully agree.

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.

david