0

これが私のコードです：

    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 のような数で動かなくなります。どこかでエラー/重大な非効率性を犯したと思います - 私のスクリプトは小さな数でも機能するためです.

4

1 に答える 1

0

さらに調査したところ、「%」コードを使用してモジュラス計算を実行しているため、Pythonの「pow」関数を使用するよりもはるかに非効率的であることがわかりました。前者は、モジュラスを計算する前に完全な指数を計算するため、非常に大きな数を処理する必要があります。後者は段階的に進み、毎回係数 n で再調整されるため、より効率的です

于 2016-11-17T12:29:14.197 に答える