Fast computation of multiplicative inverse modulo q - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T04:59:17Z http://mathoverflow.net/feeds/question/40997 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/40997/fast-computation-of-multiplicative-inverse-modulo-q Fast computation of multiplicative inverse modulo q Idoneal 2010-10-04T09:05:57Z 2010-10-10T06:43:35Z <p>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$?</p> http://mathoverflow.net/questions/40997/fast-computation-of-multiplicative-inverse-modulo-q/41002#41002 Answer by Sebastian Petersen for Fast computation of multiplicative inverse modulo q Sebastian Petersen 2010-10-04T09:41:42Z 2010-10-04T09:41:42Z <p>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". </p> http://mathoverflow.net/questions/40997/fast-computation-of-multiplicative-inverse-modulo-q/41004#41004 Answer by AVS for Fast computation of multiplicative inverse modulo q AVS 2010-10-04T10:07:35Z 2010-10-04T16:28:53Z <p>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).</p> <p>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&amp;1\newline 1&amp;-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$.</p> <p>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.</p> <p>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:</p> <p>Chapter 11 of von zur Gathen and Gerhard, "Modern Computer Algebra," Cambridge University Press, 2003.</p> <p>Chapter 2 of Yap, "Fundamental Problems of Algorithmic Algebra," Oxford University Press, 2000.</p> <p>N. Moller, "<a href="http://www.lysator.liu.se/~nisse/archive/S0025-5718-07-02017-0.pdf" rel="nofollow">On Schonhage's algorithm and subquadratic integer GCD computation</a>," Mathematics of Comutation 77(261), pp. 589-607 (2008).</p> <p>Stehle and Zimmerman, "<a href="http://perso.ens-lyon.fr/damien.stehle/downloads/recbinary.pdf" rel="nofollow">A binary recursive GCD algorithm</a>," ANTS-VI, LCNS 3076, pp. 411-425, 2004.</p> http://mathoverflow.net/questions/40997/fast-computation-of-multiplicative-inverse-modulo-q/41631#41631 Answer by Barry for Fast computation of multiplicative inverse modulo q Barry 2010-10-09T21:53:29Z 2010-10-09T21:53:29Z <p>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.</p> <p>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. </p> <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.</p> http://mathoverflow.net/questions/40997/fast-computation-of-multiplicative-inverse-modulo-q/41657#41657 Answer by Luke Gustafson for Fast computation of multiplicative inverse modulo q Luke Gustafson 2010-10-10T06:43:35Z 2010-10-10T06:43:35Z <p>Another good reference is <a href="http://www.loria.fr/~zimmerma/mca/pub226.html" rel="nofollow">http://www.loria.fr/~zimmerma/mca/pub226.html</a></p> <p>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.</p> <p>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$.</p>