[python] pow (a, d, n)이 a ** d % n보다 훨씬 빠른 이유는 무엇입니까?

Miller-Rabin 소수성 테스트 를 구현하려고했는데 왜 중형 숫자 (~ 7 자리)에 너무 오래 (> 20 초) 걸리는지 의아해했습니다. 결국 문제의 원인이되는 다음 코드 줄을 발견했습니다.

x = a**d % n

(단 a, d및 n모든 유사하지만 동일하지 않은, 중간 번호는, **누승 연산자이며, %모듈러 연산자이다)

그런 다음 다음으로 바꾸려고 시도했습니다.

x = pow(a, d, n)

비교하면 거의 즉각적입니다.

컨텍스트를 위해 원래 기능은 다음과 같습니다.

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으로 실행) :

2642565
time: 23.785543s
2642565
time: 0.000030s

출력 (Python 3.3.0, 2.7.2로 실행하면 매우 유사한 시간이 반환 됨) :

2642565
time: 14.426975s
2642565
time: 0.000021s

그리고 관련 질문, 일반적으로 PyPy가 훨씬 빠를 때 PyPy보다 Python 2 또는 3으로 실행할 때이 계산이 거의 두 배 빠른 이유는 무엇입니까?

---

---

답변