miller-rabin算法

meta分析

氯化钠晶体miller-rabin算法

新壮态>山西科教频道小郭跑腿米勒-拉宾素性检验（Miller Rabin算法），是一种素数判定法则，利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授Gary Lee Miller首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以列耶路撒冷希伯来大学的Michael O. Rabin教授作出修改，提出了不依赖于该假设的随机化算法。Miller-Rabin算法在基于Fermat定理的算法中是最优秀的，无论从误判概率还是从速度上看，它都优于其它 Fermat 类算法，例如： Fermat 算法、 Lehmann 算法、 Solovay- Strassen算法等。 Lucas 测试是Pomerance、Selfridge 和 Wagstaff 提出的一种基于Lucas序列的概率素数测试算法，该算法一轮消耗的时间大概相当于6轮Miller-Rabin测试。一轮Lucas 的误判概率为4/15，该算法经过一些改进,一轮的误判概率达到1/8。这种算法在误判概率和速度的权衡考虑上不如Miller-Rabin 算法。 Grantham-Frobenius 测试(QFT) 是 Grantham 提出的基于 Frobenius概率素数和Frobenius强概率素数理论的算法，给定一组参数(b,c)，误判概率可以被控制在1/7710以下。时间复杂度是(3+O(1))log2(n)( 以模n乘法为基本操作)，大概相当于3轮Miller-Rabin算法。这种算法理论比较艰深，目前只停留在理论研究阶段，还不适合现实应用。 Adams 和Shanks 提出了一种基于Perrin 序列的算法，他们算法的Q和I两种情况下

还没发现伪素数，没有考虑算法的速度，只是就误判概率来进行研究，他们的工作主要是侧重数学理论研究，算法目前还不适合现实应用

中国生物制品学杂志

本文发布于:2024-09-22 05:35:09，感谢您对本站的认可！

本文链接：https://www.17tex.com/xueshu/33219.html

上一篇：KAPPA分析说明【精编版】

下一篇：基于Fisher判别法的鸢尾花分类研究

标签：算法概率素数

留言与评论（共有 0 条评论）