信息安全基础与密码学综合实验(二)——中国剩余定理

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

实验环境

• Window11
• Visual Studio Code v1.105.0
• python v3.12.0a7

实现目标

实现剩余定理算法，支持读取文本文件中500位大整数测试数据，求解三个方程组成的一次同余方程组；验证算法对两两互素模的正确性，掌握非两两互素模方程组的处理思路；完成算法测试与数据分析。

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

背景

中国剩余定理是数论中的重要定理，用于求解模数两两互素的一次同余方程组。其核心价值在于将复杂的多模数同余问题，转化为简单的单模数运算，广泛应用于密码学、分布式计算等领域。

原理

中国剩余定理：设正整数$m_1,m_2,…,m_k$两两互素，对任意整数$a_1,a_2,\cdots,a_k$，一次同余方程组

$$\left\{ \begin{aligned} x &\equiv& a_1 \pmod{m_1} \\ x &\equiv& a_2 \pmod{m_2} \\ &\vdots& \\ x &\equiv& a_k \pmod{m_k} \end{aligned} \right.$$

在模$m$意义下有唯一解，该解表示为：

$$x \equiv M_1M_1^{-1}a_1 + M_2M_2^{-1}a_2 + \dots + M_kM_k^{-1}a_k \pmod{m}$$

其中，$m = m_1m_2\cdots m_k$，$M_j = \frac{m}{m_j}$（$j=1,2,\cdots,k$）。

算法步骤

1. 判断正整数$m_1,m_2,\cdots,m_k$是否两两互素；若是，则继续；若否，则跳出，输出“不能直接利用中国剩余定理”；
2. 计算总模数$m = m_1m_2\cdots m_k$，以及每个模数对应的$M_j = m \div m_j$；
3. 计算每个$M_j$在模$m_j$下的逆元$M_j^{-1} \pmod{m_j}$；
4. 计算每个分项$x_j \equiv M_jM_j^{-1}a_j \pmod{m}$；
5. 计算最终解$x \equiv \sum_{j=1}^{k} x_j \pmod{m}$。

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

算法流程图

主要函数的介绍

gcd(a,b)

• 功能描述：用欧几里得算法计算两个整数的最大公约数
• 输入参数：a（整数）、b（整数）
• 输出参数：最大公约数（整数）

extended_gcd(a,b)

• 功能描述：扩展欧几里得算法，求解满足ax+by=gcd(a,b)的x,y
• 输入参数：a（整数）、b（整数）
• 输出参数：元组 (x,y,gcd(a,b))（均为整数）

mod_inverse(a,m)

• 功能描述：求解a在模m下的逆元（仅当gcd(a,m)=1时存在）
• 输入参数：a（整数）、m（整数）
• 输出参数：逆元（整数），若不存在则报错

is_pairwise_coprime(ms)

• 功能描述：判断模数列表是否两两互素
• 输入参数：ms（模数列表，如 [m1,m2,m3]）
• 输出参数：布尔值（True = 两两互素，False = 非两两互素）

read_test_data(file_path)

• 功能描述：读取测试数据，按“a1,a2,a3,m1,m2,m3”顺序提取
• 输入参数：file_path（数据文件路径）
• 输出参数：元组(as_list, ms_list)， as_list=[a1,a2,a3]， ms_list=[m1,m2,m3]

crt_solver(as_list, ms_list)

• 功能描述： CRT 主求解函数，仅处理两两互素模数的方程组
• 输入参数：as_list（余数列表）、ms_list（模数列表）
• 输出参数：最小正整数解x（整数）

算法实现的主要代码

def gcd(a, b):
    """计算两个整数的最大公约数（欧几里得算法）"""
    while b != 0:
        a, b = b, a % b
    return a

def extended_gcd(a, b):
    """扩展欧几里得算法：返回(x, y, g)满足 ax + by = g，其中g = gcd(a,b)"""
    if b == 0:
        return (1, 0, a)
    else:
        x, y, g = extended_gcd(b, a % b)
        return (y, x - (a // b) * y, g)

def mod_inverse(a, m):
    """求解a在模m下的逆元（仅当gcd(a,m)=1时存在）"""
    x, y, g = extended_gcd(a, m)
    if g != 1:
        raise ValueError("逆元不存在（a与m不互素）")
    else:
        return x % m

def is_pairwise_coprime(ms):
    """判断模数列表是否两两互素"""
    n = len(ms)
    for i in range(n):
        for j in range(i + 1, n):
            if gcd(ms[i], ms[j]) != 1:
                return False
    return True

def read_test_data(file_path):
    """读取测试数据：按顺序提取a1,a2,a3,m1,m2,m3（每行1个数字）"""
    try:
        with open(file_path, 'r', encoding='utf-8') as f:
            # 过滤空行，提取有效数字并转换为整数（支持大整数）
            lines = [line.strip() for line in f if line.strip()]
            if len(lines) != 6:
                raise ValueError("测试数据格式错误：需包含6个数字（a1,a2,a3,m1,m2,m3）")
            a1 = int(lines[0])
            a2 = int(lines[1])
            a3 = int(lines[2])
            m1 = int(lines[3])
            m2 = int(lines[4])
            m3 = int(lines[5])
        return [a1, a2, a3], [m1, m2, m3]
    except FileNotFoundError:
        raise FileNotFoundError("测试数据文件未找到，请检查文件路径")
    except ValueError as e:
        raise ValueError(f"数据读取错误：{str(e)}")

def crt_solver(as_list, ms_list):
    """中国剩余定理求解器（仅处理3个方程、模数两两互素的情况）"""
    # 验证输入列表长度
    if len(as_list) != 3 or len(ms_list) != 3:
        raise ValueError("需输入3个方程的余数和模数")
    
    # 步骤1：计算总模数m
    m = ms_list[0] * ms_list[1] * ms_list[2]
    
    # 步骤2：计算每个M_i = m / m_i
    M1 = m // ms_list[0]
    M2 = m // ms_list[1]
    M3 = m // ms_list[2]
    
    # 步骤3：计算每个M_i的逆元t_i
    t1 = mod_inverse(M1, ms_list[0])
    t2 = mod_inverse(M2, ms_list[1])
    t3 = mod_inverse(M3, ms_list[2])
    
    # 步骤4：计算最小正整数解x
    x = (as_list[0] * M1 * t1 + as_list[1] * M2 * t2 + as_list[2] * M3 * t3) % m
    return x

# 主程序（执行入口）
if __name__ == "__main__":
    # 读取测试数据
    try:
        as_list, ms_list = read_test_data("3.txt")
        print("=" * 50)
        print("读取的测试数据：")
        print(f"同余方程组：")
        print(f"x ≡ {as_list[0]} (mod {ms_list[0]})")
        print(f"x ≡ {as_list[1]} (mod {ms_list[1]})")
        print(f"x ≡ {as_list[2]} (mod {ms_list[2]})")
        print("=" * 50)
        
        # 判断模数是否两两互素，非互素则直接跳出并提示
        if not is_pairwise_coprime(ms_list):
            print("不能直接利用中国剩余定理")
        else:
            # 求解并输出结果
            x = crt_solver(as_list, ms_list)
            print("中国剩余定理求解结果：")
            print(f"方程组的最小正整数解为：x = {x}")
            print("\n解的正确性验证：")
            for a, m in zip(as_list, ms_list):
                verify_result = x % m
                print(f"{x} mod {m} = {verify_result}（预期值：{a}）→ {'验证通过' if verify_result == a else '验证失败'}")
        print("=" * 50)
    except Exception as e:
        print(f"程序执行错误：{str(e)}")

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

测试数据说明

本次实验使用的测试数据为3个方程组成的一次同余方程组，数据格式符合“a1,a2,a3,m1,m2,m3”顺序（每行1个数字），支持最大500位的大整数。

对测试数据1进行分析

对测试数据2进行分析

思考与总结

1. 求一次同余方程组$
   \left{
   \begin{aligned}
   x &\equiv& a_1 \pmod{m_1} \
   x &\equiv& a_2 \pmod{m_2} \
   &\vdots& \
   x &\equiv& a_k \pmod{m_k}
   \end{aligned}
   \right.
   $的解，若正整数𝒎𝟏，𝒎𝟐，…，𝒎𝒌不是两两互素，是否能直接用中国剩余定理求解？例如方程组$
   \left{
   \begin{aligned}
   7x ≡5\pmod{18}\
   13x≡2 \pmod {15}\
   \end{aligned}\right.
   $，需要如何求解？

答：不能直接利用中国剩余定理求解。

$$7x≡5(mod8)⟺\left\{ \begin{aligned} x≡3(mod2)\\ x≡2(mod9)\\ \end{aligned} \right.$$ $$13x≡2mod15⟺\left\{ \begin{aligned} x≡2\pmod3\\ x≡4\pmod5\\ \end{aligned}\right.$$

等价于：

$$\left\{ \begin{aligned} x≡3\pmod2\\ x≡2\pmod9\\ x≡4\pmod5\\ \end{aligned} \right.$$

由于2,5,9互素，运用中国剩余定理：

$$m_1=2,m_2=9,m_3=5，a_1=3,a_2=2,a_3=4,m=m_1m_2m_3=90$$, $M_1=\frac{m}{m_1}=45,M^{-1}_1=1(mod2), M_2=\frac{m}{m_2}=10,M^{-1}_2=1(mod9),M_3=\frac{m}{m_3}=18,M^{-1}_3=2(mod5)$. $$x=M_1M^{-1}_1a_1+M_2M^{-1}_2a_2+M_3M^{-1}_3a_3(modm)=29(mod90)$$

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

答：通过本次实验深入理解了中国剩余定理的适用条件（模数两两互素），掌握了“方程合并”在非两两互素模数方程组中的应用，明确了 “相容性验证”是求解非互素模数方程组的关键。