sec_karatsuba

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> Unfortunately, I had not the time to try with the -1 option, but I believe
> +1 is faster. The couple of negation (plus one more for the result) are a
> linear cost in the number of limbs of the operand.

If you or anyone else wants to experiment with this, I think it would be
good to start with sec_toom2_sqr. Then with -1, there's no conditional
negation for the result. So -1 has a better chance, and if it doesn't
win for squaring, it seems very unlikely it can win for multiplication.

> The extra limb is a linear cost only if the product cost is quadratic, and
> it's under-linear above the Karatsuba range...

I'd expect that the common case will be that it recurses to basecase
only. The largest secret numbers in important cryptographic applications
I'm aware of is about 2048 bits (32 limbs on a 64-bit machine), the
secret factors for 4096-bit RSA.

Regards,
/Niels

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