2012/09/30 by Jean-Guillaume Dumas
Computer Science · Mathematics · #Analytic Number Theory Research #Computation #Constant (computer programming) #Exponent #Inverse #Logarithm #Modulo #Multiplicative function #Multiplicative inverse #Polynomial and algebraic computation #Prime (order theory) #advanced mathematical theories #cs.MS #cs.SC
paper · pdf · doi:10.1109/tc.2013.94
published as IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2014, 63 (8), pp.2106-2109
openalex publication_date 2013/04/19 · arxiv created 2018/05/15 · arxiv updated 2019/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study algorithms for the fast computation of modular inverses. Newton–Raphson iteration overp-adic numbers gives a recurrence relation computing modular inverse modulopm, that is logarithmic inm. 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 700 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.