存儲器錯誤

Question

DEF重複（M，結果，A，S，d）：

check = True 
r = 0 
while r <= s - 1: 
    if result == m - 1: 
     check = False 
     return check 
    result = (result ** 2) % m 
    r = r + 1 
return check 

我需要編寫一個素性測試蟒程序來測試非常大的數字，比如至少100數字。上面的代碼是用於重複平方的Miller Rabin確定性素性測試代碼的一部分。它對於大數量來說非常慢。我如何加快速度？這是一個項目。謝謝！

Answer 1

您的問題可能是(result ** 2) % m，使用pow的3參數版本做相同的，但更有效，因爲算法使用的是Modular exponentiation和比第一做x**n，然後計算其模好得多。這樣你保證永遠不會比m更大一些，而如果你做(x**n) % m你可以有x**n非常遠大於m，可能是您事業的問題

也沒必要爲check變量，你不不使用a。 此外，你從0到S-1，更好的利用範圍

def repeated(m, result, s, d): 
    for r in range(s): 
     if result == m - 1: 
      return False 
     result = pow(result, 2, m) 
    return True 

現在對於的test

如果

你需要這部分a，d，s和n這是我該怎麼做

def mr_check(n,a,s,d): 
    result = pow(a,d,n) 
    if result == 1 : 
     return False 
    for r in range(s): 
     result = pow(result,2,n) 
     if result == n-1: 
      return False 
    return True