Fast constant-time gcd computation and modular inversion
tg at gmplib.org
Wed Aug 24 22:26:51 CEST 2022
nisse at lysator.liu.se (Niels Möller) writes:
count = (49 * bits + 57) / 17;
(For production code, one will need to cap the intermediates there,
at least for 32-bit machines. Perhaps something like this:
count = (51 * bits - 2 * bits + 57) / 17 =
= 3 * bits - (2 * bits - 57) / 17
About a factor 3 slower than plain mpz_gcd on my machine. It will be
interesting to see if slowdown for modular inversion is about the same.
I think your measurements are a bit optimistic, though. My measruments
from slightly modified timing code suggest 4.5x slowdown, and more for
really small operands.
This will still completely outclass the current sec code.
Please encrypt, key id 0xC8601622
More information about the gmp-devel