Fast constant-time gcd computation and modular inversion

[Marco Bodrato]

Il 2022-09-01 17:04 Torbjörn Granlund ha scritto:
> /* FIXME: Using mpz_invert is cheating. Instead, first compute m' =
>        m^-1 (mod 2^k) via Newton/Hensel. We can then get the inverse 
> via
> 
>        2^{-k} (mod m) = (2^k - m') * m + 1)/2^k. */
>     mpz_invert (t, t, m);
>     mpn_copyi (info->ip, mpz_limbs_read (t), mpz_size (t));
> 
> You might want to use mpn_binvert here.

We should start writing mpn_sec_binvert :-)
Or use the current mpn_sec_invert for the precomputation.

Ĝis,
m