Fast constant-time gcd computation and modular inversion

[Torbjörn Granlund]

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

    count = (49 * bits + 57) / 17;

Odd.

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

Cool!

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.


-- 
Torbjörn
Please encrypt, key id 0xC8601622