Что-то не так с моим кодом PollardP1_rho, но я не знаю, как его исправить

Question

Я попытался использовать метод MillerRabin + PollardP1_rho, чтобы разделить целое число на простые числа в Python3 для уменьшения сложности времени, насколько я мог. Но это не сработало некоторые тесты , Я знал, где проблема. Но я тиро в алгоритме, я не знал, как его исправить. Поэтому я буду размещать здесь все относительные коды.

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) 

Когда я попытался проверить это:

PrimeFactorsListGenerator(4) 

Это не остановило и петельные это:

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

Я уже протестировали функции до того PollardP1_rho, и они работают нормально, поэтому я знаю, что функция PollardP1_rho не может правильно обрабатывать номер 4, а также номер 5. Как я могу это исправить?

Answer 1

Я сам решил. В коде есть 1 ошибка. Я не должен использовать результат var 'вне функции в качестве глобального var, я должен определить в функции и использовать result.extend(), чтобы обеспечить доступность всего рекурсивного процесса. Поэтому я переписал PollardP1_rho (n, c) и PrimeFactorsListGenerator (п):

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 (а, б, п) на всех, используя Python встроенный мощн (а , b, n) выполнит трюк и полностью оптимизируется.