Python:Fermat素性检测

算法背景与原理:

1、Fermat 小定理:给定素数 p,a∈Z,则有 a^(p-1)%p=1
2、Fermat 素性检测算法:奇整数 m,若任取一整数 2<=a<=m-2,gcd(a,m)=1,使得 a^(m-1)(mod m)=1,则 m 至少有 1/2 的概率为素数

算法步骤:

1、从键盘输入待检测的大整数 m
2、给出安全参数 k
3、随机选取整数 a,满足 a∈[2,m-2]
4、计算 g=gcd(a,m),如果 g=1 进行下一步,否则不是素数,跳出
5、计算 r=a^(m-1)(mod m),如果 r=1 则 m 可能是素数,否则不是素数,跳出
6、重复上述过程 k 次,如果每次判定 m 都可能是素数,那么 m 是素数的概率是 1-1/2^k

import random
import math

'''
def modpow(a,m):
    s=m-1
    r=1
    while s!=0:
        if s%2==1:
            r=r*a%m
        a=(a*a)%m
        s=s//2
    return r
'''
m=int(input('m = '))
k=int(input('安全系数k = '))

s=k
while s>0:
    a=random.randint(2, (m-2))
    print('a=',a,end="")
    #print(',(',a,',',m,')=',math.gcd(a, m),end="")
    if math.gcd(a, m)==1:
        #print(a,'^(',m,'-1)(mod',m,')≡',modpow(a, m),',',end="")
        #or  print(a,'^(',m,'-1)(mod',m,')≡',pow(a, m-1, m),',',end="")
        if pow(a, m-1, m)==1:
        #if modpow(a, m)==1:
            s=s-1
            print(',故m可能为素数  ',100*(1.0-(1.0/(2**(k-s)))),'%')
    else:
        print('m为合数')
        break
if s==0:
    print('m',100*(1.0-(1.0/(2**k))),'%可能为素数')

仅供参考,其实这玩意网上一搜一大把
主要解决模指数问题就行,如果仅用**做大数幂运算的话会很慢

上一篇:P4549 【模板】裴蜀定理


下一篇:(扩)欧几里得的一些见解