On the Inversion Modulo a Power of an Integer Guangwu Xu, Yunxiao Tian, Bingxin Yang Abstract Recently, Koç proposed a neat and efficient algorithm for computing x = a − 1 ( mod p k ) x=a^{-1}\pmod{p^{k}} for a prime p p based on the exact solution of linear equations using p p -adic expansions. The algorithm requires only addition and right shift per step. In this paper, we design an algorithm that computes x = a − 1 ( mod n k ) x=a^{-1}\pmod{n^{k}} for any integer n > 1 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 build-in arithmetic of computer architecture, e.g., n = 2 64 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. Key words: Multiplicative inverse, Modular arithmetic, Schoolbook multiplication. 1 Introduction Modular arithmetic is a basic tool in modern computation. Its efficiency impacts heavily on applications in cryptography and communication. In practice, modular multiplication is of the most concern with respect to the cost of computation. There are several modern methods for achieving efficient modular multiplication. The famous Montgomery reduction algorithm [ 6 ] makes a very clever use of the fact that integer division (and modulation) by a power of 2 is trivial. The algorithm works on integers with Montgomery representation and requires to compute inverse of an odd integer (the modulus) modulo the special number R=2^{k} . The computational task of computing inversion of an odd integer modulo a power of 2 is often seen in other scenarios, e.g. [ 7 ] . It is expected that the calculation of an inverse modulo a power of 2 is easier than general case. Indeed there have been several surprisingly simple and efficient methods designed for this purpose. In [ 3 ] , Dussé and Kaliski gave an efficient algorithm for computing the inverse by modifying the extended euclidean algorithm. Arazi and Qi introduce several algorithms to compute x=a^{-1}\pmod{2^{k}} for an odd integer a>0 in [ 1 ] with multiplication being eliminated from the computation. Dumas [ 2 ] observed that the idea of Hensel lifting can be used to create an iterative formula for computing a^{-1}\pmod{p^{k}} for prime number p and k=2^{s} , with p\not|a . Recently in [ 5 ] , Koç proposed a neat and efficient algorithm for computing x=a^{-1}\pmod{p^{k}} for a prime number p and k>0 [ 5 ] . This algorithm is based on the exact solution of linear equations using p -adic expansions. Nice features of Koç algorithm include that only addition (subtraction) 1 1 1 The algorithm does require multiplications of a digit with a number. and right shifting (dividing by p ) are used in each step. We would also like to mention that an inverse modulo power of 2 algorithm proposed by Hurchalla [ 4 ] gives the best performance when within the bit size of instruction set of an architecture (e.g., the modulus is 2^{64} ). The main purpose of this paper is to design an efficient and flexible algorithm that computes x=a^{-1}\pmod{n^{k}} for any integers n>1 and k>0 . The motivation of our algorithm is the schoolbook multiplication. The formulation of carries in computation makes the use of right shifting (dividing by n ) appear natural. Besides its generality, our algorithm also has a slight improvement over Koç algorithm in terms of the number of operations used. However, our algorithm is flexible in that n>1 can be arbitrary, as long as the number a to be inverted satisfies \gcd(a,n)=1 . A useful application is to set n=2^{64} , so one can compute modulo inverse of an odd integer of the form a=a_{0}+a_{1}2^{64}+a_{2}(2^{64})^{2}+\cdots+a_{k-1}(2^{64})^{k-1},\ 0\leq a_{i}<2^{64}, to well utilize the build-in arithmetic of a 64 -bit computer. Our experiment show that the speed improvement compared to the existing methods is very significant. The contents of the rest of this paper is arranged as follows: Section 2 describes Koç’s algorithm for inversion modulo p^{k} , with an alternative proof of its correctness and some further discussion to specify several useful properties of the method. In section 3, the method of inverse modulo a general power is presented, together with its elementary motivation and formulation, as well as a discussion of its performance. Section 4 summarizes the paper . 2 Koç’s Algorithm for Inversion Mod p^{k} In [ 5 ] , Koç proposed a method for computing inverse with a modulus being a prime power. Let us fix a prime p and an integer k>0 . Given an integer a>0 such that p\not|a , then x=a^{-1}\pmod{p^{k}} exists. Since 00 ; integer 00 and an odd integer a<2^{k} 2: a^{-1}\pmod{2^{k}} 3: function ModInverse2 ( a,2^{k} ) 4: b_{0} \leftarrow 1 5: for i=0 to k-1 do 6: X_{i} \leftarrow b_{i}\pmod{2} 7: b_{i+1} \leftarrow \frac{b_{i}-aX_{i}}{2} 8: end for 9: return x=(X_{k-1}\cdots X_{1}X_{0})_{2} 10: end function 3 An Algorithm of Inversion Mod n^{k} for General n The main task of this section is to develop a method of computing modulo inverse with modulus being a power of arbitrary integer bigger than 1 . Let us fix integers n>1,k>0 . Let 01 , integer k>0 , integer a0 and an odd integer a<2^{k} 2: a^{-1}\pmod{2^{k}} 3: function ModInverse2 ( a,2^{k} ) 4: T_{0} \leftarrow 0 5: X_{0} \leftarrow 1 6: for i=1 to k-1 do 7: T_{i} \leftarrow \frac{T_{i-1}+X_{i-1}a}{2} 8: X_{i} \leftarrow T_{i}\pmod{2} 9: end for 10: return x=(X_{k-1}\cdots X_{1}X_{0})_{2} 11: end function In the following, we have some further discussions on algorithm 1 . Besides its generality for allowing modulus to be a power of any integer bigger than 1 , Algorithm 1 also save one multiplication by a digit over Koç algorithm (algorithm 1 ). This is because the length of the for loop in our algorithm is k-1 , instead of k . Each step in the loop has two such multiplications, but we have one multiplication in the initial step, this leaves one saving of one multiplication by a digit. However, a greater flexibility provided by our algorithm implies more optimization possibilities. As a particular example, we consider the case of n=2^{64} . We show that by utilizing the build-in arithmetic of a computer whose native bit width of a CPU’s arithmetic instructions is 64 , a significant speed up is seen. The following table contains comparisons of our algorithm 1 for the setup of n=64 with (1) Koç algorithm (algorithm 2 ), and (2) Hurchalla algorithm in [ 4 ] , for k=128,256,512,1024,2048,3072 and 4096 (in our algorithm, these corresponding to k=2,4,8,16,32,48 and 64 ). The experiment are conducted on Unbuntu 24.04.2, with CPU AMD Ryzen 7 8845HS. Programs are compiled using gcc 14.2.0 with option -Ofast -march=native -flto . The numbers in the second, third and fourth columns are average running time in ns . The length k of modulus algorithm 1 with n=2^{64} and initial a^{-1}\pmod{n} computed using Hurchalla alg. Hurchalla algorithm in [ 4 ] Binary version of Koç algorithm (algorithm 2 ) 128 \mathbf{2.81} 7.11 177.89 256 \mathbf{22.27} 164.48 5546.50 512 \mathbf{68.58} 442.70 14469.55 1024 \mathbf{201.85} 1538.34 39118.61 2048 \mathbf{1302.52} 6228.26 97033.69 3076 \mathbf{4119.65} 14851.10 225846.22 4096 \mathbf{7253.46} 26724.95 389627.86 In this experiment, we use Hurchalla algorithm to compute a^{-1}\pmod{2^{64}} for the initialization of c\leftarrow a^{-1}\pmod{n} in our algorithm, and all basic operations are done by 64 -bit native machine arithmetic. This results a great gain of efficiency. 4 Conclusions In this paper, we develop method of computing inverse modulo a power of arbitrary integer bigger than 1 . In formulation, our algorithm is comparable with a recent algorithm of Koç for prime power, but with a motivation from the elementary schoolbook multiplication. Since the base (or radix) of our modulus is not restricted, we are able to compute a^{-1}\pmod{n^{k}} for suitable n>1 . The experiment using n=2^{64} demonstrates a great performance over existing methods. The paper also describes an alternative proof of correctness of Koç algorithm and explains how to use the proof to derive a^{-1}\pmod{n^{s}} and (n^{s})^{-1}\pmod{a} for s