信息安全数学基础复习

第一章 整除与同余

1.1 整除

研究整数之间最基础的关系。

• 定义：$b|a⟺a=bq$。
• 重要性质：
  • 传递性：若 $a|b$ 且 $b|c$，则 $a|c$。
  • 线性组合性质：若 $d|a$ 且 $d|b$，则对于任意整数 $x,y$，有 $d\mid (ax+by)$。
• 带余除法：$a=bq+r,0\le r<b$。

1.2 最大公约数 (GCD & LCM)

解同余方程的关键工具。

• 欧几里得算法 (辗转相除法)：
  • 核心递归式：$(a,b)=(b,a\mathrm{mod}b)$。
• 扩展欧几里得算法 (Extended Euclidean)：
  • 目标：求解贝祖等式 $sa+tb=(a,b)$。
  • 应用：用于计算模逆元。若 $(a,m)=1$，则 $s$ 即为 $a$ 模 $m$ 的逆元。

1.3 素数与分解

整数的原子结构。

• 算术基本定理：每个大于 1 的整数 $n$ 都可以唯一分解为素数的乘积：$n=p_1^{{\alpha }_1}\cdots p_k^{{\alpha }_k}$。
• 判定互素的充要条件：$(a,b)=1⟺\exists u,v,ua+vb=1$。用于证明！
  • 互素性质：若 $c|ab$ 且 $(c,a)=1$，则 $c|b$。
  • 若 $a|c,b|c$ 且 $(a,b)=1$，则 $ab|c$。
• 埃拉托色尼筛法：一种通过迭代剔除素数倍数来生成素数表的算法。

1.4 同余体系

• 定义：若 $m\mid (a-b)$，则 $a\equiv b(\mathrm{mod}m)$。
• 性质：同余关系是等价关系（自反、对称、传递），且保持加法与乘法运算。

---

第二章 群

2.1 群的定义

带有运算的集合，满足特定的代数约束。

群 $G$ 是定义了乘法运算的非空集合，满足四条公理：

1. 封闭性：$\forall a,b\in G⟹ab\in G$。
2. 结合律：$(ab)c=a(bc)$。
3. 单位元：存在 $e$ 使得 $ea=ae=a$。
4. 逆元：对于任意 $a$，存在 $b$ 使得 $ab=ba=e$。

2.2 子群 (Subgroups)

群 $G$ 的非空子集 $H$，若对 $G$ 的运算也构成群，则为子群。

判定定理：

1. 两步法：(1) $ab\in H$ (封闭)；(2) $a^{-1}\in H$ (逆元封闭)。
2. 一步法：$\forall a,b\in H⟹a{b}^{-1}\in H$。
3. 有限集判定：若 $H$ 是有限非空子集，只需满足封闭性。

2.3 同构与同态

• 同态：保持运算结构的映射，$f(ab)=f(a)f(b)$。
  • 同态核：$Ker(f)=\{x\in G\mid f(x)=e^{\prime }\}$，核是 $G$ 的子群（且是正规子群）。
• 同构：双射的同态映射，记为 $G\cong G^{\prime }$。

---

第三章 循环群与群的结构

3.1 循环群

由单一生成元 $g$ 的幂次构成的群。

• 定义：$G=⟨g⟩=\{g^k\mid k\in \mathbb{Z}\}$。
• 元素的阶：使 $a^k=e$ 的最小正整数 $k$。
  • 计算公式：在 $n$ 阶循环群中，$|g^k|=\frac{n}{(n,k)}$。
• 生成元个数：$n$ 阶循环群共有 $\phi (n)$ 个生成元。

3.2 剩余类群

• $Z_m$：模 $m$ 的剩余类加法群，是 $m$ 阶循环群。
• 同构结论：任意 $n$ 阶循环群同构于 $Z_n$；任意无限循环群同构于整数加群 $Z$。

3.3 陪集与拉格朗日定理

揭示了子群与群阶数的整除关系。

• 陪集：$aH=\{ah\mid h\in H\}$。陪集构成了群的一个划分。
• 拉格朗日定理：有限群 $G$ 的子群 $H$ 的阶整除 $G$ 的阶，即 $|G|=k\cdot |H|$。
  • 推论：任意元素 $a$ 的阶整除 $|G|$；$a^{|G|}=e$。

3.4 正规子群与商群

• 正规子群 ($N⊴G$)：左陪集等于右陪集，即 $\forall a\in G,aN=Na$（或 $aN{a}^{-1}=N$）。
• 商群 ($G/N$)：由正规子群的所有陪集构成的群，运算为 $(aN)(bN)=(ab)N$。
• 自然同态：$f:G\to G/N,f(a)=aN$。

