Side channel silent karatsuba / mpn_addmul_2 karatsuba

Marco Bodrato bodrato at
Sat Dec 15 06:40:43 UTC 2018


Il Gio, 13 Dicembre 2018 8:05 pm, Marco Bodrato ha scritto:
> Not much. My goal was to write a surely correct and hopefully not too slow
> sec_mul. I simply handled the extra-bits with an (n+1)x(n+1) -> 2n+1
> multiply...

Are branches based on the _initial_ bit size allowed? Do we think that the
multiplication will be used also for large enough numbers requiring more
recursions of Karatsuba?

If that's the case, we may keep track of the "possibly non zero bits" in
the highest limb, and actually add a limb in the multiplication only if

This idea is effective or not, depending on the odd-even sizes for the
recursion levels... maybe it's not a good idea.


More information about the gmp-devel mailing list