我最近在 a paper 的并行化中偶然发现了 Pollard's Rho algorithm ，并且考虑到我的具体应用，除了我没有达到所需的数学水平这一事实之外，我想知道这种特殊的并行化方法是否对我的具体情况有所帮助。
我试图找到两个因子 - 半素数 - 一个非常大的数字。我的假设，基于我对论文的一点理解，这种并行化在具有许多较小因子的数字上运行良好，而不是在两个非常大的因子上。
这是真的？我应该使用这种并行化还是使用其他东西？我什至应该使用 Pollard 的 Rho，还是有更好的不同分解算法的并行化？
最佳答案
大整数因式分解的基本思想是使用多种方法，每种方法都有自己的优缺点。通常的计划是先用质数试除 1000 或 10000，然后是几百万 Pollard rho 步；这应该能让你得到大约十二位数的因数。到那时，需要进行一些测试:是素数还是完美数(有一些简单的测试用于这些性质)。如果您还没有计算出这个数字，您就知道这会很困难，因此您将需要重型工具。一个有用的下一步是 Pollard 的 p-1 方法，然后是其近亲椭圆曲线方法。过了一会儿，如果这不起作用，剩下的唯一方法是二次筛法或数场筛法，它们本质上是平行的。
您所要求的并行rho方法在今天还没有广泛使用。正如您所建议的，Pollard rho 更适合寻找小因素而不是大因素。对于半素数，最好在其中一个筛子上花费并行循环而不是在 Pollard rho 上。
我推荐 mersenneforum.org 上的保理论坛以获取更多信息。
关于java - Pollard-Rho 分解并行化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7540529/