信安数学基础学习与练习

2025-12-15

引言

hello！欢迎来到咪猫魔法世界~ 🐾✨

本篇内容参考了不少CSDN上的优质文章与笔记，我把核心知识点都提炼成了易懂的短句（可能略有偏差，但足够贴合初学理解）。其中包含具体示例、算法解析、构造方法的优质资料也都整合在文中啦，希望能给同样初学的师傅们一些帮助（若有理解上的偏差也希望师傅们及时指出！）~~o( =∩ω∩= )m

一、信安数学基础学习

1. 整除、欧几里得除法与素数基本定理

整除：若a÷b=c无余数，则称b整除a（记为b∣a），商为c。
关键性质：
- 传递性：如12能被6整除、6能被3整除，则12必能被3整除；
- 线性组合：如6能整除12和18，则6也能整除12×2+18×3=78（倍数的线性组合仍为倍数）。
欧几里得除法（带余除法）：a÷b=c余d（0<d<b），其中c和d是唯一确定的。
核心作用：是求最大公约数、解同余方程的基础，先固定除法的“商余关系”。
最大公约数(gcd)与欧几里得算法(辗转相除法)：
- gcd定义：能同时整除a和b的最大整数，如gcd(198,252)=18；
- 特殊情况：若gcd(a,b)=1，则a和b互素（如4和5，仅1能同时整除）；
- 欧几里得算法：大数÷小数得余数，再用原除数÷余数，重复至余数为0，最后一个非零余数即为gcd；
- 示例：计算gcd(252,198)
  
  ①252÷198=1余54；
  
  ②198÷54=3余36；
  
  ③54÷36=1余18；
  
  ④36÷18=2余0
  
  → 最终gcd=18。
扩展欧几里得算法：
- 核心能力：除求gcd(a,b)外，还能找到整数x、y满足a×x + b×y = gcd(a,b)；
- 计算方法：回代法——先通过欧几里得算法求gcd，再从最后一步反向回代，推导出满足等式的x、y；
- 注意点：若x为负数，需累加模数至x为正；
- 核心应用：求模逆元——若a和m互素（gcd(a,m)=1），可找到x使a×x ≡1 mod m（x即为a的逆元，如2×3=6≡1 mod5，3是2的逆元），是密码学解密的关键。
素数基本定理：
- 核心结论：当x→∞时，不大于x的素数个数π(x)与x/lnx渐近等价（比值趋近于1）；
- 应用：用于计算欧拉函数、判断RSA等密码算法的安全性（依赖大素数难分解的特性）。

2. 同余与剩余系

同余：
- 定义：若a和b除以m的余数相同，则称a≡b(mod m)（如17≡2 mod5），且a-b能被m整除；
- 核心性质：
  - 加减乘不变：如3≡8 mod5、4≡9 mod5，则3+4=7≡8+9=17 mod5，3×4=12≡8×9=72 mod5；
  - 消去律（有条件）：如2×3≡2×8 mod5，因2和5互素，可消去2得3≡8 mod5。
剩余系：
- 完全剩余系：除以m能覆盖0~m-1所有余数的一组数（无遗漏、无重复）；
- 简化剩余系：从完全剩余系中筛选出与m互素的数，其个数为欧拉函数φ(m)；
- 示例：模6的完全剩余系为{0,1,2,3,4,5}，简化剩余系为{1,5}，故φ(6)=2。

3. 欧拉函数、欧拉定理与费马小定理

欧拉函数φ(m)：1~m中与m互素的整数个数，如φ(6)=2。
五种计算方法：
- 若m=1，则φ(1)=1；
- 若p是素数，则φ(p)=p-1（1~p-1均与p互素）；
- 若p是素数且k≥1，则φ(pᵏ)=pᵏ - pᵏ⁻¹ = pᵏ⁻¹(p-1)（排除能被p整除的数）；
- 若m、n互素，则φ(mn)=φ(m)φ(n)（积性函数特性）；
- 通用公式：若m=∏ᵢ₌₁ʳ pᵢᵏⁱ，则φ(m)=m∏ᵢ₌₁ʳ(1-1/pᵢ)。
欧拉定理：
- 核心结论：若gcd(a,m)=1，则a^φ(m)≡1(mod m)（a的φ(m)次方与1的差能被m整除）；
- 核心作用：简化高次幂模运算；
- 示例：a=2、m=5（gcd(2,5)=1，φ(5)=4），则2⁴=16≡1(mod5)；
- 应用：计算3¹⁰⁰(mod7) 因gcd(3,7)=1，φ(7)=6，故3⁶≡1(mod7)；100=6×16+4 → 3¹⁰⁰≡(3⁶)¹⁶×3⁴≡1¹⁶×81≡4(mod7)。
费马小定理：
- 核心结论：欧拉定理的简化版——若p是素数且a不能被p整除，则a^(p-1)≡1(mod p)；
- 推论：对任意a，素数p满足a^p≡a(mod p)（如4⁷=16384≡4 mod7）。

