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

问题描述 投票:0回答:4

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

algorithm cryptography modulo
4个回答
18
投票

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

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

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


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

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


3
投票

此外,作为对 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
的特殊形式。


0
投票

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)

0
投票

如果您使用任何具有 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
   
© www.soinside.com 2019 - 2024. All rights reserved.