Python中的Pollard's Rho启发式方法

Question

这是一个自己写的函数，但它有一些问题。我猜可能是在循环里搞错了。它的结果不太稳定——我知道这就是“启发式”的意思，但我觉得对于，比如说 n==57 的情况，这应该没问题。

def Rho_Heuristic(n):
    import random
    cum_d = 1
    x = random.randint(0, n-1)
    y = x
    k = 2
    i = 1
    while not(cum_d == n):
      i = i + 1
        x = (x*x-1)%n
        d = GCD(y-x, n)
       if (not(d == 1) and not(d == n)):
           print d
           cum_d = (d * cum_d)
       if i==k:
           y = x
           k = 2*k;

Answer 1

如果你想要对任何给定的输入都能得到确定的输出，可以在你启动程序的时候调用：

random.seed(0) 

这段代码。

Answer 2

Pollard的Rhos算法是一种启发式方法。它返回的因子总是正确的，只是很少会返回所有的因子。如果你需要找到具有特定特征的因子，PRH是个不错的选择。当我实现一个RSA攻击的概念验证时，我只是不断运行这个算法，直到找到合适的质数。