New mulmod_bknp1

[Marco Bodrato]

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.

> 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.

Maybe. One should write the code and try.

Ĝis,
m