On Newton–Raphson Iteration for Multiplicative Inverses Modulo Prime Powers
From MaRDI portal
Abstract: We study algorithms for the fast computation of modular inverses. Newton-Raphson iteration over -adic numbers gives a recurrence relation computing modular inverse modulo , that is logarithmic in . We solve the recurrence to obtain an explicit formula for the inverse. Then we study different implementation variants of this iteration and show that our explicit formula is interesting for small exponent values but slower or large exponent, say of more than bits. Overall we thus propose a hybrid combination of our explicit formula and the best asymptotic variants. This hybrid combination yields then a constant factor improvement, also for large exponents.
Recommendations
- Verified Newton-Raphson iteration for multiplicative inverses modulo powers of any base
- Numerical analysis meets number theory: Using rootfinding methods to calculate inverses mod pn
- The Calcualtion of Multiplicative Inverses Over GF(P) Efficiently Where P is a Mersenne Prime
- scientific article; zbMATH DE number 4144069
- Fast evaluation of modular functions using Newton iterations and the AGM
- scientific article; zbMATH DE number 1159711
- An algorithm for numerically inverting the modular \(j\)-function
- scientific article; zbMATH DE number 2016686
- On the number of places of convergence for Newton's method over number fields
- On Calculating Multiplicative Inverses Modulo $2^{m}$
Cited in
(3)
This page was built for publication: On Newton–Raphson Iteration for Multiplicative Inverses Modulo Prime Powers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5268120)
