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 上的保理论坛以获取更多信息。