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)를 작성할 필요가 없습니다 파이썬 내장 펑 (A , b, n)이 트릭을 수행하고 완전히 최적화됩니다.