Fast computation of multiplicative inverse modulo q

Question

Given a large number $q$ (say, a prime) and a number $a$ between 2 and $q-1$ what is the fastest algorithm known for computing the inverse of $a$ in the group of residue classes modulo $q$?

Answer 1

The fast Euclidean algorithm runs in time $O(M(n)\log n)$, where $n=\log q,$ and $M(n)$ is the time to multiply two $n$-bit integers. This yields a bit-complexity of $$ O(n\log^2 n\log\log n) $$ for the time to compute the inverse of an integer modulo $q$, using the standard Schonhage-Strassen algorithm for multiplying integers (a slightly better asymptotic result can be obtained using Furer's multiplication algorithm).

To understand the basic idea behind the fast Euclidean algorithm, recall that the standard Euclidean algorithm computes the (extended) gcd of two integers $r_0 > r_1$ by successively computing $m_i=\lfloor r_{i-1}/r_i\rfloor$ and setting $$ r_{i+1} = r_{i-1} - m_ir_i, $$ until it obtains $r_{k+1} = 0$, at which point $r_k = \gcd (r_0, r_1)$. This can be expressed in matrix form as $$ R_1 = \begin{bmatrix} r_0\newline r_1 \end{bmatrix};\qquad R_{i+1} = \begin{bmatrix} r_i\newline r_{i+1}\end{bmatrix} = M_iR_i;\qquad M_i=\begin{bmatrix} 0&1\newline 1&-m_i \end{bmatrix}, $$ and if we compute the matrix $S_k=M_kM_{k-1}\ldots M_1$, we have $R_{k+1}=S_kR_1$ which expresses the entry $r_k=\gcd(r_0,r_1)$ as a linear combination of $r_0$ and $r_1$. Assuming this gcd is 1, we can then read off the inverse of $r_1$ modulo $r_0$ (and vice versa) from the top row of $S_k$.

As described above, this involves $O(k)$ arithmetic operations on integers of size $O(n)$, and one can show that $k=O(n)$, leading to a running time that is roughly quadratic in $n$. The fast Euclidean algorithm achieves a quasi-linear running time by only computing $O(\log n)$ of the matrices $S_i$. Roughly speaking (and ignoring many important details), this is done by directly computing $S_{k/2}$ using what is known as a "half-gcd" algorithm, computing $R_{k/2+1}=S_{k/2}R_1$, and then proceeding recursively. The half-gcd algorithm, in turn, works by recursively calling itself. The depth of the recursion is $O(\log n)$ and this yields an $O(M(n)\log n)$ complexity bound.

This algorithm also works over polynomial rings and is often described in this setting. Further details can be found in the (incomplete) list of references below:

Chapter 11 of von zur Gathen and Gerhard, "Modern Computer Algebra," Cambridge University Press, 2003.

Chapter 2 of Yap, "Fundamental Problems of Algorithmic Algebra," Oxford University Press, 2000.

N. Moller, "On Schonhage's algorithm and subquadratic integer GCD computation," Mathematics of Comutation 77(261), pp. 589-607 (2008).

Stehle and Zimmerman, "A binary recursive GCD algorithm," ANTS-VI, LCNS 3076, pp. 411-425, 2004.

Answer 2

Instead of going all the way to the GCD with the Euclidean algorithm and working backwards to find a multiplicative inverse, you can go straight to the multiplicative inverse with the Euclidean algorithm.

If p is a prime and a is not divisible by p, perform the Euclidean algorithm on p^2 and ap+1. The first remainder less than p that appears is a multiplicative inverse for a mod p.

I don't know how fast this algorithm is compared to other methods. The number of steps to reach this inverse will be the same as the number of steps to reach GCD(a,p)=1 using the Euclidean algorithm with a and p. But the algorithm proposed above requires a comparison of the remainder at each step with p.

Answer 3

Another good reference is http://www.loria.fr/~zimmerma/mca/pub226.html

Other than the Euclidean algorithm as described in other answers, you can get time $O(M(n))$ if the modulus is of the form $p^k$, by working successively mod $p$, $p^2$, etc. See the link for details, section 2.5.

If you need to invert several numbers, say $x$ and $y$, it is often faster to invert $xy$ and then calculate $x^{-1} = (xy)^{-1}y$, $y^{-1} = (xy)^{-1}x$.

Answer 4

For arbitrary $q$ (not necessarily prime) the Euclidean algorithm is pretty fast in solving the problem "decide whether the residue class of $a$ is a unit and compute the inverse, if it exists".