linux - linux中factor命令背后的算法是什么？

Question

该factor命令打印指定整数 NUMBER 的质因数。

当我尝试它时

factor 12345678912345678912

即使对于如此大的数字，它也会在工厂内产生。

它使用的是哪种算法？

Answer 1

Gnu coreutils 手册告知正在使用Pollard 的 rho 算法。

http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html

Answer 2

以下是 GNU 因子的一个版本的源代码示例：

http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c

它包括试验师和波拉德 rho 的例程。快速扫描在我看来，好像它使用试除法来查找一些小因素（最多约lg(n)^2，在这种情况下约为 4000），然后是 Pollard，如果剩下的可能不是素数。在这种情况下，205432623008947如果我对 4000 的看法是正确的，即35129 * 5847949643.

在您的示例中，第二大素数因子是，最大素数35129的平方根大约是76471。所以单试分裂会很快，因为它只需要尝试大约 25,000 名候选人。

Answer 3

从源代码：

算法：

1. 使用一个小的素数表执行试除法，但没有硬件除法，因为素数表存储逆模词基。（此代码的 GMP 变体不使用预先计算的逆，而是依靠 GMP 进行快速可分性测试。）
2. 使用 Miller-Rabin 检测复合材料和 Lucas 检测素数来检查任何非因式分解部分的性质。
3. 使用 Pollard-Brent rho 算法分解任何剩余的复合零件，或者如果 USE_SQUFOF 定义为 1，请先尝试。使用 Miller-Rabin 和 Lucas 再次检查已发现因素的状态。

我们更喜欢在除法中使用 Hensel 范数，而不是更熟悉的 Euclidian 范数，因为前者会导致更快的代码。在 Pollard-Brent rho 代码和主要测试代码中，我们使用 Montgomery 将所有 n 残基乘以词基的技巧，允许廉价的 Hensel 约简 mod n。

GMP 代码使用的算法可能要慢得多；例如，在大约 2017 年的 Intel Xeon Silver 4116 上，使用双字算法分解 2^{127}-3 大约需要 50 毫秒，但使用 GMP 代码大约需要 750 毫秒。

总的来说，factor速度快得令人愉悦。但是，这不是魔术。如果你选择病态难以分解的数字，它会显着减慢。

RSA 加密的底层安全性基于分解 2 个大的互质数的难度。所以让我们看看我们可以factor用大的互质推多难。能够分解的最大数factor是 2 ¹²⁷ -1（可能在内部用 int64_t 表示），它恰好是素数：

$ factor $(bc <<< 2^127)
factor: ‘170141183460469231731687303715884105728’ is too large
$ factor $(bc <<< 2^127-1)
170141183460469231731687303715884105727: 170141183460469231731687303715884105727
$ factor $(bc <<< 2^127-2)
170141183460469231731687303715884105726: 2 3 3 3 7 7 19 43 73 127 337 5419 92737 649657 77158673929
$ 

2 ¹²⁷ -1 和 2 ¹²⁷ -2 几乎立即分解；很快发现2 ¹²⁷ -1 是素数，而 2 ¹²⁷ -2 的因数相对较小。

更难的东西呢？^{2 60}数量级的 2 个因子的乘积将接近可以处理的因子的更高阶。那么接下来的 2 个高于 2 ⁶⁰的素数呢？

$ primes $(bc <<< 2^60) | head -2
1152921504606847009
1152921504606847067
$ bc <<< 1152921504606847009*1152921504606847067
1329227995784916015866073631529372603
$ time factor 1329227995784916015866073631529372603
1329227995784916015866073631529372603: 1152921504606847009 1152921504606847067

real    0m30.628s
user    0m30.578s
sys 0m0.004s
$ 

因此，随着互质因子位数的增加，因式分解时间增加得更快。