判断一个数P是否为素数的一般方法:
方法1
:k从2开始,到n-1为止,判断P是否可以整除k
改进1
:k到sqrt(P)为止
改进2
:k从3开始且只考虑奇数
时间复杂度
:O(P)
一个更快的算法:Miller-Rabin算法
实现思路
:在2到P-1的范围内,随机选择一个数a,若a正好不满足
,就输出P不是质数;否则重复m次,若每次的a都满足上述公式,就输出P是质数。
时间复杂度分析
:m是一个不大的数,比如10;关键是计算
耗时。
利用到的定理和思想:
1.费马定理
:如果P是质数,一定有
因此,如果输出判断为不是质数,结果一定是对的。
反之则不一定成立,所以会出现不是质数却被判断为质数的情况。
2.定理:
如果P不是质数,则没有一个a或者至少在[2,P-1]中一半数的a,使得
不成立。
3.错误概率:
每次错误的概率不大于1/2,所以判定m次,错误概率不大于
。所以m越大的话错误概率就越小,最后是一个可接受的值,甚至可以忽略。
属于Monte-Carlo算法,牺牲了一定的正确率但是换来了时间上的高效。
python代码实现
import random
# 快速求幂取模
def quickPowMod(a,n,m):
re = 1
base = a % m
while(n>0):
tem = n&1
if (tem):
re = (re*base) % m
base = (base*base) % m
n >>= 1
return re
def Miler_Rabin(P):
# 循环次数m
m = 10
flag = 0
for i in range(0, m):
# a是2-P-1的随机数
a = random.randint(2, P-1)
# 直接求幂取余
# tem = pow(a, P-1)
# tem2 = tem % P
# 快速求幂取余
tem2 = quickPowMod(a,P-1,P)
if tem2 != 1:
flag = 1
break
if flag == 0:
print("{0} is prime".format(P))
elif flag == 1:
print("{0} is not prime".format(P))
else:
print("error")
if __name__ == '__main__':
while(1):
P = int(input("请输入一个数字:"))
Miler_Rabin(P)
数据测试(添加了两个测试函数)
import random
import time
# 快速求幂取模
def quickPowMod(a,n,m):
re = 1
base = a % m
while(n>0):
tem = n&1
if (tem):
re = (re*base) % m
base = (base*base) % m
n >>= 1
return re
def Miler_Rabin(P):
# 循环次数m
m = 10
flag = 0
for i in range(0, m):
# a是2-P-1的随机数
a = random.randint(2, P-1)
# 直接求幂取余
# tem = pow(a, P-1)
# tem2 = tem % P
# 快速求幂取余
tem2 = quickPowMod(a,P-1,P)
if tem2 != 1:
flag = 1
break
if flag == 0:
print("{0} is prime".format(P))
elif flag == 1:
print("{0} is not prime".format(P))
else:
print("error")
# 对素数进行判定,同时还能验证算法正确率
# prime,prime2中都是素数
def test1():
prime = [9998581,9999071,9999163,9999167,9999217,9999221,9999397,9999713,9999929,9999991]
prime2 = [111111111111229,111111111111233,111111111111389,111111111111443,111111111111527,519111111111683,719111111111683,919111111111553,919111111111679,919111111111681]
sumTime = 0
maxTime = 0
for P in prime2:
start = time.time()
Miler_Rabin(P)
end = time.time()
timeUse = end-start
if maxTime < timeUse:
maxTime = timeUse
sumTime = sumTime+(timeUse)
print("平均用时{0}s".format(sumTime/len(prime)))
print("最坏用时{0}s".format(maxTime))
# 对随机数进行判断
def test2():
sumTime = 0
maxTime = 0
for i in range(0,100):
P = random.randint(100000000000000000000000000000,999999999999999999999999999999)
start = time.time()
Miler_Rabin(P)
end = time.time()
timeUse = end-start
if maxTime < timeUse:
maxTime = timeUse
sumTime = sumTime+(timeUse)
print("平均用时{0}s".format(sumTime/100))
print("最坏用时{0}s".format(maxTime))
if __name__ == '__main__':
test1()
test2()
实验结果:
对10个9位素数判断的平均用时和最坏用时如下:
对100个随机的9位数进行素数判断,耗时情况如下:
对10个12位素数的判断平均用时和最坏用时如下:
对100个随机的12位数进行素数判断,耗时情况如下:
对100个随机的30位数进行素数判断,耗时情况如下:
结论
使用Miller-Rabin算法来判断素数的正确率非常高,这一点也可以通过提高判断次数m来做到。通过对实验数据的分析,可以看到对9、12、30位的数进行判断,最坏用时都是相近的(被判断的数中有素数),这是因为使用了快速求幂取余的方法,判断素数的过程都是m轮计算量相近的求幂取余运算。