写在最前面：

下面三种检验方法的目的是为了判断一个数是否为素数。其原理都是一样的，即随机生成一个数，判断这个数与大数之间是否满足伪素数关系。换句话说，就是有条件可以直接判断这个数是否为合数，经过多次尝试后没有满足合数条件，就认为这个数很大可能为素数。

Fermat素性检验

原理及流程图

其原理本质在于费马小定理及其逆反条件

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import math
import random, time

def Fermat_detect(n, t):
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    for _ in range(t):
        b = random.randint(2, n-2)
        d = math.gcd(b, n)
        if(d != 1):
            return False
        else:
            r = pow(b, n-1, n)
            if(r != 1):
                return False
    return True

def main():
    n = int(input("请输入需要检测的数字："))

    t = int(input("请输入循环轮数："))
    start = time.perf_counter()
    if Fermat_detect(n, t):
        he = 1.0 / pow(2, t)
        print("%d 是素数的可能性是%.5f" % (n, 1 - he))
    else:
        print("%d 为合数" % n)
    end = time.perf_counter()
    print("time is :%.5f" % (end - start))

if __name__ == "__main__":
    main()

注意点:
1、使用random模块生成随机数
2、使用math模块求解最大公因子和幂次、求余运算
3、除法运算尽量使用//

Solovay_Stassen素性检验

原理及流程图

其本质是利用欧拉定理及其逆反条件，这个逆反条件就是判合数条件。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import math
import random, time

# 此函数用于求解雅克比符号(利用性质求解）
# n&1   与运算  可以判断n是否为偶数:如果是偶数，n&1,返回0；否则返回1，为奇数
def jacobi(n, m): # calc Jacobi(n/m)
    n = n%m
    if n == 0:
        return 0
    Jacobi2 = 1
    if not (n&1): # 若有n为偶数, 计算Jacobi2 = Jacobi(2/m)^(s) 其中n = 2^s*t t为奇数
        k = (-1)**(((m**2-1)//8)&1)
        while not (n&1):
            Jacobi2 *= k
            n >>= 1
    if n == 1:
        return Jacobi2
    return Jacobi2 * (-1)**(((m-1)//2*(n-1)//2)&1) * jacobi(m%n, n)



def Solovay_Stassen(n, t):
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    for _ in range(t):
        b = random.randint(2, n-2)
        m = int((n-1)//2)
        r = pow(b, m, n)
        if(r != 1 and r != n-1):
            return False
        if r == n-1:
            r = -1
        s = jacobi(b, n)
        if(r != s):
            return False
    return True


def main():
    n = int(input("请输入需要检测的数字："))

    t = int(input("请输入循环轮数："))
    start = time.perf_counter()
    if Solovay_Stassen(n, t):
        print("%d 可能为素数" % n)
    else:
        print("%d 为合数" % n)
    end = time.perf_counter()
    print("time is :%.5f" % (end - start))


if __name__ == "__main__":

    main()

注意点：
这里要使用代码实现雅克比符号的求解，这个过程就是利用其性质：分子为1,2,0等与二次互反率。

  • n&1 判断是否为偶数，是返回0.

  • n>>1右移一位，其实就是 除以2

miller_robin素性检验

原理及流程图

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import random,time

def is_primes(b, d, s, n):

    x = pow(b, int(d), n)
    if x == 1 or x == n - 1:
       return False
    for _ in range(s - 1):
        x = pow(x, 2, n)
        if x == n - 1:
            return False
    return True

def miller_rabin(n, t):
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    s = 0
    d = n-1
    while d % 2 == 0:
        s += 1
        d = d // 2
    for _ in range(t):
        b = random.randrange(2, n-1)
        if is_primes(b, d, s, n):
            return False
    return True

def main():
    n = int(input("请输入需要检测的数字："))

    t = int(input("请输入循环轮数："))
    start = time.perf_counter()
    if miller_rabin(n, t):
        print("%d 可能为素数"% n)
    else:
        print("%d 为合数"%n)
    end = time.perf_counter()
    print("time is :%.5f" % (end - start))

if __name__ == "__main__":
    main()

运行实例:

给出一个大素数查询网站：https://primes.utm.edu/lists/small/small.html?tdsourcetag=s_pctim_aiomsg#100