On Newton-Raphson iteration for multiplicative inverses modulo prime powers
Résumé
We study algorithms for the fast computation of modular inverses. We first give another proof of the formulas of [1] for the modular inverse modulo 2 , derived from Newton-Raphson iteration over p-adic fields, namely Hensel's lifting. From the expression of Newton-Raphson's iteration we then derive a recurrence relation and an actually explicit formula for the modular inverse, generalizing to any prime power modulus. On the one hand, we show then that despite a worse complexity the two newly obtained algorithms can be 4 times faster for small exponents. On the other hand, these two algorithms become slower for arbitrary precision integers of more than 1500 bits.
Origine : Fichiers produits par l'(les) auteur(s)