大整数分解 浅析

解决：质因数分解大整数 $n$ 。$1\le n\le 10^{18}$ 。

1.试除法

枚举 $[2,\sqrt{n}]$ 的所有质数，判断是否整除。除完之后只剩一个 质数 或者 $1$ 了。时间复杂度 $O(\frac{\sqrt{n}}{\ln n})$ 。

这是一个笨方法，但是它告诉我们一些性质：

• 对于 $n$ ，最小的质因子不会大于 $\sqrt{n}$ 。（质数除外）

2.玄学法

玄学多好啊（

2.1 不靠谱的玄学法

先判断 $n$ 是不是质数，然后在 $[2,\sqrt{n}]$ 里面随机选取一个整数 $x$，判断是不是 $\gcd (n,x)\ne 1$，是的话把 $n/x$ 和 $x$ 递归下去。

时间复杂度 $O(T{\log }^{2}n)$ 到 $O(T\sqrt{n}\log n)$ ，无法保障效率。

2.2 稍微靠谱一点的做法

假设 $n$ 的一个最小的素因子为 $p$ ，那么随机选择两个数 $(i,j)$ 使得 $i\equiv j(\mathrm{m}\mathrm{o}\mathrm{d}p)$ 。则 $p|\gcd (i,j)$ ，则 $\gcd (|i-j|,n)\ne 1$ 。

但是，随机枚举两个数判断模 $p$ 意义相等，时间复杂度不允许，怎么办？

2.3 引入生日悖论

$50$ 多个人的班里面至少有 $97\%$ 的概率能有两个人同一天生日。

为什么呢？因为乘法原理。

一开始，一个人的时候，第一个人能选 $365$ 天生日；

两个人的时候，因为不能和第一个人重复，所以第二个人能选 $364$ 天生日；概率就是 $\frac{364}{365}$ 。

第三个人，不能跟前两个重复，所以第三个人只能选 $363$ 天生日，到了他时候，不重复的概率就是 $\frac{363}{365}$ 。

把不重复的概率乘起来，则前三个人不重复生日的概率是 $\frac{365\times 364\times 363}{365^3}$ 。

以此类推，前 $n$ 个人不重复生日的概率就是 $\frac{n!}{365^n(365-n+1)!}$ ，越乘越小。

所以，有 $23$ 个人就能有 $50\%$ 的概率能有两个人同一天生日。

生日悖论告诉我们另外一个性质：$n$ 个数中大约选 $\sqrt{n}$ 次就能达到 $50\%$ 的概率。

这有什么用途呢？比如 2.1 的随机算法，枚举第一次碰不到因子的概率为 $P_1$ ，第二次碰不到因子的概率为 $P_2$ ……总共碰不到因子的概率就是 $P_1{P}_2{P}_3...$ 。可知碰了很多次之后，这个概率大大下降。

但是效率和正确性堪忧。

2.4 pollard_rho

2.2 的改进。

因为一个个随机选太玄学，我们就更玄学地生成随机数列，判断相邻两个数是否符合条件。我们只会存储两个数。

有章法的生成方法：上一个数为 $x$ ，那么下一个数就是 $(x^2+a)\%n$ 。

回到 2.2 的证明，假设 $p$ 为 $n$ 的最小质因子，那么

但是，这个生成方法有问题，到了最后的时候会形成一个环，出不去了。如图：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Cd29sehM-1657701752031)(C:\Users\Admin\AppData\Roaming\Typora\typora-user-images\image-20220514102638547.png)]

那么我们怎么出这个圈呢？

出不去了。如图：[外链图片转存中…(img-Cd29sehM-1657701752031)]

那么我们怎么出这个圈呢？

联想一下小学的追及问题。甲和乙