python质数python的程序里为什么2%2不为0

来源：蜘蛛抓取(WebSpider) 时间：2019-02-26 02:41 标签： 质数python

本文实例讲述了Python素数检测的方法分享给大家供大家参考。具体如下：

如果n是一个素数a是小于n的任意正整数，那么a的n次方与a模n同余

选择一个底数（例如2）对于大整数p，如果2^(p-1)与1不是模p同余数则p一定不是素数；否则，则p很可能是一个素数

也可以归纳为下面的算法 两个函数是一样的

有了模幂运算快速处理僦可以实现费马检测

费马测试当给出否定结论时是准确的，但是肯定结论有可能是错误的对于大整数的效率很高，并且误判率随着整數的增大而降低

Miller-Rabin检测是目前应用比较广泛的一种

这就是Miller-Rabin素性测试的方法不断地提取指数n-1中的因子2，把n-1表示成d*2^r（其中d是一个奇数）那么峩们需要计算的东西就变成了a的d*2^r次方除以n的余数。于是a^(d * 2^(r-1))要么等于1，要么等于n-1如果a^(d * 2^(r-1))等于1，定理继续适用于a^(d * 2^(r-2))这样不断开方开下去，直到對于某个i满足a^(d *

定理:若n是素数,a是小于n的正整数,则n对以a为基的Miller测试,结果为真.
Miller测试进行k次,将合数当成素数处理的错误概率最多不会超过4^(-k)

希望本文所述对大家的Python程序设计有所帮助

我要回帖

更多关于 质数python 的文章

 

随机推荐