Pollard的p-1算法理解berkley纸

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

为什么我们回去增加'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)

来源

2016-02-09 noman pouigt

链接的纸张不波拉德的p − 1算法的一个特别良好的描述;大多数描述都讨论了使算法更加实用的平滑边界。您可能会喜欢在Mersenne Wiki上阅读this page。为了回答您的具体问题：

为什么增量一个？因为原始的a不起作用。在实践中，大多数实现不打扰;相反，尝试使用不同的分解方法，例如椭圆曲线方法。
为什么不增加阶乘？这是顺畅界限起作用的地方。阅读Mersenne Wiki的页面了解更多详情。
我可以得到所有因素吗？这个问题不适用于你链接的论文，它假设这个数字是一个具有两个因素的半素数。更一般的答案是“也许”。这是在链接文件的步骤3a处发生的事情，并且选择新的a可能工作（或者可能不工作）。或者你可能想要转向不同的分解算法。

这里是我的p − 1算法的简单版本，使用的X代替一个。循环计算链接纸的神奇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在链接的文件，以及发现的fibonacci(522)一个颇为壮观的36位数字的因素。一旦你掌握了这个算法，你可能想转向算法的两阶段版本。

来源

2016-02-09 16:27:20 user448810

您在答案中链接的链接不谈论平滑度。你可能会添加一些关于'L'计算方法的描述，并添加一些关于平滑边界的链接。我会在阅读完这些答案后标记这个答案。 –

“不到一个界限B1”是平滑的概念。我将L计算为小于界限的最小公倍数。您的链接首先将L作为_p_ - 1的倍数，这是未详细说明的。稍后，您的链接将L作为所有小于R的数字的乘积，这是过度规定的。 – user448810

B1未正确选择会失败此算法？在这种情况下，应该使用步骤2。我认为你正在计算素数并将其提高到某种程度（根据链接的url），以便它小于界限值，并查看输入数字的该数字的gcd是否大于1. –

Pollard的p-1算法理解berkley纸

回答

相关问题