首先,强烈推荐阅读这篇文章.(看懂了就不用来了)
Miller-Robin 算法包括两个部分,一个是费马测试,还有一个就是二次探测.这两个东西听上去非常的玄学(的确也是),我来讲清楚,并附上代码.我们现在要进行测试的数是\(p\).
之后,我们可以通过调整\(k\)的值来进行测试,用的就是二次探查和费马测试.我们来用代码具体讨论如何进行这些测试:
这个算法也是一个非常毒瘤,随机化的玄学算法.一般的质因数分解算法是试除法,它的时间复杂度为\(O(\sqrt{n})\).Pollard-Rho 这个算法用随机化用更小的时间复杂度解决分解问题.Crazydave 博客上有一个非常优秀的讲稿(by BigBallon),大家可以去看一看.
这个算法的基础其实是一种玄学算法:随机枚举质因数.对,没错,就是瞎××取随机数来进行试除,也叫作"自我良好算法".这个算法主要是通过枚举因子进行试除.恩,这个算法的复杂度\(O(上天)\).
那么如何才能优化这个看上去无法优化的算法呢?玄学算法当然需要玄学优化,这里给大家介绍一个玄学定理,以便加速.
是的,下面我来描述这个理论.