Constant-time GCD

[fjarri]

There is already an item for that in #1, but I would like to make a separate issue to add more info, and to make it more noticeable. It is likely I will have a go at it the next time I have free time available, in which case I will assign myself to the issue; before that it's free for the taking.

So the state of the art seems to be:

• Bernstein & Yang "Fast constant-time gcd computation and modular inversion" (https://gcd.cr.yp.to/safegcd-20190413.pdf)
• Improved bounds for the paper above: https://github.com/sipa/safegcd-bounds
• Pornin "Optimized Binary GCD for Modular Inversion" (https://eprint.iacr.org/2020/972.pdf)
• Implementation tricks used in libsecp256k1: https://github.com/bitcoin-core/secp256k1/blob/master/doc/safegcd_implementation.md

Additionally, with the GCD available, it seems straightforward to implement Jacobi symbol and modular inversion based on it. The latter may supersede the existing inv_odd_mod_bounded(), which was ported from GMP and therefore lacks any comments or references explaining the algorithm.

[tarcieri]

FWIW, all of the fiat-crypto generated field implementations in the https://github.com/rustcrypto/elliptic-curves repo use Bernstein-Yang inversions

[mratsim]

See implementation in Rust: privacy-scaling-explorations/halo2curves#83

[tarcieri]

#372 added an initial implementation of Bernstein-Yang, but currently providing modular inversions only (and not fully wired up to the existing inversion APIs yet).

Constant-time GCD can be implemented in terms of its "divstep" function.

[tarcieri]

#472 implements GCD using Bernstein-Yang