PollardP1_rhoコードに問題がありますが、修正方法がわかりません

Question

MillerRabin + PollardP1_rhoメソッドを使用して、整数を複雑な時間の複雑さを減らすためにPython3の素数に分解しようとしましたが、問題がどこにあるのか分かっていましたが、私はアルゴリズムのチロであり、修正方法はわかりませんでしたので、すべての相対コードをここに入れます。それは停止しなかった

PrimeFactorsListGenerator(4) 

と、このループ：：私はこれをテストしてみました

import random 

def gcd(a, b): 
    """ 
    a, b: integers 
    returns: a positive integer, the greatest common divisor of a & b. 
    """ 
    if a == 0: 
     return b 
    if a < 0: 
     return gcd(-a, b) 
    while b > 0: 
     c = a % b 
     a, b = b, c 
    return a 

def mod_mul(a, b, n): 
    # Calculate a * b % n iterately. 
    result = 0 
    while b > 0: 
     if (b & 1) > 0: 
      result = (result + a) % n 
     a = (a + a) % n 
     b = (b >> 1) 
    return result 

def mod_exp(a, b, n): 
    # Calculate (a ** b) % n iterately. 
    result = 1 
    while b > 0: 
     if (b & 1) > 0: 
      result = mod_mul(result, a, n) 
     a = mod_mul(a, a, n) 
     b = (b >> 1) 
    return result 

def MillerRabinPrimeCheck(n): 
    if n in {2, 3, 5, 7, 11}: 
     return True 
    elif (n == 1 or n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0): 
     return False 
    k = 0 
    u = n - 1 
    while not (u & 1) > 0: 
     k += 1 
     u = (u >> 1) 
    random.seed(0) 
    s = 5 #If the result isn't right, then add the var s. 
    for i in range(s): 
     x = random.randint(2, n - 1) 
     if x % n == 0: 
      continue 
     x = mod_exp(x, u, n) 
     pre = x 
     for j in range(k): 
      x = mod_mul(x, x, n) 
      if (x == 1 and pre != 1 and pre != n - 1): 
       return False 
      pre = x 
     if x != 1: 
      return False 
     return True 

def PollardP1_rho(n, c): 
    ''' 
    Consider c as a constant integer. 
    ''' 
    i = 1 
    k = 2 
    x = random.randrange(1, n - 1) + 1 
    y = x 
    while 1: 
     i += 1 
     x = (mod_mul(x, x, n) + c) % n 
     d = gcd(y - x, n) 
     if 1 < d < n: 
      return d 
     elif x == y: 
      return n 
     elif i == k: 
      y = x 
      k = (k << 1) 

result = [] 
def PrimeFactorsListGenerator(n): 
    if n <= 1: 
     pass 
    elif MillerRabinPrimeCheck(n) == True: 
     result.append(n) 
    else: 
     a = n 
     while a == n: 
      a = PollardP1_rho(n, random.randrange(1,n - 1) + 1) 
     PrimeFactorsListGenerator(a) 
     PrimeFactorsListGenerator(n // a) 

PollardP1_rho(4, random.randrange(1,4 - 1) + 1) 

は、私はすでにPollardP1_rho前に、機能をテストしているが、彼らは正常に動作し、私はPollardP1_rhoが正しく番号4を扱うことができないことを知っています。数字5もそれを修正できますか？

Answer 1

私はそれを自分で解決しました。 コードに間違いが1つあります。 関数の外部でvar 'result'をグローバル変数として使用しないでください。関数内で定義し、result.extend（）を使用して再帰的プロセス全体の可用性を確保する必要があります。PollardP1_rho（n、c ）とPrimeFactorsListGenerator（N）：

def Pollard_rho(x, c): 
    ''' 
    Consider c as a constant integer. 
    ''' 
    i, k = 1, 2 
    x0 = random.randint(0, x) 
    y = x0 
    while 1: 
     i += 1 
     x0 = (mod_mul(x0, x0, x) + c) % x 
     d = gcd(y - x0, x) 
     if d != 1 and d != x: 
      return d 
     if y == x0: 
      return x 
     if i == k: 
      y = x0 
      k += k 

def PrimeFactorsListGenerator(n): 
    result = [] 
    if n <= 1: 
     return None 
    if MillerRabinPrimeCheck(n): 
     return [n] 
    p = n 
    while p >= n: 
     p = Pollard_rho(p, random.randint(1, n - 1)) 
    result.extend(PrimeFactorsListGenerator(p)) 
    result.extend(PrimeFactorsListGenerator(n // p)) 
    return result 

#PrimeFactorsListGenerator(400) 
#PrimeFactorsListGenerator(40000) 

追加の先端があります：あなたが使用して、すべての機能mod_mul（A、B、n）を記述する必要はありませんPythonの組み込みのPOW（A 、b、n）はトリックを行い、完全に最適化されます。