我的 PollardP1_rho 代码有问题，但我不知道如何修复

Question

我尝试使用 MillerRabin + PollardP1_rho 方法将整数分解为 Python3 中的素数，以尽可能降低时间复杂度 could.But 它未能通过一些测试，我知道在哪里问题was.But我是算法初学者，我不知道如何解决it.So我会把所有相关代码放在这里。

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.How我可以修复吗那个？

Answer 1

我自己解决了。代码中有 1 个错误。我不应该在函数外使用 var 'result' 作为全局变量，我应该在函数中定义并使用 result.extend() 来确保整个递归的可用性 process.So 我重写了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) 可以解决问题，并且已经过全面优化。

我的 PollardP1_rho 代码有问题，但我不知道如何修复

Something wrong with my PollardP1_rho code but I don't know how to fix it

algorithm

python-3.x

prime-factoring