有一些众所周知的密码学算法来计算模幂 (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)
此外,作为对 Evgeny 答案的概括:如果你知道 m 的因式分解:
m = p1 * p2 * ... * p{n}
,你可以使用 欧拉定理:
计算 totient
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
为底写下指数,例如 2
:
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)
如果您使用任何具有 64 位 double-prec 浮点作为数字底层表示的平台,例如
Javascript
或 awk
,
您可以通过非常非常少的步骤完成
28^27 % 76
:
28 = a
76 = m
10,578,455,953,408 = v = a^9
28^27 % 76 := ( a^9 )^3 % m
= ( a^9 % m )^3 % m
= ( v % m )^3 % m
-------------------
= ( 20 )^3 % 76
= 8000 % 76
---------------
= 20
或作为单个端到端方程而不会溢出:
( 28^9 % 76 )^3 % 76
一种完全不同的方法是实现
28
和 76
与 0 (mod 4)
一致,从而使底层表达式
7^27 % 19 * 4^(27-1) % 19 * 4
从
7^3 % 19 => 1
开始,整个7^27 % 19
就变成了1
,而你只需计算
4^26 % 19 * 4
4^26 % 19 * 4 4^27 % 76
= 5 * 4 = ( 4^ 3 )^9 % 76
--------------- or = ( -12 )^9 % 76
= 20 = ( -56 )^3 % 76
= ( 20 )^3 % 76
-----------------
= 20