优化/ 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进行重新调整，从而更高效