先写一下Miller Rabin（具体介绍见老板的PPT）
对于该算法，先要知道二次探测定理。这个比较简单，看PPT即可
但还是要解释一个东西。PPT里面在举例子的时候，用\(2^{340}\)为例子，并说明\(2^{170}\)%\(341\)的结果只能是1或者340，这与二次探测定理的\(x\)要小于\(p\)不矛盾，因为PPT说的是\(2^{170}\)%\(341\)，利用模的运算法则即可
对于PPT接下来的操作步骤，当结果是1的时候，我们继续就更能增加\(n\)是质数的可能性；如果结果某一次为\(n-1\)，就没办法继续用二次探测定理了，所以不得已截止。此时就可以采用多次进行Miller Rabin测试来增加这个算法的正确性。
对于Pollard Rho算法，建议看一下这一篇博客
下面对这篇博客的一些东西进行解释
首先那个判圈算法的代码没有错误，可以手动模拟一下t和r的样子，只不过代码中的\(t-r\)不再是文字描述中说的随机数列相邻两项依次相减罢了，而是中间隔了很多个相减
路径倍增常熟优化那里可以去看OIwiki关于此算法的解析，说得更清楚
但是对于OIwiki的文章，也有一些需要解释的
那个乘法累计的操作就是判断在数列迭代的过程中，是否会存在一个gcd是大于1的，如果存在那么累乘结果的gcd也会大于1，如果不存在那么累乘结果的gcd也是1，这样就可以节省更多的时间
标签：gcd,Miller,Pollard,算法,Rho,PPT,Rabin From： https://www.cnblogs.com/dingxingdi/p/17675851.html