7.22日算法日记

2021/7/22 22:06:46

编程Tag： 算法随机数素数复杂度 GCD 日记 Pollard 7.22

本文主要是介绍7.22日算法日记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

引言

我发现如果先自学一遍，然后再写的话记录一个知识点要花费两倍的时间，考虑到中间的损耗，实际要做出一个根据自己理解的文章至少要两天，因此我在想不如和学图形学时一样将日记当作笔记，边学边记，认为简单的就大概记录一下即可。以前笔记记得就很简略，不知为何现在写的却很多（自我感受），发扬一下古风吧。

内容

先记录今天的内容。当然，今天还是要把之前的补一下，FFT与笛卡尔树。

然后在写的时候我发现：FFT和PR有一定的思维共同性，恰好放在一起恐怕也是上天的选择（之类的

Pollard-Rho算法

是一种能快速找到大整数非1与自身的算法。

先把费马小定理放这里：

对于素数p，若a不是p的倍数，有 $a^{p-1}\equiv 1\qquad(mod \quad p)$

不证，有兴趣自己查阅相关资料。满足费马小定理的合数称为费马伪素数。

由此得到费马素性检验方法：

1、随机生成检验子

2、快速幂检测是否符合费马小定理

3、返回结论（时间复杂度为O（klongn）

然而这种方法在int32内尚可接受，但到了int64，误差增加（由于指数原因，而检验方法为线性

因此得出改进算法：米勒-拉宾素性检验

---

我们发现一个规律：

任何一个素数p，都可以将 $2^{p-1}$ 表示为 $2^{2^{r}d}$ 的形式，即使是1和2，也能用d来进行控制。

因此，我们考虑当p为素数时， $2^{d},2^{2d},2^{2^{2}d}...$ 这些数的性质。

考虑到 $2^{2^{r}d}$ 本身与1同余，1与任何数之间都互质且为质数，根据二次剩余的欧拉准则：

当p为奇素数且ap互质时，由费马小定理得到 $a^{p-1}\equiv 1\qquad(mod \quad p)$ ，记q=2p+1，得：

$a^{2q}\equiv1(mod \quad p)$ ，易得 $a^{q}\equiv\pm 1(mod \quad p)$ ，也即： $a^{\frac{p-1}{2}}\equiv\pm1(mod \quad p)$ 。

因此知：从现态向前，必满足 $2^{2^{r}d}\equiv1(mod \quad p)$ 直到存在某个r使得其与-1同余或r为0为止。

反向得知：如果满足此条件，则大概率为素数。也就是在费马素性检验中加上了向前验证的部分，根据概率学，这大大提高了精准度（虽然依旧是线性的优化），但我们可以将精确度提高到int64。

Jim Sinclair发现一组int64内绝不出错的检验数字：{2, 325, 9375, 28178, 450775, 9780504, 1795265022}，用此做a可保证正确性。（复杂度为O(klog n)

PR算法推理：

OK，我们速成了一下基础知识，引入上述内容的目的在于令大zi家ji对素数有个大致的认识，接下来来继续推PR算法吧。

一般来说，想要找到第一个可除因子，最简单的就是遍历，最多判断一下是否为质数，复杂度最多为 $O(\sqrt{n})$ ，不提。

另一种被提到的算法（不是去查阅一般不会用的）就是生成随机数去作为除子，emm，复杂度为 O(n) ，不吐槽了。

但随机算法可以通过最大公约数（gcd）算法，也就是用gcd来寻找因子的方法将最差复杂度变为 $O(\sqrt{n}logn)$ ，尽管这依旧比第一个算法复杂，我们可以继续想办法。

我们思考n的情况，n在最糟的情况下应该为某个质数p的平方，也就是说在[1, n]的范围内，只有这个p一个因子，然后在取gcd时，x取0到p-1，从p到(p-1)p都有gcd(xp，n)=p>1的情况，这个数据当然有 $\sqrt{n}$ 个，这就是他的来源。

---

根据生日悖论，如在[1, N]范围内生成随机数，则证明得遇到第一个重复的数字前的期望为 $\sqrt{\frac{\pi N}{2}}$ 个数（基础不牢的证明一定要看看，里面有很多常用基础知识。

那末，如果在[1, n-1]间不断生成随机数，也就是说在大概 $\sqrt{p}=n^{\frac{1}{4}}$ 个数（p同上)时有模p相同的数，他们的差d就能被p整除，所以这个d一定有n的系数，gcd（d，n）>1。

我思考了一下，这似乎很厉害，但没什么意义，因为不知道到底是哪两个数一样，如果要去寻找相关数据，则要至少花费或 $\sqrt{n}$ 的时间来进行寻找，而且不一定能找到，也就是说每次都要加入后进行一次比对。

---

虽然不清楚怎么找到的这个公式，但Pollard用了一种随机数生成算法：

$f(x)=(x^2+c)\quad mod\quad N$

每次取：

x, f(x), f(f(x))

依次类推，作为随机值。

而由于生日悖论，迟早会有一个值与之前的值相同，算法又依赖于前面得到的值，所以算法迟早会进入一个循环。因此被称为ρ（rho）算法。判环我们都知道用Floyd算法即可（快慢）。

而Pollard要求：如果在出现环之后还没有找到答案，就换个c重新生成随机数。

也就是 $gcd(|t-r|, N)>1 \quad t=f(t),r=f(f(r))$ 。

这里我觉得就是玄幻，本质还是生成了个随机数进行运算，和第二种方法除了t-r之外没有任何区别，但是就是能大大加快速度。我不是很理解，因此我做出了一个假设，那就是：

分布问题

我们发现这其实是个统计问题（突然想到zkw的统计的力量），原来是个均匀分布生成的随机数据，我们可以假装[1, n-1]范围内都是1/n这样，然后互相相减后取模，就变成了...很遗憾，是一个极为离散的随机分布，但至少我们知道他不是一个均匀分布。因此我认为此法存在可行可能。

经过验证，在1e16范围内是可行的。而在4处需要特判，可以动手试试为什么。

参考：

算法学习笔记(55): Pollard-Rho算法 - 知乎 (zhihu.com)

Pollard Rho算法浅谈 - 会虎GreyTiger - 博客园 (cnblogs.com)

FFT

之前已经学过了，所以会说的比较简略，大家想学的话一定要动手跟着一步步证明，有一些比较好的参考资料，分享/记录一下。

关于离散傅里叶变换在卷积加速中的应用与优化的相关介绍。

可爱的例题

暂停

只是认为需要个分割，接下来的部分另外发一篇。

这篇关于7.22日算法日记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

7.22日算法日记

引言

内容

Pollard-Rho算法

FFT

暂停

相关编程文章