Miller-Rabin素性测试的Python实现

柴柴柴拆柴柴 edited 4 年,6 月前

人们至今没有找到一个判断一个正整数是否为素数的简单方法,尽管$\mathrm{Wilson}$定理给出了一个正整数是素数的充要条件,即正整数$n$是素数当且仅当
$$(n-1)! \equiv -1 \; (\mathrm{mod} \; n)$$
然而,这种方法计算量过大,因此在实务中通常使用$\mathrm{Miller-Rabin}$算法进行素性测试,这是一个随机算法,理论依据是费马小定理与二次探测定理。

关于$\mathrm{Miller-Rabin}$算法的细节,可以访问此链接

在离散数学课程中,有这样一道作业:

给定一个整数$n$,求大于等于$n$的最小素数
已知相邻两个素数之差不会超过246

下面给出解决这个问题的Python代码:

import random

def fastmod(x,n,p):
    res=1
    while n!=0:
        if n&1==1:
            res=(res*x)%p
        n>>=1
        x=(x*x)%p
    return res

def miller_rabin(n):
    d=n-1
    i=random.randint(1,n-1)
    while d!=1:
        if fastmod(i,d,n)==1:
            if d%2!=0:
                return True
            d=d//2
            if fastmod(i,d,n)==n-1:
                return True
        else:
            return False
    return True

r1=int(input("r1="));i=r1+1
while i<=r1+246:
    if i%2!=0:
        if miller_rabin(i):
            res=i
            break
    i+=1

print(res)

Comments

只有红茶可以吗

支持

kingno

支持