---

第四章 环 (Rings)

4.1 环与子环

双运算系统 $(R,+,\cdot )$。

• 定义：
  1. $(R,+)$ 是交换群（Abel群）。
  2. $(R,\cdot )$ 满足封闭性、结合律。
  3. 满足分配律：$a(b+c)=ab+ac$。
• 子环判定：子集 $S$ 对减法封闭 ($a-b\in S$) 且对乘法封闭 ($ab\in S$)。

4.2 整环、除环与域

环的层级结构。

• 整环：有单位元、交换、无零因子的环。
  • 零因子：$a\ne 0,b\ne 0$ 但 $ab=0$。
• 除环：非零元均可逆（构成乘法群）的环。
• 域 (Field)：交换的除环（如 $\mathbb{Q},\mathbb{R},GF(p)$）。

4.3 环同态与理想

• 理想 (Ideal)：环 $R$ 的加法子群 $I$，且具有吸入性（$r\in R,a\in I⟹ra\in I$）。
  • 理想之于环，相当于正规子群之于群（用于构造商环）。
• 主理想：由一个元素生成的理想 $(a)=\{ra\mid r\in R\}$。在 $\mathbb{Z}$ 中所有理想都是主理想 $(n)=n\mathbb{Z}$。

---

第六章 同余式

k k

6.1 剩余系与欧拉费马定理

• 完全剩余系：模 $m$ 的 $m$ 个代表元。
• 简化剩余系：模 $m$ 中与 $m$ 互素的代表元，个数为 $\phi (m)$。
• 欧拉定理：若 $(a,m)=1$，则 $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$。
• 费马小定理：若 $p$ 为素数，则 $a^p\equiv a(\mathrm{mod}p)$。

6.2 一次同余式

方程 $ax\equiv b(\mathrm{mod}m)$。

• 判定：$d=(a,m)$，若 $d\mid b$ 则有 $d$ 个解；否则无解。
• 解法：化简为 $a^{\prime }x\equiv b^{\prime }(\mathrm{mod}{m}^{\prime })$，利用扩展欧几里得求逆元求解。

6.3 中国剩余定理 (CRT)

解方程组 $x\equiv b_i(\mathrm{mod}{m}_i)$（$m_i$ 两两互素）。

• 公式： $x\equiv {\sum }_{i=1}^k{M}_i{M}_i^{-1}{b}_i(\mathrm{mod}m)$ 其中 $M_i=m/m_i$，$M_i^{-1}$ 是 $M_i$ 模 $m_i$ 的逆元。

6.4 素数模同余式

• 威尔逊定理：$(p-1)!\equiv -1(\mathrm{mod}p)$。
• 拉格朗日定理（同余式）：模 $p$ 的 $n$ 次同余式至多有 $n$ 个解。

---

RSA算法

第七章 平方剩余

7.1 概念与判定

• 定义：$x^2\equiv a(\mathrm{mod}p)$ 有解，则 $a$ 是模 $p$ 的平方剩余。
• 欧拉判别法：$a^{\frac{p-1}{2}}\equiv (\frac{a}{p})(\mathrm{mod}p)$。

7.2 勒让德符号 $(\frac{a}{p})$

• 计算法则：
  1. 取模：$(\frac{a}{p})=(\frac{a\mathrm{mod}p}{p})$。
  2. 乘积：$(\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p})$。
  3. 平方数：$(\frac{s^2}{p})=1$。
  4. 特殊值：
     • $(\frac{-1}{p})=(-1{)}^{\frac{p-1}{2}}$ （$p\equiv 1(\mathrm{mod}4)$ 为正）。
     • $(\frac{2}{p})=(-1{)}^{\frac{p^2-1}{8}}$ （$p\equiv \pm 1(\mathrm{mod}8)$ 为正）。
  5. 二次互反律： $(\frac{p}{q})(\frac{q}{p})=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}$ (口诀：双三变号，其余不变)。

7.3 雅可比符号k k

• 推广到合数模 $m$，计算规则（包括互反律）与勒让德符号一致。
• 注意：$(\frac{a}{m})=1$ 不代表 $a$ 一定是平方剩余。

---

第八章 原根与离散对数

8.1 指数与原根

• 指数 (Order)：使 $a^d\equiv 1(\mathrm{mod}m)$ 的最小正整数 $d$。
• 原根：阶等于 $\phi (m)$ 的元素。
• 存在性：仅 $2,4,p^k,2p^k$ 有原根（参见 2. 存在性定理）。
• 判定必杀技： $g$ 是原根 $⟺$ 对 $\phi (m)$ 的所有素因子 $q$，都有 $g^{\frac{\phi (m)}{q}}\not\equiv 1(\mathrm{mod}m)$。

