java - Pollard-Rho 分解并行化

Question

我最近偶然发现了一篇关于Pollard 的 Rho 算法并行化的论文，鉴于我的具体应用，除了我没有达到所需的数学水平之外，我想知道这种特殊的并行化方法是否有助于我的具体情况.

我试图找出两个因数——半素数——非常大。根据我对这篇论文的了解，我的假设是，这种并行化在具有许多较小因子的数字上运行良好，而不是在两个非常大的因子上。

这是真的？我应该使用这种并行化还是使用其他东西？我什至应该使用 Pollard 的 Rho，还是对不同的分解算法有更好的并行化？

Answer 1

维基百科文章陈述了两个具体的例子：

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）的情况 - 在这种情况下，考虑在单独的线程中运行 2 个算法来做一场“因式分解竞赛”。

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

Answer 2

分解大整数的基本思想是使用多种方法，每种方法都有自己的优缺点。通常的计划是先试除以素数到 1000 或 10000，然后是几百万 Pollard rho 步长；这应该让你的因素达到大约十二位数。在这一点上，需要进行一些测试：数字是质幂还是完美幂（这些属性有简单的测试）。如果你还没有考虑到这个数字，你知道这会很困难，所以你需要重型工具。一个有用的下一步是 Pollard 的 p-1 方法，然后是它的近亲椭圆曲线方法。过了一会儿，如果这不起作用，剩下的唯一方法是二次筛或数域筛，它们本质上是平行的。

您询问的并行 rho 方法今天并未广泛使用。正如您所建议的，Pollard rho 更适合寻找小因素而不是大因素。对于半素数，最好在其中一个筛子上花费并行循环而不是在 Pollard rho 上。

我推荐 mersenneforum.org 上的保理论坛以获取更多信息。