Fast constant-time gcd computation and modular inversion

[Niels Möller]

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

> nisse at lysator.liu.se (Niels Möller) writes:
>
>   Extract least significant 96 bits of each number.
>
> Is that 3 32-bit limbs or 1.5 64-bit limbs?

I was thinking about 64-bit archs.

Then 96 bits seems to be the maximum number of low-end bits that can be
eliminated, under the constraint that elements of the corresponding
transformation matrix should fit in 64-bit (signed) limbs.

And there's no harm in extracting two full limsb (128 bits), it's just
that the transformation matrix doesn't depend in any way on those extra
bits.

For 32-bit transform matrix, one could do less (roughly half, not sure
of it's precicely 48 bits).

Regards,
/Niels

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