求一个整数的所有素数因子的思路是什么？
1. 一般的小数可以用简单筛法找出质数列表，然后一个个试。这种方法简单暴力，但是对几亿以下的数字可以很快。

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

任取一个数 $$x_0$$ 开始，不断计算 $$x_k=(x_{k-1}^2+1) \text{ mod } n$$ ，则如果 $$n$$ 有质因数$$p$$ ，那么 $$x_k \text{ mod } p$$ 应该能更快地进入循环，可以用龟兔赛跑算法（图形状像 $$\rho$$，因此算法得名）试图找出这个循环点，一旦找到 $$x_k\equiv x_l \text{ mod } p$$ ，立刻可以算 $$x_k-x_l$$ 和$$n$$ 的最大公约数得到分解。有一定几率失败。

3\. 更大的但在 $$10^{25}$$ 以下的 $$n$$ 可以用Lenstra椭圆曲线算法（ECM），思路：

挑选椭圆曲线 $$y^2=(x^3+ax+b) \text{ mod } n$$ 外加上面某一点 $$P$$ ，然后取一个较小的阶乘$$n!$$，反复用椭圆曲线加法算出 $$2!P, 3!P, \cdots, n!P$$ ，在重复计算加法中每一步都会计算和曲线切线斜率 $$x/y$$同余的整数，即找出整数 $$z$$ 使得$$yz\equiv x \text{ mod } n$$ ，方法为找 $$y$$ 和 $$n$$的最大公约数，在这个过程中如果得出公约数大于1则分解成立，有一定几率失败。

4\. 更大的 $$10^{100}$$ 以下的 $$n$$ 可以用二次筛（QS），思路

费尔马分解法试图把奇数 $$n$$ 写成 $$n=a^2-b^2$$ 的方法，这样立刻可得因数分解 $$(a+b)(a-b)$$，二次筛就是一种可以高效找到此类数字的方法，试图测试多个介于 $$\sqrt n$$ 和 $$n-1$$ 之间的数 $$a$$ ，如果 $$a^2\text{ mod } n$$ 正好是完全平方那就成了，不然找到几个不同的 $$a_i^2 \text{ mod } n$$，如果乘积正好是完全平方数，那么 $$a=\prod_i a_i \text{ mod } n$$ 满足条件。

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

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

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

i - $$\phi(ab)=\phi(a)\phi(b)$$

ii - $$\phi(a+b)=\phi(a)+\phi(b)$$

iii - $$\phi(1)\equiv1 \text{ mod } n$$

iv - $$\phi(\theta) \equiv m \text{ mod } n$$

已知这个定理后，如果找到整数对 $$(a_i,b_i)$$ 使得复数 $$\beta = \prod_i (a_i+b_i\theta)$$ ，整数 $$y= \prod_i (a_i+b_im)$$ ，以及 $$\beta$$ 的映像 $$x=\phi(\beta)$$ ，则很容易根据i-iv得到$$x^2\equiv y^2 \text{ mod } n$$ ，有2/3机会能由此找到 $$n $$ 的一个约数。

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