8.2 离散对数

• 定义：若 $g$ 是原根，$a\equiv g^{\gamma }(\mathrm{mod}m)$，则 $in{d}_{g}a=\gamma$。
• 性质：运算在模 $\phi (m)$ 下进行。
  • $ind(ab)\equiv ind(a)+ind(b)$
  • $ind(a^n)\equiv n\cdot ind(a)$

课后习题

整除与同余

1. 证明：若 a,b 互素，则 $a^n$ 与 $b^n$ 互素
   • 反证法！假设二者不互素，有素因子

证明通法

面对这类数论证明题时，可以遵循以下步骤来建立思路：

• 整除性 ($\mathbf{a}\mid \mathbf{b}$)： 意味着存在一个整数 $k$，使得 $b=ak$。

• 互素 ($(\mathbf{a},\mathbf{b})=1$)： 意味着 $a$ 和 $b$ 的最大公因数是 1。

• 最大公因数 ($(\mathbf{a},\mathbf{b})$)：

  • $\text{GCD}$ 的基本性质： 任何整除 $ja$ 和 $b$ 的数也能整除 $(a,b)$。

  • 裴蜀定理 (Bézout’s identity)： 存在整数 $x,y$，使得 $(a,b)=ax+by$。如果 $(a,b)=1$，则 $ax+by=1$。

• 素数分解 (Fundamental Theorem of Arithmetic)： 任何大于 1 的整数 $n$ 都可以唯一地分解成素数的乘积 $n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$。（这是解决涉及指数和整除性问题的最强大工具。）

2. 对哪些模 $m$，$32\equiv 11(\mathrm{mod}m)$、$1000\equiv -1(\mathrm{mod}m)$ 同时成立？
   • 将同余式转换为整除式
3. 特殊的同余关系：
   • $10\equiv 1(\mathrm{mod}3)$
   • $10\equiv 1(\mathrm{mod}9)$

考前复习

🎯 模块一：整除与最大公约数 (基础中的基础)

核心考点：扩展欧几里得算法 (Extended Euclidean Algorithm) 这是整个计算题的基石，求逆元全靠它，算错一步全盘皆输。

1. 必考题型：求 $\gcd (a,b)$ 并通过 $s\cdot a+t\cdot b=\gcd (a,b)$ 求系数 $s,t$

• 做题步骤：
  1. 列表法/辗转相除法：算出余数，直到余数为0。
  2. 回代法：从倒数第二个余数（即gcd）开始，将余数表示为商和被除数的形式，一层层往回带。
• 易错点：回代时的正负号！建议在草稿纸上把每一行的 $r_i=r_{i-2}-q_i\cdot r_{i-1}$ 写清楚。

2. 算术基本定理

• 概念：任何大于1的整数都能唯一分解为素数的乘积。
• 标准分解式：$n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$。
• 应用：计算 $\gcd$ 和 $\text{lcm}$，以及后续计算欧拉函数 $\phi (n)$。

---

🎯 模块二：同余式求解 (计算量最大)

1. 求解线性同余式 $ax\equiv b(\mathrm{mod}n)$

• 有解判定：只有当 $d=\gcd (a,n)$ 能整除 $b$ 时 ($d|b$)，方程才有解。
• 解的个数：如果有解，在模 $n$ 意义下有 $d$ 个解。
• 做题步骤：
  1. 计算 $d=\gcd (a,n)$。如果不整除 $b$，直接写“无解”。
  2. 化简：两边同除以 $d$，得到 $a^{\prime }x\equiv b^{\prime }(\mathrm{mod}{n}^{\prime })$。
  3. 求逆：利用扩展欧几里得求 $a^{\prime }$ 模 $n^{\prime }$ 的逆元 $(a^{\prime }{)}^{-1}$。
  4. 特解：$x_0=(a^{\prime }{)}^{-1}\cdot b^{\prime }(\mathrm{mod}{n}^{\prime })$。
  5. 通解（不要漏）：$x\equiv x_0+k\cdot \frac{n}{d}(\mathrm{mod}n)$，其中 $k=0,1,\dots ,d-1$。

2. 中国剩余定理 (CRT)

