大整数分解 浅析

这篇具有很好参考价值的文章主要介绍了大整数分解浅析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

大整数分解浅析

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

1.试除法

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

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

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

2.玄学法

玄学多好啊（

2.1 不靠谱的玄学法

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

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

2.2 稍微靠谱一点的做法

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

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

2.3 引入生日悖论

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

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

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

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

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

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

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

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

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

这有什么用途呢？比如 2.1 的随机算法，枚举第一次碰不到因子的概率为 $P_1$ ，第二次碰不到因子的概率为 $P_2$ ……总共碰不到因子的概率就是 $P_1P_2P_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)]

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

联想一下小学的追及问题。甲和乙文章来源地址https://www.toymoban.com/news/detail-409838.html

到了这里，关于大整数分解浅析的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！