为什么 pow(a, d, n) 比 a**d % n 快这么多? [英] Why is pow(a, d, n) so much faster than a**d % n?

问题描述

我试图实现一个 Miller-Rabin 素性测试，但很困惑为什么它中型号码(~7 位数)花费了很长时间(> 20 秒).我最终发现以下代码行是问题的根源:

I was trying to implement a Miller-Rabin primality test, and was puzzled why it was taking so long (> 20 seconds) for midsize numbers (~7 digits). I eventually found the following line of code to be the source of the problem:

x = a**d % n

(其中 a、d 和 n 都是相似但不相等的中型数字，** 是取幂运算符，% 是模运算符)

(where a, d, and n are all similar, but unequal, midsize numbers, ** is the exponentiation operator, and % is the modulo operator)

然后我尝试用以下内容替换它:

I then I tried replacing it with the following:

x = pow(a, d, n)

相比之下，它几乎是瞬间的.

and it by comparison it is almost instantaneous.

对于上下文，这是原始函数:

For context, here is the original function:

from random import randint

def primalityTest(n, k):
    if n < 2:
        return False
    if n % 2 == 0:
        return False
    s = 0
    d = n - 1
    while d % 2 == 0:
        s += 1
        d >>= 1
    for i in range(k):
        rand = randint(2, n - 2)
        x = rand**d % n         # offending line
        if x == 1 or x == n - 1:
            continue
        for r in range(s):
            toReturn = True
            x = pow(x, 2, n)
            if x == 1:
                return False
            if x == n - 1:
                toReturn = False
                break
        if toReturn:
            return False
    return True

print(primalityTest(2700643,1))

定时计算示例:

from timeit import timeit

a = 2505626
d = 1520321
n = 2700643

def testA():
    print(a**d % n)

def testB():
    print(pow(a, d, n))

print("time: %(time)fs" % {"time":timeit("testA()", setup="from __main__ import testA", number=1)})
print("time: %(time)fs" % {"time":timeit("testB()", setup="from __main__ import testB", number=1)})

输出(使用 PyPy 1.9.0 运行):

Output (run with PyPy 1.9.0):

2642565
time: 23.785543s
2642565
time: 0.000030s

输出(使用 Python 3.3.0 运行，2.7.2 返回非常相似的时间):

Output (run with Python 3.3.0, 2.7.2 returns very similar times):

2642565
time: 14.426975s
2642565
time: 0.000021s

还有一个相关的问题，为什么这个计算在使用 Python 2 或 3 时几乎是使用 PyPy 的两倍，而通常 PyPy 是 更快?

And a related question, why is this calculation almost twice as fast when run with Python 2 or 3 than with PyPy, when usually PyPy is much faster?

推荐答案

请参阅关于 模幂 的维基百科文章.基本上，当您执行 a**d % n 时，您实际上必须计算 a**d，这可能非常大.但是有一些方法可以计算 a**d % n 而不必计算 a**d 本身，这就是 pow 所做的.** 运算符无法执行此操作，因为它无法预见未来"知道您将立即取模.

See the Wikipedia article on modular exponentiation. Basically, when you do a**d % n, you actually have to calculate a**d, which could be quite large. But there are ways of computing a**d % n without having to compute a**d itself, and that is what pow does. The ** operator can't do this because it can't "see into the future" to know that you are going to immediately take the modulus.

这篇关于为什么 pow(a, d, n) 比 a**d % n 快这么多?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！