开坑时间：2019.10.18周五

学习原因及其他

没什么原因，就是想学。

有可能是因为今天在机房，csl到处问Pollard's rho怎么写，我随即发现自己不会，决定去学习。

2019-10-18

入门

入门，初步学习：xyx的博客

初步了解Pollard's rho的过程。认识到它的本质以及大致过程。

• 要分解\(N\)

• 伪随机生成数列\(A=\{a_1,a_2,a_3,...\}\)，每一项由前一项用固定方式推得。常用方式为\(a_i=f(a_{i-1})=(a_{i-1}^2+C)mod\,N\)其中\(C\)为一不变常数。

• 每次查看\(gcd(a_{2i}-a_i,N)\)，若不为1，说明此时找到了一个约数\(gcd(a_{2i}-a_i,N)\)。若此时\(gcd\neq N\)，说明我们确实找到了一个非平凡约数。但如果\(gcd=N\)，就没有找下去的必要了。

• 这实际上是找到了循环节。即，如果最终我们有一个因数\(P\)，那么\(a_i\,mod\,P\)实际是有循环节的。当\(gcd\neq 1\)是，我们发现\(a_{2i}\)与\(a_i\)实际上就到了循环节上一个相同的位置。

• 如果此时\(gcd=N\)，就说明\(a_{2i}\)与\(a_i\)也到了\(mod\,N\)循环节上的同一位置。这就说明不行了，我们要换一个\(C\)。

• 我们假设要经过\(Q\)步进入循环节，循环节长\(R\)步，那么\(a_{2i}\)与\(a_{i}\)要对应上循环节同一点，所需时间是\(O(Q+R)\)的。

• 所以这个算法的关键就是期望多少次，\(a_i\,mod\,P\)会冲突。生日悖论告诉我们是\(O(\sqrt{P})\)即\(O(N^{\frac{1}{4}})\)

生日悖论

进一步学习：关于生日悖论

发现一篇文章：一篇文章

这篇文章关于生日悖论讲了一些。可以帮助理解为什么会在很快的时间内成功，但是没有证明期望。

关于名字

发现了为什么要叫Pollard's rho：因为循环节这东西长得很像\(\rho\)

关于\(a_{2i}-a_i\)

这东西实际上就是Floyd的找环算法。