问Pollard-Rho分解并行化

EN

分解大整数的基本思想是使用各种方法，每种方法都有自己的优缺点。通常的计划是先用质数除以1,000或10000，然后是几百万步Pollard rho步；这应该会让你的因数达到大约12位数。在这一点上，有几个测试是按顺序进行的:数字是质数幂还是完美幂(对这些属性有一些简单的测试)。如果您还没有将数字分解，那么您知道这将是困难的，因此您将需要重型工具。下一步有用的是Pollard的p-1方法，然后是它的近亲椭圆曲线方法。一段时间后，如果这不起作用，剩下的方法就是二次筛选或数字字段筛选，它们本质上是并行的。

您所询问的并行rho方法目前并未得到广泛使用。正如您所建议的，Pollard rho更适合发现小因素而不是大因素。对于半质数，最好在其中一个筛子上花费并行周期，而不是在Pollard rho上。

我推荐在mersenneforum.org上的保理论坛了解更多信息。

维基百科的文章列举了两个具体的例子：

Number                Original code      Brent's modification
18446744073709551617  26 ms              5 ms
10023859281455311421  109 ms             31 ms

首先，在你的程序中运行这两个程序，看看你的时间。如果它们类似于这样(“硬”数字计算的时间长4-6倍)，问问你自己是否能接受。或者更好的是，使用其他算法，如简单的经典“蛮力”分解，并查看它们给出的时间。我猜他们可能有一个接近于1的硬-容易因子，但绝对时间更差，所以这是一个简单的权衡。

附注:当然，并行化在这里是可行的，我猜你知道这一点，但我认为强调这一点很重要。此外，对于Pollard-rho计时之间存在另一种方法(例如Pollard-Rho 5-31 ms，不同的方法15-17 ms)的情况也会有所帮助-在这种情况下，考虑在单独的线程中运行两种算法来进行“因式分解竞赛”。

如果您还没有该算法的实际实现，这里有Python implementations。