Fast constant-time gcd computation and modular inversion

[Niels Möller]

Torbjörn Granlund <tg at gmplib.org> writes:

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

I think the new algorithm by djb and Bo-Yin Yang look very promising. I
think it could work somthing like this:

Extract least significant 96 bits of each number.

Compute (in O(1)) a matrix that eliminates those bits. Matrix elements are
64-bit signed (it's not entirely clear from the proof in the paper that
they can't overflow 64 bit signed, I've tried mailing the authors for
clarification).

Then multiply original numbers by that matrix, and shift left 96 bits.
Then we have a net reduction of 32 bits. Due to signednes, we must treat
everything as two's complement.

To avoid actual shifts, we can group two such iterations, eliminating
three 64-bit limbs at the low end, and growing by at most two limbs at
the high end.

The new clever trick to deal with issues like (3), is to extend
algorithm state with an auxillary shift count.

The resulting inverse will be off by a power of two, which needs to be
eliminated with some final processing (or maybe treated specially, in
case numbers are in redc form).

Regards,
/Niels
 
-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.