Pollard-Rho分解并行化

Question

Pollard-Rho分解并行化

javaparallel-processingfactorization

7

我最近偶然看到了有关一篇论文，介绍了Pollard's Rho算法的并行化，鉴于我的具体应用场景以及我尚未达到所需的数学水平，我想知道这种特定的并行化方法是否对我的情况有帮助。

我正在试图找到一个非常大的数字的两个因子——半素数。根据我所能理解的论文的内容，我的假设是这种并行化方法对于具有许多较小因子的数字效果很好，而不是对于两个非常大的因子。

这是真的吗？我该使用这种并行化还是使用其他方法？我甚至应该使用Pollard's Rho算法吗，还是有更好的并行化因数分解算法？

- skeggse

你的"非常大的数"有多大？有多少位小数？ - user448810

从2^16（5个十进制数字）到2^8192（2467个十进制数字）不等。我猜我可能会使用许多不同的算法，取决于数字的大小，但我不确定。我知道Pollard-rho是一种专门的算法，但我没有找到其他算法的并行化，所以我有点困难。 - skeggse

请注意，尽管2^8192是理论上的上限，但我不指望能够分解任何那么大的数。 - skeggse

2个回答

5

在分解大整数方面的基本思想是使用多种方法，每种方法都有其优点和缺点。通常的做法是从1000或10000个质数开始试除法，然后进行几百万次的Pollard rho步骤；这应该可以获得约12位数字的因子。此时需要进行一些测试：该数字是否为素数幂或完全幂（这些属性有简单的测试方法）。如果你仍然没有分解该数字，那么你就知道它很难，所以你需要重型工具。一个有用的下一步是使用Pollard的p-1方法，然后是它的近亲椭圆曲线方法。一段时间后，如果这些方法都不起作用，剩下的方法只有二次筛和数域筛，它们本质上是并行的。

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

我建议在mersenneforum.org上参考更多信息。

- user448810

有一个小问题。你推荐的方法相当复杂，我似乎找不到任何算法规范或伪代码。鉴于我的数学背景有些有限，我不能只是去源头尝试自己编写代码。 - skeggse

2

你不需要自己去做。去mersenneforum.org的分解论坛。他们有指向gmp-ecm、msieve和其他免费且最好的分解程序的指针。如果你必须自己做，我的博客http://programmingpraxis.com有大多数这些分解算法的描述和源代码，尽管还没有两个筛子。 - user448810

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- schnaader · Accepted Answer

维基百科文章提供了两个具体的例子：

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毫秒，不同的方法15-17毫秒），那么考虑在单独的线程中运行这两个算法以进行“分解比赛”。

如果您还没有实际实现该算法，请参考Python实现。