On the Inversion Modulo a Power of an Integer
This work provides a more flexible and efficient method for computing modular inverses in cryptography and number theory, though it is incremental as it builds on prior algorithms.
The paper tackles the problem of computing modular inverses for powers of any integer, generalizing existing algorithms from prime powers to any integer powers, and demonstrates significant efficiency improvements in experiments.
Recently, Koç proposed a neat and efficient algorithm for computing \[ x = a^{-1} \pmod {p^k} \] for a prime $p$ based on the exact solution of linear equations using $p$-adic expansions. The algorithm requires only addition and right shift per step. In the first part of this paper, we design an algorithm that computes \[ x = a^{-1} \pmod {n^k} \] for any integers $a, n>1$ with $\gcd(a, n)=1$. The algorithm has a motivation from the schoolbook multiplication and achieves both efficiency and generality. The greater flexibility of our algorithm is explored by utilizing the built-in arithmetic of computer architecture, e.g., $n=2^{64}$, and experimental results show significant improvements. This paper also contains some results on modular inverse based on an alternative proof of correctness of Koç algorithm. For the computation of modular inverses when the modulus is a special power of a prime $p$ (i.e., of the form $p^{2^s}$), an efficient algorithm was developed by Dumas and later improved by Hurchalla. These methods are based on Hensel lifting and perform particularly well when $p=2$ and $2^s$ matches the native bit width of a computer. In the second part of the paper, we present a generalization of these methods to moduli of the form $n^{2^s}$ for any integer $n>1$. The derivation of our algorithm follows from a simple algebraic manipulation.