Side channel silent karatsuba / mpn_addmul_2 karatsuba

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> nisse at lysator.liu.se (Niels Möller) writes:

>   What's most efficient is not at all clear to me: negation costs O(n),
>   but so does handling of the extra top bits one get with evaluation in
>   +1.
>
> My hope is to handle those extra bits for free as one adds parts
> together.  (I am sure Marco gave all this a thought, looking at his
> solutions would be enlightening.)

For simplicity, assume both inputs are of size 2n limbs. With evaluation
in -1, we get we first compute |a1 - a0| and |b1 - b0| (and keep track
of signs separately). Both fit in n limbs, and it will cost n carry
propagations each for the conditional negations.

Then we compute the nxn product. The result has to be conditionally
negated, and sign-extended to size 3n when added into the final product.
The cost of that would be at least 2n carry propagations (assuming sign
extension can be done on the fly during some other carry propagation
pass), making the total cost for sign handling 4n carry propagations +
constant.

With evaluation at +1, (a1+a0) and (b1+b0) are each n limbs + a bit, and
the product is 2n limbs + 2 bits. If we handle the extra bits
separately, rather than doing it as an (n+1)x(n+1) multiply, I think that
would be two conditional n-limb additions, at weight B^2 in the final
product, and a single bit (the and of the two extra bits) at weight B^3.
I see that the last bit has some potential for folding with some other
carry propagation pass over the highest n limbs, but I don't see how to
do it cheaper than 2n carry propagations.

So +1 sounds better than -1. But it were still surprisingly many
operations on the n=1 case.

>   I did a sketch for x86 a while ago, but didn't complete it. See
>   https://gmplib.org/list-archives/gmp-devel/2017-June/004651.html. This
>   appears to use evaluation in -1.
>
> Did you time and/or test it?

As far as I remember, I ran tests, and they failed...

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.