Fast constant-time gcd computation and modular inversion

Torbjörn Granlund tg at
Thu Sep 1 17:04:07 CEST 2022

    /* 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.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list