实 验 报 告（一）

Fermat素性检测算法

一、实验目的（包括实验环境、实现目标等等）

1.实验环境：python 3.11.3
2.实验目标：理解 Fermat 素性检测算法的基本原理和费马小定理，并且编写相应程序实现对大数实现素数检验。

二、方案设计

（包括背景、原理、必要的公式、图表、算法步骤等等）

背景：素性检测是判断一个数是否为素数的过程。素数在密码学、数论等领域有着重要的应用。本次实验旨在运用Fermat 素性检测来检验4个大数是否为素数。
原理：费马小定理指出若 p 为素数，并且 a 是一个小于 p 的整数，满足 ap−1≡1(modp)a^{p-1} \equiv 1 (mod p) 。基于此定理得到Fermat素性检测。
给定奇整数m≥3和安全参数k

（1）随机选取整数a,2≤a≤m-2；

（2）计算g=(a,m)，如果g=1，转(3);否则，跳出，m为合数；

（3）计算r=am−1(modm){r=a}^{m-1}(modm)，如果r=1，m可能是素数，转（1）；否则，跳出，m为合数；

（4）重复上述过程k次，如果每次得到m可能为素数，则m为素数的概率为1−12k1-\frac{1}{2^k}。

三、方案实现

（包括算法流程图、主要函数的介绍、算法实现的主要代码等等）

流程图：

图片的描述

主要函数介绍：

1.计算最大公约数的函数 gcd(a,b):

1
2
3
4
5
def gcd(a, b):
   if b == 0:
       return a
   else:
       return gcd(b, a % b)

这个运用迭代的思想，运用欧几里得算法不断地将每轮的余数和除数互换后相除更新余数的思想得到最终的最大公约数。

2．快速模指数算法exponentiation(a, b, n):

1
2
3
4
5
6
7
8
9
def exponentiation(a, b, n):
    c = 1
    d = a % n
    while b:
        if b % 2 == 1:
            c = c * d % n
        d = d * d % n
        b //= 2
    return c

在本函数中运用快速模指数算法，这个是用来计算ab mod na^b\ mod\ n的其中c用来存储每个阶段的中间变量，d用来存储每轮a2i mod na^{2^i}\ mod\ n的数值。这样能够快速得到最终答案。
用fermat(m,k)函数来检验在安全系数为k的情况下m是否为素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def fermat(m,k):
    if m % 2 == 0 or m < 3:
        print("m必须是大于等于3的奇数")
        return False
    kk = k
    while k:
        a = random.randint(2, m - 2)
        g = gcd(a, m)
        if g != 1:
            print(f"m是合数")
            break
        else:
            r = exponentiation(a, m - 1, m)
            if r != 1:
                print(f"m是合数")
                break
        k -= 1
    if k == 0:
        print(f"m是素数的概率为{(1 - 1 / 2 ** kk) * 100}%")

主要思路是首先判断m是否为大于等于3的奇数，然后判断m和生成的随机数a是否互素，然后再计算r是否数值为1以此判断是否是合数，重复k论实验，若k论实验成功最终得到m为素数概率为1−12k1-\frac{1}{2^k}，反之m为合数。

最后调用函数检验,主函数如下

1
2
3
4
5
6
if __name__ == "__main__":
    f = open("4.txt", "r")
    m = int(f.readline())
    f.close()
    k = 10
    fermat(m, k)

四、数据分析(包括算法测试数据的分析，运行结果截图等等)

  1. 对1.txt检验：k = 10
1
743476040059754298379331647007684224429004972336533937786799284757790400765316630522369642718204165253922832684184615021404737105614714107158733905598636152327037707290538422718453498125366750918857659068838460954633737911274770976191590193809661578032117496009853673140977556559136466107768672598883924301125589893895001253674886100289402530711221893

alt text

  1. 对2.txt检验：k = 10
1
5434520625653357625890820149570485819447986258433769976634917091398967074086679540928507095017715540385352266035820823142060119390272763774034231321959236056764511968630360067353876686142517564224926196131349204754111599877101485686283117193149781387816214484583521923017500621725053392290279263586984207169423800476914654441473576611460323772832328657

alt text

  1. 对3.txt检验：k = 10
1
2
876147742992673125957404768949712978720573116974723188491435550196169965040848206868200084918233743662847668000971402407461887306389122707315529364807593342507936022301657320206278702095378618110195051280478534126716517153056984269659532882692418682262081495725304483536777013188527470348249542840277926802938912332306310470632601156641005608958891

alt text

  1. 对4.txt检验：k = 10
