费马小定理实现大数素性检测

Fermat小定理：给定素数 풑，풂 ∈ 풁 ，则有 풂 ^ ( 풑 - 1 ) ≡ ퟏ ( 풎풐풅 풑 ) 。
给定奇整数 풎 ≥ ퟑ 和安全参数 풌
（1） 随机选取整数풂 ，ퟐ ≤ 풂 ≤ 풎 − ퟐ；
（2） 计算품 = ( 풂, 풎 ) ，如果 품 = ퟏ，转（3）；否则，跳出， 풎 为合数；
（3） 计算 풓 = 풂 ^ ( 풎−ퟏ ) ( 풎풐풅 풎 ) ，如果 풓 = ퟏ，풎 可能是素数，转（1）；否则，跳出， 풎 为合数；
（4） 重复上述过程 풌 次，如果每次得到 풎 可能为素数，则 풎 为素数的概率为 ퟏ − ퟏ / ( ퟐ ^ 풌 ) 。

以下为Python实现的代码：

import random
m = int((input()))    # 输入要检测的大整数
k = int((input()))    # 选定安全系数
i = 1
def Fermat(m,k,i):
    if i <= k:
        a = random.randrange(2, m-2, 1)  # 随机选取整数a，2≤a≤m-2
        print(a)
        def gcd(a, m):  # 辗转相除法求最大公约数
            if a < m:
                a, m = m, a
            while m != 0:
                temp = a % m
                a = m
                m = temp
            return a
        g = gcd(a, m)
        if g == 1:    # 若为素数则用费马小定理进行进一步验证
            r = pow(a, m-1, m)   # 求模运算，得到m除a的m-1次方的余数
            if r == 1:    # 若为素数则再重新选定a再次验证
                i += 1
                Fermat(m,k,i)
            else:
                return 0
        else:
            return 0
    else:
        return 1
b = Fermat(m,k,i)
if b == 0:
    print("{}为合数".format(m))
else:
    c = 1 - 1/(pow(2,k))
    d = format(c,'.4%')
    print("安全参数为{}时，{}有{}的可能为素数".format(k,m,d))

①当输入的m为-1时，k取3

m的值：

k的值及第一个a的值：

第二个a的值：

第三个a的值：

结论：

则m有87.5%的概率为素数。

②当输入的m为-1时，k取5

随机得到的a的值：

最终判定m为合数。