4. 中国剩余定理(CRT)

核心结论：若模数两两互素（如3和5），则任意给定余数要求，都能找到唯一解（解在模数乘积范围内）。
核心作用：将大模数计算拆分为小模数计算（如算x mod15拆为x mod3和x mod5），简化RSA等算法运算。
定理内容及构造步骤：
1. 定理内容：设m₁,m₂,…,mₖ两两互素，M=m₁m₂⋯mₖ，Mᵢ=M/mᵢ，对任意整数a₁,…,aₖ，同余方程组：
  \[ \left\ \begin{array}{l} x \equiv a₁(mod m₁) \\ x \equiv a₂(mod m₂) \\ \vdots \\ x \equiv aₖ(mod mₖ) \end{array} \right. \]
  有唯一解x≡∑ᵢ₌₁ᵏ aᵢMᵢMᵢ’ (mod M)（Mᵢ’是Mᵢ模mᵢ的逆元，即MᵢMᵢ’≡1(mod mᵢ)）；
2. 构造步骤（k=2，m₁、m₂互素）：
  - 步骤1：计算M=m₁m₂，M₁=m₂，M₂=m₁；
  - 步骤2：求M₁模m₁的逆元M₁’（解m₂x≡1(mod m₁)）、M₂模m₂的逆元M₂’（解m₁y≡1(mod m₂)）；
  - 步骤3：解为x=a₁M₁M₁’+a₂M₂M₂’(mod M)。

二、信安数学基础练习

✨ 咪猫碎碎念：目前仅能独立完成gcd计算的代码编写，CRT相关代码的核心逻辑需借助ai才能实现，后续还会反复打磨，直到能熟练掌握

1. 用Python实现gcd的计算(并给出Bézout等式)

数论的基础原理我已经在前面进行了梳理，下面我就直接附上代码（a、b可替换）了。代码核心是循环更新余数和系数（替代递归更易理解），注释我也尽量写得比较详细，对新朋友很友好了：

 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


def extended_gcd(a, b):
    # 自定义扩展欧几里得函数，返回(gcd, x, y)满足a*x + b*y = gcd
    old_r, r = a, b  # 上一步/当前余数
    old_s, s = 1, 0  # 上一步/当前x的系数
    old_t, t = 0, 1  # 上一步/当前y的系数
    
    # 辗转相除，直到余数为0
    while r != 0:
        quotient = old_r // r  # 计算商
        # 更新余数：新余数 = 旧余数 - 商×当前余数
        old_r, r = r, old_r - quotient * r
        # 更新x系数（逻辑同余数）
        old_s, s = s, old_s - quotient * s
        # 更新y系数（逻辑同余数）
        old_t, t = t, old_t - quotient * t
    
    # 余数为0时，old_r是gcd，old_s/old_t是满足等式的x/y
    return (old_r, old_s, old_t)

# 可替换的a、b值
a = 252
b = 198
# 调用函数
gcd, x, y = extended_gcd(a, b)
print(f"{a}和{b}的最大公约数是:{gcd}")
print(f"满足 {a}×x + {b}×y = {gcd} 的解是:x={x}, y={y}")
print("验证:", a * x + b * y)  # 结果等于gcd即验证正确

2. 用Python实现一个CRT函数(互素)

CRT的实现依赖扩展欧几里得算法求逆元，代码基于上面的extended_gcd函数编写（仅适用于模数互素的场景）：

 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


# 扩展欧几里得算法（复用）
def extended_gcd(a, b):
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1
    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t
    return (old_r, old_s, old_t)

