大整数分解 浅析

解决质因数分解大整数 $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)]

那么我们怎么出这个圈呢

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