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

实验环境：

  • Window11

  • Visual Studio Code v1.105.0

  • python v3.12.0a7

实现目标：

实现Fermat素性检测算法，并对两个大整数进行分析。

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

原理：

给定素数p，a∈Z，则有；

奇整数m，若任取一整数$2≤a≤m-2，(a,m)=1$，使得，则m至少有的概率为素数。

算法步骤：

给定奇整数m≥3和安全参数k：

(1)随机选取整数a，$2≤a≤m-2$；

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

(3)计算$r=a^{(m-1)} (mod⁡m )$，如果r=1，m可能是素数，转(1)，否则,跳出，m为合数；

(4)重复上述过程k次，如果每次得到m可能为素数，则m为素数的概率为。

方案实现

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

算法流程图

主要函数介绍

fermat_primality_test(n, k)

  • 功能：实现费马素性检测算法，用于判断一个数是否为素数

  • 参数：

    • n：待检测的整数

    • k：安全参数，表示测试轮数，越大误判概率越低

  • 返回值：布尔值，True表示可能是素数，False表示一定是合数

  • 工作原理：

    • 首先处理特殊情况

    • 然后进行k轮测试，每轮随机选择a并验证费马小定理

    • 若任何一轮不满足，则判定为合数

dread_large_number_from_txt(file_path)

  • 功能：从指定文本文件中读取大整数

  • 参数：file_path：文本文件路径

  • 返回值：从文件中读取并转换的整数

  • 异常处理：

    • 文件不存在

    • 文件内容不是有效整数

    • 其他读取错误

主程序模块

  • 功能：程序入口点，负责协调执行整个流程

  • 执行步骤：

    1. 从文本文件读取待检测的大整数

    2. 获取用户输入的安全参数k

    3. 调用fermat_primality_test函数进行素性检测

    4. 输出最终检测结果

主要代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import random

def fermat_primality_test(n, k):

    # 处理特殊情况，直接返回结果

    if n <= 1:

        return False

    elif n <= 3:

        return True

    elif n % 2 == 0:

        return False

    

    # 多轮检测，降低误判概率

    for _ in range(k):

        # 随机选择基数a，范围为[2, n-2]

        a = random.randint(2, n - 2)

        # 用pow函数高效计算a^(n-1) mod n，内置函数支持大整数且性能更优

        if pow(a, n - 1, n) != 1:

            return False

    

    # 所有轮次通过，判定为大概率素数

    return True

def read_large_number_from_txt(file_path):

    try:

        # 读取文件内容，去除空白字符（如换行、空格）

        with open(file_path, 'r', encoding='utf-8') as f:

            content = f.read().strip()

        # 将字符串格式的大整数转为int类型（Python原生支持任意长度整数）

        return int(content)

    except FileNotFoundError:

        print(f"错误：未找到文件 {file_path}")

        exit()

    except ValueError:

        print("错误：文件内容不是有效的整数")

        exit()

    except Exception as e:

        print(f"读取文件时发生错误：{e}")

        exit()

# 主程序：读取文件并执行检测

if __name__ == "__main__":

    # TXT文件实际路径

    txt_file_path = "2.txt"

    # 读取TXT中的大整数

    large_number = read_large_number_from_txt(txt_file_path)

    # 输入安全参数k

    k = int(input("请输入安全参数k:"))

    # 执行Fermat素性检测

    is_prime = fermat_primality_test(large_number, k)

    

    # 输出检测结果

    if is_prime:

        print(f"检测结果：{large_number}\n该数大概率是素数")

    else:

        print(f"检测结果：{large_number}\n该数是合数")

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

对2.txt文件中的大整数进行检测：

对4.txt文件中的大整数进行检测：

思考与总结

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

答：不一定。例如a=8,m=63，a和m互素，并且满足863-1≡1(mod63)，也就是am-1≡1(modm)，但是m并不是素数。

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

答:（1）用到了求模运算，主要是计算。
（2）判断两个数是否互素，主要是计算g=(a,m)，g是否等于1。

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

答：米勒-拉宾（Miller-Rabin）素性检测算法，两者的联系在于：均为概率性算法，核心依赖模幂运算，且真正的素数必能通过两者的检测。区别在于：米勒-拉宾引入二次探测定理，测试条件更严格，能有效规避费马检测无法识别的卡迈克尔数，准确性和实用性更高；费马检测仅依赖单一条件，易受伪素数干扰，而米勒-拉宾在特定范围内可通过固定基底实现确定性检测。

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

答：通过Fermat素性检测实验，不仅深入理解了该算法的原理与局限性还掌握了快速模幂等优化技巧以应对大整数运算挑战；同时，结合数论知识体会到理论与实践的差距，认识到概率性算法需在效率与准确性间权衡，也为后续理解更优算法奠定了基础，培养了针对具体问题选择和优化算法的思维。