優化/ Python中

Question

這裏給我糾正米勒拉賓素性測試是我的代碼：

import random 
def one_d(n): 
    b = n 
    # initialize n 
    s = 0 
    # while loop, terminating when s becomes odd 
    while n % 2 == 0: 
     # increment s 
     s = s+1 
     # divide n by 2 
     n = n/2 
    tuple1 = tuple([s,n]) 
    return tuple1 
    print "2^",s,"*",n,"=", b 
def miller_rabin(n, a): 
    list1 = [] 
    tuple1 = one_d(n-1) 
    for r in xrange(tuple1[0]): 
     list1.append((a**(2**(r)*tuple1[1])) % n) 
     if list1[r] == n-1 or list1[r] == 1: 
      return "True" 
    else: 
     return "False" 
def isprime(n): 
    for i in xrange(10): 
     a = random.randrange(2, n-1) 
     if miller_rabin(n, a) == "False": 
      return "False" 
    return "True 

據我瞭解，這個測試應該能夠處理非常大的數字，但我的腳本卡上相同的數字50034901.我假設我在某處發生了錯誤/嚴重低效 - 因爲我的腳本仍然適用於較小的數字。

Answer 1

確定經過進一步調查後，我意識到這是因爲我使用「％」代碼來執行我的模數計算，這比使用python的「pow」函數要低得多。前者在計算模量之前計算完整指數，因此必須處理非常大的數字。後者按步驟進行，每次都通過模數n進行重新調整，從而更高效