• 题型：解同余方程组 $x\equiv a_i(\mathrm{mod}{m}_i)$，其中 $m_i$ 两两互素。
• 万能公式： $x\equiv {\sum }_{i=1}^k{M}_i{M}_i^{\prime }{a}_i(\mathrm{mod}M)$
  • $M=m_1\times \cdots \times m_k$
  • $M_i=M/m_i$
  • $M_i^{\prime }$ 是 $M_i$ 模 $m_i$ 的逆元（即 $M_i{M}_i^{\prime }\equiv 1(\mathrm{mod}{m}_i)$）
• 扩展考点：如果 $m_i$ 不互素怎么办？
  • 策略：拆分成素数幂，检测矛盾；或者用两两合并法求解。

---

🎯 模块三：核心定理与函数 (概念与证明题高发区)

1. 费马小定理与欧拉定理

• 费马小定理：$p$ 为素数，$\gcd (a,p)=1\Rightarrow a^{p-1}\equiv 1(\mathrm{mod}p)$。
• 欧拉定理：$\gcd (a,n)=1\Rightarrow a^{\phi (n)}\equiv 1(\mathrm{mod}n)$。
• 应用场景：
  • 降幂：计算 $a^k(\mathrm{mod}n)$ 时，指数 $k$ 可以先对 $\phi (n)$ 取模。（注意：底数 $a$ 和 $n$ 必须互素！如果不互素怎么处理？参考你刚才问的 RSA 证明思路）。
  • 求逆元：$a^{-1}\equiv a^{\phi (n)-1}(\mathrm{mod}n)$。

2. 欧拉函数 $\phi (n)$

• 计算公式：$\phi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots$
  • 特别地，若 $n=pq$，$\phi (n)=(p-1)(q-1)$。
• 性质：积性函数。若 $\gcd (m,n)=1$，则 $\phi (mn)=\phi (m)\phi (n)$。

3. 威尔逊定理 (Wilson)

• $(p-1)!\equiv -1(\mathrm{mod}p)$。
• 考法：通常用于证明题，或者简化阶乘相关的同余式。

---

🎯 模块四：二次剩余 (最容易算错符号)

1. 勒让德符号 (Legendre Symbol) $(\frac{a}{p})$

• 定义：判断 $a$ 是否为模 $p$ 的二次剩余。
• 欧拉判别法：$(\frac{a}{p})\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p)$。
  • 算出来是 $1$：有二次剩余。
  • 算出来是 $-1$：无二次剩余。

2. 雅可比符号 (Jacobi Symbol) $(\frac{a}{n})$

• 注意：$n$ 是奇合数。$(\frac{a}{n})=1$ 不代表 $a$ 一定是 $n$ 的二次剩余（除非 $n$ 是素数）。
• 计算重灾区 - 二次互反律：
  • 法则 1 (倒数)：$(\frac{q}{p})=(\frac{p}{q})\cdot (-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}$。
    • 口诀：只有当 $p,q$ 都是“模4余3”的数时，翻转加负号；否则直接翻转。
  • 法则 2 (-1)：$(\frac{-1}{p})=(-1{)}^{\frac{p-1}{2}}$。 ($p\equiv 1(\mathrm{mod}4)$ 为正，$\equiv 3(\mathrm{mod}4)$ 为负)。
  • 法则 3 (2)：$(\frac{2}{p})=(-1{)}^{\frac{p^2-1}{8}}$。 ($p\equiv 1,7(\mathrm{mod}8)$ 为正，$p\equiv 3,5(\mathrm{mod}8)$ 为负)。

3. 模 $p$ 平方根求解 (Tonelli-Shanks 即使不考大题，也要会简单情况)

• 若 $p\equiv 3(\mathrm{mod}4)$，且 $a$ 是二次剩余，则 $x\equiv \pm a^{\frac{p+1}{4}}(\mathrm{mod}p)$。（这个公式最好背下来，经常考）。

---

🎯 模块五：原根与指数

1. 阶 (Order)

• ${\delta }_n(a)$ 是使 $a^k\equiv 1(\mathrm{mod}n)$ 成立的最小正整数 $k$。
• 性质：$k$ 一定整除 $\phi (n)$。

2. 原根 (Primitive Root)

• 定义：若 $g$ 的阶等于 $\phi (n)$，则 $g$ 是原根。
• 存在条件：只有 $n=2,4,p^k,2p^k$ ($p$是奇素数) 时才有原根。
• 找原根方法：
  1. 算出 $\phi (n)$。
  2. 列出 $\phi (n)$ 的所有素因子 $q_i$。
  3. 验证 $g^{\phi (n)/q_i}\not\equiv 1(\mathrm{mod}n)$ 对所有 $q_i$ 是否成立。若都成立，就是原根。

---

🎯 模块六：RSA 专题 (你重点复习过)

