计算 (a^(2^N))%m 的最快算法？

Question

有一些众所周知的密码学算法来计算模幂 (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)

Answer 1

如果 m 是素数，你可以更快地计算。

您首先使用从右到左的二元方法计算 p = 2^N % (m-1)。

然后使用从右到左的二元方法计算 a^p % m，由于费马小定理，它等于原始表达式。

---

如果 m 不是素数，但足够小，可以将其分解，您可以计算欧拉 totient 函数并使用 欧拉定理。

如果无法根据 m 进行优化，那么您能做的最好的可能就是使用 蒙哥马利缩减。

Answer 2

此外，作为对 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

的特殊形式。

Answer 3

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)

Answer 4

如果您使用任何具有 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