信息安全数学基础

Appearance

2026-06-13
2199
9.3m

第 3 章：一次同余方程 ​

普通方程 ax = b 你会解：两边除以 a 就完事。 同余方程 ax ≡ b (mod m) 你敢直接除吗？ 绝对不敢！在模的世界里，乱除以一个数是会“坐牢”的！

在模的世界里，“除以 a”得先问一句：a 在模 m 下有倒数（逆元）吗？ 这一章就是教你：什么时候能除、怎么除、除完之后到底有几个答案。

一、乘法逆元：模的世界里的“倒数” ​

普通数学：5 的倒数是 1/5，因为 5 × 1/5 = 1。 模的世界里没有分数，但我们想达到同样的效果：找一个整数 b，让 a × b ≡ 1 (mod m)。 这个 b 就叫 a 模 m 的乘法逆元，记作 a⁻¹ mod m。

🚨 什么时候才有逆元？（必考选择题） ​

只有当 gcd(a, m) = 1（两者互素）时才有！不互素绝对没有！ 这跟“普通数学里 0 没有倒数”是一个道理。

例题：求 40⁻¹ mod 31 ​

40 比 31 大，第一步永远是先把数变小：

40 ≡ 9 (mod 31) 所以求 40 的逆元，其实就是求 9 的逆元，即解方程 9x ≡ 1 (mod 31)。

怎么解？直接召唤第1章的“神奇表格法”！ （大数 31 写第一行，小数 9 写第二行，求 x 的那一列就是逆元）

行号商 q余数 r逆元列 (y)草稿计算（当前=上上-商×上一行）
-1无310(写死)
0无91(写死)
134-3q: 31÷9=3余4
y: 0 - 3×1 = -3
2217q: 9÷4=2余1
y: 1 - 2×(-3) = 7

余数到了 1，停止！看最后一行，逆元就是 7。 验证：9 × 7 = 63 = 31×2 + 1 ✓。 所以 40⁻¹ ≡ 7 (mod 31)。

二、同余方程有没有解？看这一个数就够了 ​

标准形式：ax ≡ b (mod m)

有解的充要条件（死记硬背）：

令 d = gcd(a, m)。如果 d 能整除 b，就有解！否则直接写“无解”。

做题第一件事，啥也别管，先算 gcd(a, m)！

  • 例题 1：12x ≡ 3 (mod 15) 有解吗？

    d = gcd(12, 15) = 3。看等式右边是 3，3 能整除 3 吗？能！有解。

  • 例题 2：12x ≡ 1 (mod 15) 有解吗？

    d = gcd(12, 15) = 3。3 能整除 1 吗？不能！无解。（交卷！）

三、有解的话怎么解？标准 4 步法（大题必考） ​

