Pollard的p−1算法：伯克利论文理解

Question

This paper 解释了 Pollard 的 p-1 分解算法。当找到的因子等于我们返回并更改 'a' 的输入时，我无法理解这种情况（基本上是上述论文中的第 2 页第 2 点）。

为什么我们返回并递增 'a'？
为什么我们不继续增加阶乘呢？是因为我们不断进入我们已经看到的同一个循环吗？

我可以使用相同的算法获得所有因子吗？比如 49000 = 2^3 * 5^3 * 7^2。目前我只有 7 和 7000。也许我可以递归地使用这个 get_factor() 函数，但我想知道基本情况。

def gcd(a, b):
if not b:
    return a
return gcd(b, a%b)

def get_factor(input):
    a = 2
    for factorial in range(2, input-1):
     '''we are not calculating factorial as anyway we need to find
        out the gcd with n so we do mod n and we also use previously
        calculate factorial'''
        a = a**factorial % input
        factor = gcd(a - 1, input)
        if factor == 1:
            continue
        elif factor == input:
            a += 1
        elif factor > 1:
            return factor

n = 10001077
p = get_factor(n)
q = n/p
print("factors of", n, "are", p, "and", q)

Answer 1

链接的论文不是对 Pollard 的 p − 1 算法的特别好的描述；大多数描述都讨论了使算法更加实用的平滑度边界。您可能想阅读 Prime Wiki 上的 this page。回答您的具体问题：

为什么递增a？因为原来的a不行。实际上，大多数实现都不会打扰；相反，尝试了一种不同的因式分解方法，例如椭圆曲线法。
为什么不增加阶乘？这就是平滑度边界发挥作用的地方。阅读 Mersenne Wiki 上的页面了解更多详情。
我可以得到所有因素吗？这个问题不适用于您链接的论文，该论文假设被分解的数字是一个恰好有两个因子的半素数。更一般的答案是 "maybe." 这是链接论文的步骤 3a 中发生的情况，选择新的 a 可能有效（或可能无效）。或者您可能想换一种不同的因式分解算法。

这是我的 p − 1 算法的简单版本，使用 x 而不是 a. while 循环计算链接论文的神奇 L（它是小于平滑度界限 b 的整数的最小公倍数)，这与链接论文的阶乘计算相同，但计算方式不同。

def pminus1(n, b, x=2):
    q = 0; pgen = primegen(); p = next(pgen)
    while p < b:
        x = pow(x, p**ilog(p,b), n)
        q, p = p, next(pgen)
    g = gcd(x-1, n)
    if 1 < g < n: return g
    return False

您可以在 http://ideone.com/eMPHtQ 上看到它的实际效果，它在链接论文中对 10001 进行因式分解，并找到一个相当惊人的 36 位因数 fibonacci(522)。掌握该算法后，您可能想继续学习该算法的两阶段版本。

Pollard的p−1算法：伯克利论文理解

Pollard’s p−1 algorithm: understanding of Berkeley paper

prime-factoring

factorization