6
$\begingroup$

Is there an algorithm that can compute modular inverses in less than $O(n^{2})$? If not, is the Euclidean algorithm provably optimal?

$\endgroup$
4
$\begingroup$

Firstly, you use $O(n^2)$ in a way that I'm not accustomed. If we are using it on two numbers with the larger of size $n$, then the extended Euclidean algorithm runs in time $O( (\log n)^2)$. In fact, Lamé showed that the number of steps is less than $10$ times the number of digits of the smaller of the two numbers in the algorithm$^{[1]}$. This proof is short and uses the Fibonacci numbers (which happen to be the exact cases when there is worst-case running time).

But that is besides the point. In practice, there is a faster algorithm that is still often used, although it has roughly the same asymptotic growth of $O( \log^2 n)$. It's called the Binary GCD algorithm (also called Stein's algorithm), since it takes advantage of how computers store data.

For very large numbers, you might use the asymptotically faster methods of Schönhage$^{[2]}$ or Stehlé$^{[3]}$.

I don't describe them, but instead point you towards a survey article by Möller, which describes 4 different sub-$O( \log^2 n )$ algorithms and their implementations.


References

[1]: Lamé, 1844. "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes Rendus Acad. Sci. 19: 867–870.

[2]: Cesari G (1998). "Parallel implementation of Schönhage's integer GCD algorithm". In G. Buhler. Algorithmic Number Theory: Proc. ANTS-III, Portland, OR. New York: Springer-Verlag. pp. 64–76. Volume 1423 in Lecture notes in Computer Science.

[3]:Stehlé D, Zimmermann P (2005). "Gal's accurate tables method revisited". Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17). Los Alamitos, CA: IEEE Computer Society Press.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 IIRC Lamé's result states that (in the worst case) five iterations of Euclid will reduce the number of digits by one. Do you count two operations per iteration or how did you get ten? $((1+\sqrt5)/2)^5>10$ $\endgroup$ – Jyrki Lahtonen Jul 5 '13 at 6:37
  • $\begingroup$ In CS it's standard to talk about algorithmic complexity in terms of the size of the input rather than the value it represents, so the $n$ in $O(n^2)$ would be the sum of the logarithms of the two numbers, and it's equivalent to your bound in terms of the values of the numbers. $\endgroup$ – Peter Taylor Jul 5 '13 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.