有一些著名的密码学算法可以计算模指数 (a^b)%c (比如右到左二进制方法在这里 :http://en.wikipedia.org/wiki/Modular_exponentiation)。
但是是否存在计算形式为 (a^(2^N))%m 的模指数的算法,比 "传统" 算法更快?
非常感谢!
注意:
1) m 可以是非常大的质数...或者不是 (因此没有依赖于 m 的优化)
2) N 可以达到 2^32-1( N < 2^32)
有一些著名的密码学算法可以计算模指数 (a^b)%c (比如右到左二进制方法在这里 :http://en.wikipedia.org/wiki/Modular_exponentiation)。
但是是否存在计算形式为 (a^(2^N))%m 的模指数的算法,比 "传统" 算法更快?
非常感谢!
注意:
1) m 可以是非常大的质数...或者不是 (因此没有依赖于 m 的优化)
2) N 可以达到 2^32-1( N < 2^32)
m = p1 * p2 * ... * p{n}
,你可以使用欧拉定理:phi(m)= (p1-1)*(p2-1)*...*(p{n}-1)
。p = 2^N % phi(m)
并发现a^(2^N) % m = a^p % m
。2^N
的特殊形式。Evgeny和Rasmus给出了很好的答案。此外,记得使用连续平方算法来计算幂。也就是说,将指数(比如E
)用二进制表示:
E = b0*1 + b1*2 + ... + bk*2^k
其中每个bi
都是0
或1
,而bk = 1
是最后一个非零位。然后,您可以通过以下方式将一个数字(例如N
)提高到指数E
:
N^E (mod m) = n0^b0 * n1^b1 * ... * nk^bk (mod m)
在哪里
n0 = N (mod m)
n1 = n0^2 (mod m)
n2 = n1^2 (mod m)
...
nk = n(k-1)^k (mod m)
28^27 mod 76
,您需要N = 28
,E = 27
,m = 76
,计算过程如下:27 = 1 + 2 + 8 + 16
E = b0 + b1 + b3 + b4
并且
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
最后
28^27 (mod 76) = 28 * 24 * 36 * 4 (mod 76) = 20
N^ E (mod m) = n0 * n1 * n3 * n4 (mod 76)
(2^(2^N))%m
的公式。 - Dan D.