已知 ax ≡ b (mod m) 有解，且 d = gcd(a, m)。

  • 第 1 步：大瘦身（除以 d）。三处（a、b、m）同时除以 d，得到 a'x ≡ b' (mod m')。
  • 第 2 步：求逆元。在新模数 m' 下，求 a' 的逆元。
  • 第 3 步：得特解。方程两边同乘逆元，得到第一个解 x₀。
  • 第 4 步：一生二，二生 d。原方程其实一共有 d 个解！把漏掉的补齐：

    x ≡ x₀, x₀+m', x₀+2m', ..., 补够 d 个 (mod 原模数 m)

完整大题演练：解 91x ≡ 35 (mod 133) ​

第 1 步：算 d，大瘦身。 辗转相除算得 d = gcd(91, 133) = 7。 7 能整除 35，有解！且一共有 7 个解。 把 91、35、133 全体除以 7：

13x ≡ 5 (mod 19)

第 2 步：在模 19 下，求 13 的逆元。 用表格法（或者凑数法：13×3 = 39 = 19×2 + 1），得出 13 的逆元是 3。

第 3 步：两边同乘逆元 3，得特解。

x ≡ 5 × 3 = 15 (mod 19) （注意，此时的模数还是缩水版的 19）

第 4 步：扩展回模 133，补齐 7 个解。 这 7 个解就是每次加上缩水版的模数 m' = 19：

  • 第1个：15
  • 第2个：15 + 19 = 34
  • 第3个：34 + 19 = 53
  • 第4个：53 + 19 = 72
  • 第5个：72 + 19 = 91
  • 第6个：91 + 19 = 110
  • 第7个：110 + 19 = 129

答案写完整：

x ≡ 15, 34, 53, 72, 91, 110, 129 (mod 133)

连环翻车点警告

  1. 第一步大瘦身时，模数 m 忘了除以 d！只除了 a 和 b，直接 0 分。
  2. 最后一步得出一个解就跑了！题目有 d 个解，必须写全！

四、系数里带大指数——先用第2章降维打击 ​

遇到这种题：12 × 7¹⁶⁸ x ≡ 9 (mod 27) 别怕，本质还是 数字 × x ≡ 9，先在草稿纸上把 7¹⁶⁸ mod 27 化简。

复习第2章欧拉定理： gcd(7, 27) = 1。算 φ(27) = 27 × (1 - 1/3) = 18。 所以 7¹⁸ ≡ 1 (mod 27)。 168 ÷ 18 = 9 余 6，所以：

7¹⁶⁸ ≡ 7⁶ (mod 27) 算 7⁶ 得到 10。（计算过程略，参考上一章平方表）

方程瞬间变成：

12 × 10 x ≡ 9 (mod 27) 120 x ≡ 9 (mod 27) 12 x ≡ 9 (mod 27) ← 这不就变成上一节的基础题了吗？接着走 4 步法就行。

五、中国剩余定理（CRT）：“滚雪球”合并法 ​

遇到一组方程，模数互素（比如 5, 11, 17）：

x ≡ 2 (mod 5) x ≡ 5 (mod 11) x ≡ 3 (mod 17)

考场救命策略：千万别背书上的大公式！

书上教你算 Mi,Mi−1 然后求和。那条公式又长又容易算错。 请一定要用“代入替换法（滚雪球法）”！ 一次合并两个方程，绝对稳。

手把手“滚雪球”例题 ​

第一步：从第1个方程变出个 t

x ≡ 2 (mod 5) 可以写成：x = 2 + 5t

第二步：把 x 塞进第 2 个方程

(2 + 5t) ≡ 5 (mod 11) 5t ≡ 3 (mod 11) (求 5 在模 11 的逆元是 9)： t ≡ 3 × 9 = 27 ≡ 5 (mod 11) 所以 t = 5 + 11k

第三步：把 t 塞回 x 里（雪球滚大了）

x = 2 + 5(5 + 11k) = 2 + 25 + 55k = 27 + 55k(到这里，前两个方程已经合并成了 x ≡ 27 (mod 55) )

第四步：把新 x 塞进第 3 个方程

(27 + 55k) ≡ 3 (mod 17) 先降维化简（27 mod 17 = 10，55 mod 17 = 4）： 10 + 4k ≡ 3 (mod 17) 4k ≡ -7 ≡ 10 (mod 17) (求 4 在模 17 的逆元是 13)： k ≡ 10 × 13 = 130 ≡ 11 (mod 17)

第五步：收尾，得到最终结果 取特解 k = 11 代回 x：

x = 27 + 55 × 11 = 27 + 605 = 632 最终模数是三个模数的乘积：5 × 11 × 17 = 935。 所以答案：x ≡ 632 (mod 935)。

六、CRT 的预处理（陷阱题） ​

题目不给你纯净的 x ≡，而是给了：

5x ≡ 3 (mod 17) 4x ≡ 6 (mod 11)

破解法：急什么，先各自解出 x！

  • 把第 1 个方程解了，得到 x ≡ 4 (mod 17)
  • 把第 2 个方程解了，得到 x ≡ 7 (mod 11) 然后拿纯净版的这两个方程，用上面的“滚雪球”法继续做。

七、二元一次同余方程组 ​

跟初中学的二元一次方程组一模一样（代入消元法），唯一区别就是每一步加减乘除都要记得模 m。

3x + y ≡ 7 (mod 23) x + 2y ≡ 6 (mod 23)

从第一个方程提 y：y ≡ 7 - 3x 代入第二个：x + 2(7 - 3x) ≡ 6 整理得到：-5x ≡ -8 (mod 23)，也就是 5x ≡ 8 (mod 23)。 求 5 的逆元（是 14），两边乘 14 解出 x = 20。 再代回去解出 y 即可。没有任何新知识点。

🚀 本章做题速查表（考前 5 分钟必看） ​

看到什么立刻想
求 a⁻¹ mod m先看 gcd(a,m)=1；再用表格法凑出 ax+my=1。
问你 ax ≡ b 有没有解算 d=gcd(a,m)，看右边的 b 能不能被 d 整除。
解大题 ax ≡ b除以 d（别忘除模数） → 求逆元乘过去 → 扩出 d 个解。
系数里有逆天大指数老实点，先用费马/欧拉定理把系数化简。
多个同余方程组CRT 滚雪球代入法：变出 t → 代入 → 解出 t → 变出 k → ...

☠️ 历年期末最惨烈翻车现场 ​

  1. 上来就干不看路：解方程前居然不先算 d = gcd(a, m)。遇到无解的题，白算了一整面草稿纸。
  2. 大瘦身忘了模数：15x ≡ 5 (mod 20)，除以 5 变成 3x ≡ 1 (mod 20)... 兄弟，模数 20 也要除以 5 变成 4 啊！
  3. 只有一个解：算出一个 x0 直接交卷。题目可是有 d 个解的！少写几个直接扣一半分。
  4. 背错 CRT 巨型公式：听话，老老实实用“滚雪球替换法”，全程小数字计算，绝对不会错。

自测题（没做对别进考场） ​

  1. 求 7⁻¹ mod 26。（小数字可以尝试凑数法，比如 7×4=28 没用，那 7×? 能凑出差 1 的？）
  2. 判断 12x ≡ 4 (mod 15) 有解吗？
  3. 解 91x ≡ 35 (mod 161)。（必练重点，考查4步法和补齐解）
  4. 用滚雪球法解方程组：x ≡ 1 (mod 3)，x ≡ 2 (mod 5)。

自测答案 ​

  1. 凑数：7×15 = 105 = 26×4 + 1，所以 7⁻¹ ≡ 15 (mod 26)。（用表格法算也是 15）
  2. gcd(12, 15) = 3，3 不能整除 4 → 无解。
  3. d = gcd(91, 161) = 7，7 能整除 35。全体除以 7 得 13x ≡ 5 (mod 23)。求得 13 的逆元是 16。两边乘 16 得 x ≡ 80 ≡ 11 (mod 23)。d=7，一共 7 个解，每次加 23：x ≡ 11, 34, 57, 80, 103, 126, 149 (mod 161)。
  4. 第一个方程设 x = 1 + 3t，代入第二个：1 + 3t ≡ 2 → 3t ≡ 1 (mod 5)。3 的逆元是 2，所以 t ≡ 2。x = 1 + 3×2 = 7 (mod 15)。
最近更新