Thuật toán nhanh nhất để tính toán (a^(2^N))% m?

Question

Có các thuật toán nổi tiếng về mật mã để tính toán lũy thừa mô đun (a^b)% c (như phương pháp nhị phân từ phải sang trái ở đây: http://en.wikipedia.org/wiki/Modular_exponentiation).

Nhưng làm thuật toán tồn tại để tính toán lũy thừa mô đun của biểu mẫu (a^(2^N))% m nhanh hơn so với thuật toán "cổ điển"?

Cảm ơn bạn rất nhiều!

Lưu ý:

1) m có thể là một số nguyên tố rất lớn ... hay không (vì vậy không tối ưu hóa tùy thuộc vào m)

2) N có thể lớn như 2^32-1 (N < 2^32)

Answer 1

Nếu m là số nguyên tố, bạn có thể tính toán nhanh hơn rất nhiều.

Bạn bắt đầu với tính toán p = 2 ^N% (m-1) bằng phương pháp nhị phân từ phải sang trái.

Sau đó, bạn sử dụng phương pháp nhị phân từ phải sang trái để tính ^p% m, bằng biểu thức ban đầu vì Fermat's little theorem.

---

Nếu m là không đắc địa, nhưng đủ nhỏ, để nó có thể là yếu tố, bạn có thể tính toán Phi hàm Euler và sử dụng Euler's Theorem.

Nếu không có tối ưu hóa tùy thuộc vào m là có thể, có lẽ tốt nhất bạn có thể làm là sử dụng Montgomery reduction.

Answer 2

Ngoài ra, như một sự tổng quát để trả lời Evgeny của: nếu bạn biết thừa số của m: m = p1 * p2 * ... * p{n}, bạn có thể sử dụng Euler's theorem:

Tính hàm Ơ-le phi(m)= (p1-1)*(p2-1)*...*(p{n}-1).

Sau đó, bạn có thể tính p = 2^N % phi(m) và thấy rằng a^(2^N) % m = a^p % m.

Không ai trong số này sử dụng dạng đặc biệt là 2^N.

Answer 3

Evgeny và Rasmus đưa ra câu trả lời tuyệt vời. Để thêm vào đó, hãy nhớ sử dụng bình phương liên tiếp cho các quyền hạn. Đó là, viết số mũ, nói E, trong cơ sở 2:

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

nơi mỗi bi hoặc là 0 hoặc 1 và bk = 1 là bit khác không ngoái.Sau đó, bạn có thể nâng cao một số, nói N, đến số mũ E bởi

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

nơi

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

Ví dụ, để tính toán 28^27 mod 76, bạn có N = 28, E = 27, m = 76, và tính toán là

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

và

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 

và cuối cùng

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