Fast constant-time gcd computation and modular inversion

Torbjörn Granlund tg at
Sat Jun 4 01:02:26 CEST 2022

Any algorithm with these properties would be a huge improvement compared
to what we have today:

0. No side-channel leakage of anything but bit counts of input operands.
   (I suppose there are usages where the mod argument is not sensitive,
   such as for the elliptic curve usages).  This is already true for the
   present, slow code.

1. Computation of a 2 x 2 matrix in O(1) time.  Not necessarily fast.

2. Guaranteed reduction of intermediate operand bit count by a full limb

3. If the reduction in (2) happens to be greater than one limb, the
   subsequent iteration of (1) must still work.  I.e., it must allow the
   bits it depends on to be zero and should not need to locate, say, the
   least significant 1 bit of the full operands.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list