flint
flint copied to clipboard
Implement `mpn_gcdinv` with precomputed powers of two modular inverses
Should allow for fast iterations via the binary Euclidean algorithm. Would probably work very well with the mpn_mod module.
What algorithm precisely? The binary Euclidean algorithm expressly avoids divisions, and in the ordinary Euclidean algorithm the divisor changes each iteration so precomputations don't seem useful.
Modified version of Algorithm 1 of Thomas Pornin's paper