# 实现互素场景下的CRT
def crt(remainders, moduli):
    current_sol = 0  # 初始解：x ≡ 0 mod 1
    current_mod = 1  # 初始模数：1
    
    # 遍历每个同余方程x ≡ a (mod m)
    for a, m in zip(remainders, moduli):
        # 求current_mod在模m下的逆元
        gcd, inv, _ = extended_gcd(current_mod, m)
        # 互素CRT要求模数互素（gcd=1）
        if gcd != 1:
            return "错误:模数不互素,普通CRT无法求解"
        
        # 求解k：k ≡ (a - current_sol) * 逆元 (mod m)
        k = ((a - current_sol) * inv) % m
        # 更新解和模数
        current_sol += k * current_mod
        current_mod *= m
        # 取模简化解的数值
        current_sol %= current_mod
    
    return current_sol

# 测试示例（可替换为多组互素模数）
if __name__ == "__main__":
    remainders = [3, 5]
    moduli = [5, 11]
    solution = crt(remainders, moduli)
    print(f"方程组的解:{solution}")
    print(f"验证:{solution} mod 5 = {solution % 5}(应等于3)")
    print(f"验证:{solution} mod 11 = {solution % 11}(应等于5)")

3. 用Python实现通用CRT函数

通用CRT支持模数非互素的场景，核心是“逐步合并方程+检查矛盾”，我对比了互素/通用CRT的差异，整理如下：

对比维度	互素CRT	通用CRT
核心步骤	1. 计算所有模数乘积；2. 直接套公式求解	1. 逐个合并方程；2. 合并后更新解和模数
矛盾检查	无（模数互素必存在解）	有（检查合并的方程是否矛盾）
模数计算	直接相乘（如3×5=15）	计算最小公倍数（如4和6的lcm=12）
适用场景	确定模数两两互素	模数未知/非互素

简单来说：互素CRT像“填空题”（套公式即可），通用CRT像“证明题”（逐步推导+校验），若发现矛盾则及时终止（如“x>10且x<5”无解题）。

通用CRT代码实现：

 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


# 扩展欧几里得算法（复用）
def extended_gcd(a, b):
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1
    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t
    return (old_r, old_s, old_t)

# 通用CRT实现（支持模数非互素）
def general_crt(remainders, moduli):
    current_a = 0  # 当前解的余数
    current_m = 1  # 当前模数
    
    # 逐个合并同余方程
    for a, m in zip(remainders, moduli):
        # 求current_m和m的最大公约数及系数
        gcd, x, y = extended_gcd(current_m, m)
        # 检查是否有解：(a - current_a)需能被gcd整除
        if (a - current_a) % gcd != 0:
            return f"无解:方程 x≡{current_a}({current_m}) 和 x≡{a}({m}) 矛盾"
        
        # 计算新模数（最小公倍数）
        lcm = current_m // gcd * m
        # 计算合并后的解
        k = ((a - current_a) // gcd * x) % (m // gcd)
        new_a = current_a + k * current_m
        # 简化解的数值
        current_a = new_a % lcm
        current_m = lcm
    
    return current_a  # 返回最小正整数解

# 测试示例（有解/无解场景）
if __name__ == "__main__":
    # 测试1：有解（x≡3 mod4，x≡1 mod6 → 解为7）
    print("测试1:")
    remainders1 = [3, 1]
    moduli1 = [4, 6]
    solution1 = general_crt(remainders1, moduli1)
    print(f"解:{solution1}")
    if isinstance(solution1, int):
        print(f"验证:{solution1} mod4 = {solution1 % 4}(应等于3)")
        print(f"验证:{solution1} mod6 = {solution1 % 6}(应等于1)")
    
    # 测试2：无解（x≡1 mod2，x≡0 mod4 → 矛盾）
    print("\n测试2:")
    remainders2 = [1, 0]
    moduli2 = [2, 4]
    solution2 = general_crt(remainders2, moduli2)
    print(f"结果:{solution2}")

最后：通用CRT的测试中，无解场景会“及时止损”，有解场景则会“不撞南墙不回头”地推导出唯一解，这种严谨的推导思路，也是密码学学习中需要养成的习惯哦~🐾