Najszybszy algorytm do obliczenia (a^(2^N))% m?

Question

Istnieją dobrze znane algorytmy kryptograficzne do obliczania modułowej potęgowania (a^b)% c (podobnie jak w przypadku metody binarnej od prawej do lewej tutaj: http://en.wikipedia.org/wiki/Modular_exponentiation).

Ale czy istnieje algorytm obliczania modułowej potęgowania formy (a^(2^N))% m szybciej niż w przypadku algorytmów "klasycznych"?

Dziękuję bardzo!

Uwaga:

1) m może być bardzo duża pierwsza ..., czy nie (tak nie optymalizację w zależności od m)

2) N może być tak duża, jak 2^32-1 (N < 2^32)

Answer 1

Jeśli m jest liczbą pierwszą, można to obliczyć znacznie szybciej.

Zaczynasz od obliczenia p = 2 ^N% (m-1) metodą binarną od prawej do lewej.

Następnie należy użyć metody binarnej od prawej do lewej, aby obliczyć wartość ^p% m, która jest równa oryginalnemu wyrażeniu z powodu Fermat's little theorem.

---

Jeżeli m jest nie pierwsza, ale na tyle mały, aby mógł on zostać uwzględniony, można obliczyć funkcję totient Eulera i używać Euler's Theorem.

Jeśli nie jest możliwa optymalizacja w zależności od m, prawdopodobnie najlepszą możliwą metodą jest użycie Montgomery reduction.

Answer 2

Również jako uogólnienie, aby odpowiedzieć Evgeny: jeśli znasz faktoryzacji M: m = p1 * p2 * ... * p{n}, można użyć Euler's theorem:

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

Następnie można obliczyć p = 2^N % phi(m) i znaleźć a^(2^N) % m = a^p % m.

Żadne z powyższych nie używa specjalnego formularza 2^N.

Answer 3

Evgeny i Rasmus dają wspaniałe odpowiedzi. Aby dodać do tego, pamiętaj, aby używać kolejnych kwadratów dla mocy. Oznacza to, że wykładnik napisać, powiedzieć E w bazie 2:

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

gdzie każdy bi jest albo 0 lub 1 i bk = 1 jest ostatnią niezerową bit.Następnie można podnieść liczbę, powiedzmy N, aby wykładnik E przez

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

gdzie

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

Na przykład, aby obliczyć 28^27 mod 76 masz N = 28, E = 27, m = 76, a obliczenie jest

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

i

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 

i wreszcie

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