Algoritmo más rápido para calcular (a^(2^N))% m?

Question

Existen algoritmos bien conocidos para que la criptografía calcule la exponenciación modular (a^b)% c (como el método binario de derecha a izquierda aquí: http://en.wikipedia.org/wiki/Modular_exponentiation).

¿Pero existe el algoritmo para calcular la exponenciación modular de la forma (a^(2^N))% m más rápido que con los algoritmos "clásicos"?

¡Muchas gracias!

Nota:

1) M puede ser un gran primer ... o no (por lo que no en función de la optimización m)

2) N puede ser tan grande como 2^32-1 (N < 2^32)

Answer 1

Si m es primo, puede calcular esto mucho más rápido.

Usted comienza con la computación de p = 2 ^N% (m-1) con el método binario de derecha a izquierda.

Luego se usa el método binario de derecha a izquierda para calcular un ^p% m, que es igual a la expresión original debido a Fermat's little theorem.

---

Si m no es primo, pero lo suficientemente pequeño, por lo que se puede factorizar, puede calcular la función totient de Euler y utiliza Euler's Theorem.

Si no es posible una optimización en función de m, probablemente lo mejor que puede hacer es usar Montgomery reduction.

Answer 2

También, como una generalización de la respuesta de Evgeny: si conoce la factorización de m: m = p1 * p2 * ... * p{n}, puede utilizar Euler's theorem:

Calcular el totient phi(m)= (p1-1)*(p2-1)*...*(p{n}-1).

Luego puede calcular p = 2^N % phi(m) y encontrar que a^(2^N) % m = a^p % m.

Ninguno de esto usa la forma especial de 2^N, sin embargo.

Answer 3

Evgeny y Rasmus dan excelentes respuestas. Para agregar a eso, recuerda usar la cuadratura sucesiva para los poderes. Es decir, escribir el exponente, por ejemplo E, en la base 2:

E = b0*1 + b1*2 + ... + bk*2^k 

donde cada bi está bien 0 o 1 y bk = 1 es el último bit distinto de cero.A continuación, puede plantear una serie, digamos N, al exponente E por

N^E (mod m) = n0^b0 * n1^b1 * ... * nk^bk (mod m) 

donde

n0 = N (mod m) 
n1 = n0^2 (mod m) 
n2 = n1^2 (mod m) 
... 
nk = n(k-1)^k (mod m) 

Por ejemplo, para calcular 28^27 mod 76, tiene N = 28, E = 27, m = 76, y el cálculo se

27 = 1 + 2 + 8 + 16 
E = b0 + b1 + b3 + b4 

y

n0 = 28 (mod 76) 
n1 = 28^2 (mod 76) = 24 
n2 = 24^2 (mod 76) = 44 
n3 = 44^2 (mod 76) = 36 
n4 = 36^3 (mod 76) = 4 

y finalmente

28^27 (mod 76) = 28 * 24 * 36 * 4 (mod 76) = 20 
N^ E (mod m) = n0 * n1 * n3 * n4 (mod 76)