1
9876147742992673125957404768949712978720573116974723188491435550196169965040848206868200084918233743662847668000971402407461887306389122707315529364807593342507936022301657320206278702095378618110195051280478534126716517153056984269659532882692418682262081495725304483536777013188527470348249542840277926802938912332306310470632601156641005608958891

alt text

五、思考与总结

如果有一个整数𝒂，(𝒂,𝒎)=𝟏，使得𝒂^𝒎−𝟏≡𝟏 𝒎𝒐𝒅 𝒎 则𝒎一定是一个素数吗？为什么？（请简述并举例说明，不能只简单回答“是”或“不是”）

答：m不一定是素数，因为费马小定理是规定m 是一个素数，那么对于任何整数 a(1 < a < m)a (1\ <\ a\ <\ m)，都有am−1≡1 (mod m)a^{m-1} \equiv 1\ \left(mod\ m\right)，但反过来并不一定成立。存在一些合数 m 也满足上述条件，是伪素数。
比如：我们取m=341,a=2m = 341, a = 2,很明显(a,m)=1(a,m)=1 ,但是 2341−1≡1 (mod 341)2^{341-1}\equiv1\ \left(mod\ 341\right) 又因为 341 = 11 × 31341\ =\ 11\ \times\ 31 可以说明m是合数。

Fermat素性检测中都用到了哪些运算？分别实现什么功能？请简述。

答：运用了用欧几里得算法求最大公约数，用来检验随机生成的a是否和m互素。运用了快速模指数算法运算，用来快速计算r=am−1≡1modmr = am-1≡1 mod m的数值，判断m是否为合数。

你还了解哪种素性检测算法？请简述，并分析其与Fermat素性检测算法的区别与联系。

答： Miller-Rabin 素性检测算法，它是一种基于随机性的概率素性检测算法。也是多次测试来判断一个数是否为素数。
算法：

  1. 检查m是否为 2 或 3，如果是，则 n 是素数。检查 n 是否为偶数或小于 2，如果是，则 n 是合数。

  2. 将待检测的数 m 写成$\ m\ =\ d\ \times\ 2^r\ +\ 1$的形式，d为奇数。

  3. 进行 k 次测试：

    (1)随机选择一个整数 a，(1 < a < m−1)(1\ <\ a\ <\ m-1)。

    (2)计算x = ad mod mx\ =\ a^d\ mod\ m。如果x=1x = 1或x=m−1x = m-1，则 m 可能是素数。则继续下一次测试转到(1);否则重复计算 x = x2 mod m\ x\ =\ x^2\ mod\ m，最多重复r−1r-1次。如果在任何一次计算中x=m−1x=m-1，则继续下一次测试转到(1)。如果所有测试都未通过，则m是合数。

    (3)如果 k 次测试都通过，则m可能是素数,m为素数概率为1−14k1-\frac{1}{4^k}

区别：

Fermat 素性检测只进行一次幂模运算，而 Miller-Rabin 进行多次幂模运算，检测更严格。Fermat 素性检测容易被费马伪素数欺骗，而 Miller-Rabin 通过多次检测减少了伪素数的概率。并且在安全参数为k的情况下Fermat 素性检测正确概率为1−12k1-\frac{1}{2^k}，而Miller-Rabin正确概率是1−14k1-\frac{1}{4^k}

联系：

两者都是随机性的概率素性检测的算法，并且都使用模指数运算来检验是否是素数。

实验过程中还遇到了什么问题，如何解决的？通过该实验有何收获？

答：在快速模指数函数编写的时候起初运行的很慢，后来我发现是我在每轮生成中间变量b_n的时候没有用取余数之后的值进行平方运算。后来改正后速度得到了提高。经过本实验我深入理解了 Fermat 素性检测算法的原理和实现过程。学会了如何使用快速幂算法进行高效的大整数运算。此外还了解了Miller-Rabin 素性检测算法。

实验完整代码

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
import random

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
    
def exponentiation(a, b, n):
    c = 1
    d = a % n
    while b:
        if b % 2 == 1:
            c = c * d % n
        d = d * d % n
        b //= 2
    return c
# print(exponentiation(312,13,667))

def fermat(m,k):
    if m % 2 == 0 or m < 3:
        print("m必须是大于等于3的奇数")
        return False
    kk = k
    while k:
        a = random.randint(2, m - 2)
        g = gcd(a, m)
        if g != 1:
            print(f"m是合数")
            break
        else:
            r = exponentiation(a, m - 1, m)
            if r != 1:
                print(f"m是合数")
                break
        k -= 1
    if k == 0:
        print(f"m是素数的概率为{(1 - 1 / 2 ** kk) * 100}%")

if __name__ == "__main__":
    f = open("4.txt", "r")
    m = int(f.readline())
    f.close()
    k = 10
    fermat(m, k)