求一个整数的所有素数因子的思路是什么？ 第1页

1. 一般的小数可以用简单筛法找出质数列表，然后一个个试。这种方法简单暴力，但是对几亿以下的数字可以很快。

2. 再大一点的数 就用Pollard的 算法，思路：

任取一个数 开始，不断计算 ，则如果 有质因数 ，那么 应该能更快地进入循环，可以用龟兔赛跑算法（图形状像 ，因此算法得名）试图找出这个循环点，一旦找到 ，立刻可以算 和 的最大公约数得到分解。有一定几率失败。

3. 更大的但在 以下的 可以用Lenstra椭圆曲线算法（ECM），思路：

挑选椭圆曲线 外加上面某一点 ，然后取一个较小的阶乘 ，反复用椭圆曲线加法算出 ，在重复计算加法中每一步都会计算和曲线切线斜率 同余的整数，即找出整数 使得 ，方法为找 和 的最大公约数，在这个过程中如果得出公约数大于1则分解成立，有一定几率失败。

4. 更大的 以下的 可以用二次筛（QS），思路

费尔马分解法试图把奇数 写成 的方法，这样立刻可得因数分解 ，二次筛就是一种可以高效找到此类数字的方法，试图测试多个介于 和 之间的数 ，如果 正好是完全平方那就成了，不然找到几个不同的 ，如果乘积正好是完全平方数，那么 满足条件。

5. 再往上只能用普通数域筛选法（GNFS），这个就很复杂了，思路

也是用费尔马分解法，只是比二次筛更高效，核心定理：

取系数为整数的 次多项式 有复根 ，并存在不是 倍数的整数 ，使得 为 倍数，将所有次数不超过 的整系数多项式代入后的值定义为一个“环”（因为任何两个这样形式的数的和或积依然是这样形式的数），那么必然存在一个将这个环里的复数映射到不是 倍数的整数上的函数 满足：

i -

ii -

iii -

iv -

已知这个定理后，如果找到整数对 使得复数 ，整数 ，以及 的映像 ，则很容易根据i-iv得到 ，有2/3机会能由此找到 的一个约数。

2009年，232位的RSA-768数通过上百台计算机耗时两年成功分解，用的就是高度优化后的GNFS。