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).Thuật toán nhanh nhất để tính toán (a^(2^N))% m?
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)
Bạn có biết rằng Ronald L. Rivest của [LCS35 Time Capsule Crypto-Puzzle] (http://www.google.com/search?q=LCS35+Time+Capsule + Crypto-Puzzle) dựa trên vấn đề này? Và vấn đề này đã được chọn vì nó là một tính toán nối tiếp vốn có. Mặc dù nó sử dụng '(2^(2^N))% m'. –
Lưu ý rằng nếu bạn biết hệ số M, bạn có thể tính toán câu trả lời nhanh hơn lũy thừa. –