使用试除法得到质因数的复杂度是\(O(\sqrt{n})\)，如果数字较大比如\(10^{18}\)就束手无策了。 在上一篇文章有写到Miller Rabin可以在\(O(klog^{2}{n})\)的复杂度下判断一个数字是不是素数，这次要介绍的Pollard Rho（普拉德柔）算法就是结合Miller Rabin的快速素性检验来进行的一个复杂度大约为\(O(n^{\frac{1}{4}})\)来 […]
最近评论
MartinHou 发布于 3 个月前（10月27日）
嫩爹 发布于 3 个月前（10月17日）
采集一直 发布于 4 个月前（09月27日）
采集一直 发布于 4 个月前（09月27日）
hesy 发布于 4 个月前（09月21日）