¿Cuál es la manera más rápida (método general) para calcular la cantidad de $a^b \!\mod c$? Por ejemplo $a=2205$, $b=23$, $c=4891$.
Esta pregunta ya tiene respuestas:
- Exponenciación modular a mano ( $a^b\bmod c$ ) (12 respuestas )
Respuestas
¿Demasiados anuncios?
Supongamos que a,b,c hace referencia aquí son enteros positivos, como en tu ejemplo.
Para un determinado exponente b, puede ser más rápido (más corto) método de computación a^b de exponenciación binaria. Knuth tiene una discusión de este fenómeno en el Arte de la Programación de computadoras Vol. 2 (Semi-Algoritmos numéricos), Seg 4.6.3 y el índice término "adición de cadenas". Él cites b=15 como el caso más pequeño donde exponenciación binaria no es óptimo, en el que se requiere de seis a la multiplicación, pero a^3 puede ser calculado en dos multiplicaciones y, a continuación, (a^3)^5 en tres más para un total de cinco multiplicaciones.
Específicamente para el exponente b=23 el parsimonioso, además de la cadena implica los exponentes (por encima de 1) 2,3,5,10,13, punto en el cual a^23 = (a^10)*(a^13), para un total de seis multiplicaciones. Exponenciación binaria para b=23 requiere siete multiplicaciones.
Otro enfoque que puede producir resultados más rápidos cuando b es grande (no en tu ejemplo) depende de saber algo sobre la base de la a y el módulo de c. El recuerdo de Euler de la generalización de Fermat Poco de Thm. que si a,c son coprime, a continuación, a^d = 1 mod c para d de Euler phi función de c (el número de enteros positivos a menos de c y coprime). En particular, si c es un número primo, entonces por Fermat Poco de Thm. ya sea c divide a y a^b = 0 mod c o de lo a^b = a^e mod c donde e = b mod (c-1) desde phi(c) = c-1 para un primer c.
Si la base a y el módulo de c no coprime, entonces podría ser ventajoso para el factor de a en su máximo común factor c y su factor más grande que es coprime a c.
También puede ser ventajoso si c no es el primer factor en el primer poderes y hacer independiente exponentiations para cada factor, armando de nuevo juntos, a través de la del Resto Chino Thm. En tu ejemplo c = 4891 = 67*73, por lo que se pueden calcular a^b mod 67 y a^b mod 73 y combinar los resultados para obtener a^b mod c. Esto es especialmente útil si usted está limitado en la precisión de la aritmética de enteros que usted puede hacer.
Rory MacLeod
Puntos
4574
El cuadrado y multiplicar algoritmo es generalmente la manera más rápida de hacer exponenciación modular.
Xenph Yan
Puntos
20883
Una manera común de exponenciación rápida, ya sea en la aritmética modular o, en general, es la exponenciación al cuadrado. Aquí es la sección donde se habla específicamente acerca de $a^b\bmod c$.
David HAust
Puntos
2696
Generalmente repetido cuadratura funciona bien. Se merece ser mejor conocido que este surge simplemente de escribir el exponente binario base en Horner polinomio de la forma, es decir, $\rm\ d_0 + x\ (d_1 + x\ (d_2\ +\:\cdots))\:.\ $ a Continuación es un ejemplo de computación $\rm\ a^{101}\ $ por repetir la cuadratura. Tenga en cuenta que el repetido forma cuadrada surge simplemente de la realización de diversas sustituciones en el binario polinomio de Horner forma es decir $\rm\ 1\to a,\ \ 0\to 1,\ \ (x)\:2\to (x)^2\ $ a $101_{10} = 1100101_2\ $ ampliado en Horner forma, viz.
