flint icon indicating copy to clipboard operation
flint copied to clipboard

Implement `mpn_gcdinv` with precomputed powers of two modular inverses

Open albinahlback opened this issue 1 year ago • 2 comments

Should allow for fast iterations via the binary Euclidean algorithm. Would probably work very well with the mpn_mod module.

albinahlback avatar May 13 '24 21:05 albinahlback

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.

fredrik-johansson avatar May 14 '24 10:05 fredrik-johansson

Modified version of Algorithm 1 of Thomas Pornin's paper

albinahlback avatar May 14 '24 15:05 albinahlback