Hay un algoritmo que puede calcular inversos modulares en menos de $O(n^{2})$? Si no, es el algoritmo de Euclides seguramente óptima?
Respuesta
¿Demasiados anuncios?
En primer lugar, utilizar $O(n^2)$ en una manera que yo no estoy acostumbrado. Si estamos utilizando en dos números con el más grande de tamaño $n$, entonces el algoritmo de Euclides extendido se ejecuta en el tiempo $O( (\log n)^2)$. De hecho, Lamé mostró que el número de pasos es de menos de $10$ multiplicado por el número de dígitos de la menor de los dos números en el algoritmo de$^{[1]}$. Esta prueba es corta y utiliza los números de Fibonacci (que pasaría a ser la exacta casos cuando no es el peor caso de tiempo de ejecución).
Pero que es además el punto. En la práctica, hay un algoritmo más rápido que todavía se utiliza a menudo, a pesar de que tiene aproximadamente el mismo asintótica crecimiento de $O( \log^2 n)$. Se llama Binario MCD algoritmo (también llamado Stein algoritmo), ya que se aprovecha de cómo los ordenadores para almacenar datos.
Para números muy grandes, puede utilizar la asintóticamente métodos más rápidos de Schönhage$^{[2]}$ o Stehlé$^{[3]}$.
Yo no describir, sino que apunte hacia un artículo por Möller, que describe 4 diferentes sub-$O( \log^2 n )$ algoritmos y sus implementaciones.
Referencias
[1]: Lamé, 1844. "Note sur la limite du nombre des divisiones dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes Rendus Acad. Sci. 19: 867-870.
[2]: Cesari G (1998). "Paralelamente la aplicación de Schönhage del entero MCD algoritmo". En G. Buhler. Algoritmos De La Teoría De Números: Proc. Las HORMIGAS-III, Portland, or. Nueva York: Springer-Verlag. páginas 64-76. Volumen 1423 en Lecture notes in Computer Science.
[3]:Stehlé D, Zimmermann P (2005). "Gal precisa tablas método revisited". Actas de la 17 IEEE Simposio en el Equipo de la Aritmética (ARITH-17). Los Alamitos, CA: IEEE Computer Society Press.
