prime-factoring - Pollard 的 p−1 算法 : understanding of Berkeley paper

Question

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

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

3. 我可以使用相同的算法获得所有因子吗？如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 算法的特别好的描述；大多数描述都讨论了使算法更加实用的平滑范围。您可能想阅读this page在 Prime 维基。回答您的具体问题:

1. 为什么要增加a？因为原来的a不起作用。实际上，大多数实现都不会造成麻烦；相反，尝试了不同的因式分解方法，例如椭圆曲线法。

2. 为什么不增加阶乘？这就是平滑度界限发挥作用的地方。请阅读 Mersenne Wiki 页面了解更多详细信息。

3. 我可以获得所有因子吗？这个问题不适用于您链接的论文，该论文假设被分解的数字是具有两个因子的半素数。更普遍的答案是“也许”。这就是链接论文的步骤 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 位斐波那契 (522) 因式。一旦掌握了该算法，您可能想继续学习该算法的两阶段版本。