1. 参数计算：
   • 选 $p,q$，算 $n=pq$。
   • 算 $\phi (n)=(p-1)(q-1)$。
   • 选 $e$，算 $d=e^{-1}(\mathrm{mod}\phi (n))$。
2. 加解密：
   • 加密：$c\equiv m^e(\mathrm{mod}n)$。
   • 解密：$m\equiv c^d(\mathrm{mod}n)$。
3. 安全性分析：
   • 共模攻击（两个人用同样的 $n$）。
   • 低加密指数攻击（$e$ 太小）。
4. 证明题：即你刚才搞懂的“$m,n$ 不互素时的解密证明”，利用 CRT 或欧拉/费马定理分别在模 $p$ 和模 $q$ 下证明。

---

🎯 模块七：群论基础 (概念判定是核心)

1. 群 (Group) 的判定

• 四大公理（必须背熟，证明题起手式）：
  1. 封闭性：$a,b\in G\Rightarrow a\cdot b\in G$。
  2. 结合律：$(a\cdot b)\cdot c=a\cdot (b\cdot c)$。
  3. 单位元：存在 $e$，使得 $a\cdot e=e\cdot a=a$。
  4. 逆元：对任意 $a$，存在 $a^{-1}$，使得 $a\cdot a^{-1}=e$。
• 阿贝尔群 (Abel)：满足上述 4 点 + 交换律 ($a\cdot b=b\cdot a$)。

2. 核心定理：拉格朗日定理 (Lagrange’s Theorem)

• 结论：有限群 $G$ 的子群 $H$ 的阶 $|H|$ 一定能整除群的阶 $|G|$。
• 推论：
  • 群中任意元素 $a$ 的阶 $k$ 一定整除群的阶 $|G|$。（即 $a^{|G|}=e$）。
  • 素数阶群一定是循环群，且没有非平凡子群。

3. 循环群 (Cyclic Group)

• 定义：由一个元素 $g$ 生成的群，$G=\{g^k\mid k\in \mathbb{Z}\}$。
• 生成元个数：若 $|G|=n$，则生成元有 $\phi (n)$ 个。
• 子群性质：循环群的子群也是循环群。

---

🎯 模块八：离散对数与指数 (DLP)

这一块其实就是“原根”的进阶应用，对应密码学中的 ElGamal。

1. 指数 (Index) / 离散对数

• 定义：如果 $g$ 是模 $n$ 的原根，且 $a\equiv g^k(\mathrm{mod}n)$，那么 $k$ 称为 $a$ 以 $g$ 为底的指数（即离散对数），记作 ${\text{ind}}_g(a)=k$。
• 运算法则（类比普通对数，但要模 $\phi (n)$）：
  • $\text{ind}(a\cdot b)\equiv \text{ind}(a)+\text{ind}(b)(\mathrm{mod}\phi (n))$
  • $\text{ind}(a^k)\equiv k\cdot \text{ind}(a)(\mathrm{mod}\phi (n))$
• 解题应用：将 $x^k\equiv a(\mathrm{mod}n)$ 这种高次同余式，转化为线性同余式求解： $k\cdot \text{ind}(x)\equiv \text{ind}(a)(\mathrm{mod}\phi (n))$

2. 离散对数难题 (DLP)

• 核心：已知 $g,x,p$，算 $y\equiv g^x(\mathrm{mod}p)$ 很容易；但已知 $g,y,p$，反推 $x$ 极难。
• BSGS 算法 (大步小步法)：
  • 虽然手算考大数的概率低，但原理要知道：通过“空间换时间”，将复杂度从 $O(n)$ 降到 $O(\sqrt{n})$。
  • 如果你看过课件里的 $\sqrt{n}$ 查表法，记得那个思路。

💡 考前 5 分钟 Check List

1. 计算器：是否允许带？如果不能，练一下手算多位数乘除。
2. 逆元：看到分数 $\frac{a}{b}(\mathrm{mod}n)$ 马上反应过来是 $a\cdot b^{-1}(\mathrm{mod}n)$。
3. 负数取模：$-5(\mathrm{mod}7)=2$。做题过程中出现负数，立刻加模数变正，防止后续出错。
4. 特殊数字：
   • $\phi (p)=p-1$
   • $\gcd (a,b)=\gcd (b,a(\mathrm{mod}b))$
   • $1$ 的逆元是 $1$，$n-1$ 的逆元是 $n-1$ (即 $-1\equiv -1$)。
   • $N\equiv a_k+a_{k-1}+\cdots +a_1+a_0(\mathrm{mod}3)$