网络安全数学基础-题目汇总

AI 分析作业中的考点

整除中的考点

1. 整除的性质与判定

知识要点

• 线性组合性质：若 $a\mid b$ 且 $a\mid c$，则对任意整数 $x,y$，$a\mid (xb+yc)$。
• 整除的大小限制：设 $b\ne 0$，那么 $a\mid b⟹|a|\le |b|$。
• 互素转移性：若 $(a,b)=1$ 且 $a\mid bc$，则 $a\mid c$。

针对性习题

• 【判断】 若 $a\mid c$ 且 $b\mid c$，则 $ab\mid c$。 ( )
  • 解析：错误。例如 $6\mid 12$ 且 $4\mid 12$，但 $24\nmid 12$。必须满足 $(a,b)=1$ 结论才成立。
• 【判断】 对于任意整数 $n$，$gcd(n,n+1)=1$ 恒成立。 ( )
  • 解析：正确。根据性质 $(a,b)=(a,b+ax)$，则 $(n,n+1)=(n,n+1-n)=(n,1)=1$。

2. 欧几里得算法与最大公约数 (GCD)

知识要点

• 辗转相除法：$gcd(a,b)=gcd(b,a\mathrm{mod}b)$。
• 最小公倍数公式：$[a,b]=\frac{|ab|}{(a,b)}$。
• 多参数计算：$(a,b,c)=((a,b),c)$。

针对性习题

• 【计算】 计算 $gcd(240,46)$。
  • 过程：$240=5\times 46+10$；$46=4\times 10+6$；$10=1\times 6+4$；$6=1\times 4+2$；$4=2\times 2+0$。
  • 结果：2
• 【填空】 已知 $a=12,b=18$，则其最小公倍数 $[a,b]=$ ______。
  • 解析：$(12,18)=6$。根据公式 $\frac{12\times 18}{6}=36$。

3. 裴蜀定理与扩展欧几里得 (Exgcd)

知识要点

• 裴蜀定理：存在整数 $x,y$ 使得 $ax+by=gcd(a,b)$ 成立。
• 线性方程解的判定：方程 $ax+by=c$ 有整数解当且仅当 $gcd(a,b)\mid c$。
• 逆元基础：当 $gcd(a,n)=1$ 时，$ax\equiv 1(\mathrm{mod}n)$ 有解，可用扩展欧几里得求出。

针对性习题

• 【判断】 方程 $14x+21y=5$ 有整数解。 ( )
  • 解析：错误。$(14,21)=7$，但 $7\nmid 5$，根据裴蜀定理该方程无解。
• 【计算】 求一组整数 $(x,y)$ 使得 $17x+5y=1$。
  • 过程：
    1. $17=3\times 5+2⟹2=17-3\times 5$
    2. $5=2\times 2+1⟹1=5-2\times 2$
    3. 代入：$1=5-2\times (17-3\times 5)=-2\times 17+7\times 5$。
  • 结果：$x=-2,y=7$

4. 素数与算术基本定理

知识要点

• 唯一分解：任何正整数 $a$ 都能唯一分解为 $a=p_1{p}_2\cdots p_s$。
• 费马数：$F_n=2^{2^n}+1$。前五个 $F_0\dots F_4$ 为素数，但 $F_5$ 是合数。
• 梅森素数：$M_p=2^p-1$。
• Blum 整数：两个 $4k+3$ 型素数的乘积。

针对性习题

• 【判断】 所有的费马数都是素数。 ( )
  • 解析：错误。$F_5$ 不是素数。
• 【填空】 素数定理指出，当 $x\to \infty$ 时，小于等于 $x$ 的素数个数 $\pi (x)\approx$ ______。
  • 结果：$\frac{x}{\ln x}$。

同余中的考点

1. 同余运算与模逆元计算

知识要点

• 同余性质：若 $a\equiv b(\mathrm{mod}m)$，则 $(a,m)=(b,m)$。
• 消去律：在 $ac\equiv bc(\mathrm{mod}n)$ 中，只有当 $(c,n)=1$ 时，才能消去 $c$ 得到 $a\equiv b(\mathrm{mod}n)$。
• 模逆元：$ax\equiv 1(\mathrm{mod}m)$ 有解的充要条件是 $(a,m)=1$。

针对性习题

• 【计算】 求 $7$ 模 $26$ 的逆元。

  • 过程：即解 $7x\equiv 1(\mathrm{mod}26)$。

    $26=3\times 7+5⟹5=26-3\times 7$

    $7=1\times 5+2⟹2=7-5=7-(26-3\times 7)=4\times 7-26$

    $5=2\times 2+1⟹1=5-2\times 2=(26-3\times 7)-2\times (4\times 7-26)=3\times 26-11\times 7$。

  • 结果：$-11\equiv 15(\mathrm{mod}26)$。逆元为 $15$。

• 【判断】 若 $ak\equiv bk(\mathrm{mod}m)$，则 $a\equiv b(\mathrm{mod}m)$。 ( )
  • 解析：错误。应该是 $a\equiv b(\mathrm{mod}\frac{m}{(k,m)})$。

2. 线性同余方程（必考大题）

知识要点

• 解的判定：$ax\equiv b(\mathrm{mod}n)$ 有解当且仅当 $d=\gcd (a,n)\mid b$。
• 解的数量：若有解，则在模 $n$ 意义下恰有 $d$ 个解。

针对性习题

• 【计算】 求解方程 $6x\equiv 3(\mathrm{mod}9)$。

  • 过程：$gcd(6,9)=3$。因为 $3\mid 3$，方程有 $3$ 个解。

    先化简方程：两边除以 $3$，同时模数也除以 $3$，得 $2x\equiv 1(\mathrm{mod}3)$。

    显然 $x_0=2$ 是一个解。

    通解为 $x\equiv 2+k\cdot (\frac{9}{3})(\mathrm{mod}9)$，即 $x_1=2,x_2=5,x_3=8$。

  • 结果：$x\equiv 2,5,8(\mathrm{mod}9)$。

3. Euler 函数、Euler 定理与 Fermat 小定理

知识要点

• 欧拉函数公式：$\varphi (n)=n{\prod }_{i=1}^r(1-\frac{1}{p_i})$。
• Euler 定理：若 $(a,n)=1$，则 $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$。
• Fermat 小定理：若 $p$ 为素数且 $p\nmid a$，则 $a^{p-1}\equiv 1(\mathrm{mod}p)$。
• Wilson 定理：$p$ 为素数 $⟺(p-1)!\equiv -1(\mathrm{mod}p)$。

针对性习题

• 【计算】 计算 $\varphi (12)$。
  • 解析：$12=2^2\times 3$。$\varphi (12)=12(1-1/2)(1-1/3)=12\times 0.5\times 0.66=4$。
• 【计算】 求 $3^{100}(\mathrm{mod}13)$ 的余数。

  • 过程：$13$ 是素数，由 Fermat 小定理，$3^{12}\equiv 1(\mathrm{mod}13)$。

    $100=12\times 8+4$。

    所以 $3^{100}\equiv (3^{12}{)}^8\cdot 3^4\equiv 1^8\cdot 81(\mathrm{mod}13)$。

    $81=6\times 13+3$。

  • 结果：$3$。

4. 孙子定理（中国剩余定理 CRT）

知识要点

求解方程组 $\{\begin{array}{l}x\equiv a_1(\mathrm{mod}{n}_1)\\ x\equiv a_2(\mathrm{mod}{n}_2)\end{array}$。

1. $M=n_1{n}_2$。
2. $M_1=n_2,M_2=n_1$。
3. 求 $M_1\mathrm{mod}{n}_1$ 的逆元 $M_1^{-1}$，求 $M_2\mathrm{mod}{n}_2$ 的逆元 $M_2^{-1}$。
4. $x\equiv a_1{M}_1{M}_1^{-1}+a_2{M}_2{M}_2^{-1}(\mathrm{mod}M)$。

针对性习题

• 【计算】 解方程组 $\{\begin{array}{l}x\equiv 2(\mathrm{mod}3)\\ x\equiv 3(\mathrm{mod}5)\end{array}$。

  • 过程：$M=15$。

    $M_1=5,M_2=3$。

    $5x\equiv 1(\mathrm{mod}3)⟹2x\equiv 1(\mathrm{mod}3)⟹M_1^{-1}=2$。

    $3x\equiv 1(\mathrm{mod}5)⟹M_2^{-1}=2$。

    $x\equiv 2\cdot 5\cdot 2+3\cdot 3\cdot 2=20+18=38(\mathrm{mod}15)$。

  • 结果：$x\equiv 8(\mathrm{mod}15)$。

5. 快速幂算法

知识要点

• 核心逻辑：通过二进制分解指数，每一步进行“平方”或“平方并乘以底数”的操作。

针对性习题

• 【判断】 使用快速幂计算 $a^{13}(\mathrm{mod}n)$ 时，一共需要进行多少次乘法（含平方）？
  • 解析：$13=(1101{)}_2$。从最高位到最低位：平方（$i=2$），乘；平方（$i=1$）；平方（$i=0$），乘。加上初始状态，总计操作逻辑清晰。

二次剩余中的考点

1. Legendre 符号与 Jacobi 符号的计算（核心大题）

知识要点

• Euler 判别法：$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p)$。
• 完全积性：$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$。
• 三大判别准则：
  1. $-1$ 判别（模 4）：$\left(\frac{-1}{n}\right)=1⟺n\equiv 1(\mathrm{mod}4)$。
  2. $2$ 判别（模 8）：$\left(\frac{2}{n}\right)=1⟺n\equiv 1,7(\mathrm{mod}8)$。
  3. 二次互反律：若 $p,q$ 为奇素数，$\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)$，除非 $p\equiv q\equiv 3(\mathrm{mod}4)$（此时要变号）。
• Jacobi 符号特点：分母可为合数，计算时不需分解质因数即可翻转，但 $\left(\frac{a}{n}\right)=1$ 不代表一定有解。

针对性习题

• 【计算】 计算 Legendre 符号 $\left(\frac{29}{97}\right)$。
  • 过程：
    1. 因为 $97\equiv 1(\mathrm{mod}4)$，直接翻转：$\left(\frac{29}{97}\right)=\left(\frac{97}{29}\right)$。
    2. 取模：$97÷29=3\dots 10⟹\left(\frac{10}{29}\right)$。
    3. 拆分：$\left(\frac{2}{29}\right)\left(\frac{5}{29}\right)$。
    4. 查表/翻转：$29\equiv 5(\mathrm{mod}8)⟹\left(\frac{2}{29}\right)=-1$；$\left(\frac{5}{29}\right)=\left(\frac{29}{5}\right)=\left(\frac{4}{5}\right)=1$。
  • 结果：$(-1)\times 1=-1$。

2. 二次剩余的判定与性质

知识要点

• 数量分布：模 $p$ 的缩系中，二次剩余与非剩余各占一半，即 $\frac{p-1}{2}$ 个。
• Blum 数性质：若 $n=pq$ 为 Blum 数且 $\left(\frac{a}{n}\right)=1$，则 $a$ 或 $-a$ 中必有一个是模 $n$ 的二次剩余。
• 平方根求解：若 $p$ 是 Blum 素数（$4k+3$），$a$ 的平方根为 $\pm a^{\frac{p+1}{4}}(\mathrm{mod}p)$。

针对性习题

• 【填空】 模 11 的二次剩余共有 ______ 个。
  • 解析：$\frac{11-1}{2}=5$ 个。具体为 $1^2,2^2,3^2,4^2,5^2(\mathrm{mod}11)\to 1,4,9,5,3$。
• 【判断】 若 Jacobi 符号 $\left(\frac{a}{n}\right)=-1$，则 $a$ 一定不是模 $n$ 的二次剩余。 ( )
  • 答案：正确。

3. 二次同余方程的解法

知识要点

• 一般二次方程：$a{x}^2+bx+c\equiv 0(\mathrm{mod}p)$。利用配方法转化为 $y^2\equiv \Delta (\mathrm{mod}p)$。
• 解的个数：
  • 模奇素数 $p$：有 $1+\left(\frac{\Delta }{p}\right)$ 个解。
  • 模 $2^l$（重要！）：$x^2\equiv n(\mathrm{mod}{2}^l)$，若 $l\ge 3$，有解条件是 $n\equiv 1(\mathrm{mod}8)$，解数为 4 个。
  • 模合数 $m$：各质因子幂次分量的解数之积。

针对性习题

• 【计算】 方程 $x^2\equiv 1(\mathrm{mod}8)$ 的解有哪些？
  • 结果：$1,3,5,7(\mathrm{mod}8)$（共 4 个，验证：$1^2,3^2,5^2,7^2$ 模 8 均余 1）。
• 【简答】 如何求 $x^2\equiv a(\mathrm{mod}15)$ 的解数？

  • 过程：分解为 $x^2\equiv a(\mathrm{mod}3)$ 和 $x^2\equiv a(\mathrm{mod}5)$。

    若两边均有 2 个解，总解数为 $2\times 2=4$ 个。

4. 考前手算技巧：平方剩余速查表

在考试中，如果模数 $p$ 较小（如 7, 11, 13），直接列举平方数比用公式快

原根和指数的考点

1. 阶（Order）的计算与性质

知识要点

• 定义：使得 $a^n\equiv 1(\mathrm{mod}m)$ 成立的最小正整数 $n$ 称为 $a$ 模 $m$ 的阶，记为 ${\delta }_m(a)$。
• 核心整除性质：若 $a^k\equiv 1(\mathrm{mod}m)$，则 ${\delta }_m(a)\mid k$。推论：${\delta }_m(a)\mid \phi (m)$。
• 幂的阶公式：${\delta }_m(a^k)=\frac{{\delta }_m(a)}{(k,{\delta }_m(a))}$。

针对性习题

• 【填空】 已知 $a$ 模 $m$ 的阶为 12，则 $a^8$ 模 $m$ 的阶为 ______。
  • 解析：${\delta }_m(a^8)=\frac{12}{(8,12)}=\frac{12}{4}=3$。
• 【判断】 若 $(a,m)=1$，则 $a,a^2,\dots ,a^{{\delta }_m(a)}$ 模 $m$ 两两不同余。 ( )
  • 答案：正确。

2. 原根的判定与存在性

知识要点

• 存在性：模 $n$ 有原根当且仅当 $n=1,2,4,p^l,2p^l$（$p$ 为奇素数）。
• 判定法（素因子排除法）：设 $q_1,q_2,\dots$ 是 $\phi (m)$ 的所有质因子。若对所有 $q_i$，均有 $a^{\frac{\phi (m)}{q_i}}\not\equiv 1(\mathrm{mod}m)$，则 $a$ 是模 $m$ 的原根。
• 原根个数：若模 $m$ 有原根，则共有 $\phi (\phi (m))$ 个原根。

针对性习题

• 【判断】 模 12 存在原根。 ( )
  • 解析：错误。$12=2^2\times 3$，不符合 $2,4,p^l,2p^l$ 的形式。
• 【计算】 判定 2 是否为模 11 的原根。
  • 过程：$\phi (11)=10$，质因子为 2 和 5。
    1. 检查 $2^{10/2}=2^5=32\equiv 10\not\equiv 1(\mathrm{mod}11)$。
    2. 检查 $2^{10/5}=2^2=4\equiv 4\not\equiv 1(\mathrm{mod}11)$。
  • 结果：是原根。

3. 指数（离散对数）的运算

知识要点

• 定义：若 $g^k\equiv a(\mathrm{mod}n)$，则 $in{d}_{g}a=k$。
• 运算规律（类比对数）：
  1. $ind(ab)\equiv ind(a)+ind(b)(\mathrm{mod}\phi (n))$。
  2. $ind(a^m)\equiv m\cdot ind(a)(\mathrm{mod}\phi (n))$。
• 换底公式：$in{d}_{g_2}a\equiv in{d}_{g_1}a\cdot in{d}_{g_2}{g}_1(\mathrm{mod}\phi (n))$。

针对性习题

• 【计算】 在模 11 以原根 2 为底的指数系中，已知 $in{d}_{2}3=8$，求 $in{d}_{2}9(\mathrm{mod}10)$。
  • 解析：$in{d}_{2}9=in{d}_2{3}^2\equiv 2\cdot in{d}_{2}3=16\equiv 6(\mathrm{mod}10)$。
  • 结果：6。

4. 指数与阶的关系（常考综合计算）

知识要点

• 核心公式：${\delta }_n(a)=\frac{\phi (n)}{(in{d}_{g}a,\phi (n))}$。
  • 这个公式常用于：给出指数表，求某个元素的阶；或者反过来，已知阶求指数的公约数性质。

针对性习题

• 【填空】 设 $g$ 是模 $n$ 的原根，则 $in{d}_{g}a$ 与 $\phi (n)$ 互素是 $a$ 为原根的 ______ 条件。
  • 解析：充分必要条件。因为当 $(in{d}_{g}a,\phi (n))=1$ 时，${\delta }_n(a)=\frac{\phi (n)}{1}=\phi (n)$。

群中的考点

第一梯队：必考计算与定义（简单，必须拿分）

这类题目主要考查对“群”定义的直观理解，通常出现在选择题或填空题。

第1、2题：群的判定

• 【题目 1】 在整数集 $\mathbb{Z}$ 中定义运算“$\circ$”：$a\circ b=a+b-2$。证明：$\mathbb{Z}$ 关于运算“$\circ$”构成群。
• 【题目 2】 判断正整数集 ${\mathbb{N}}^{+}$ 关于运算 $a\circ b=a+b+ab$ 是否构成群。
• 套路与技巧： * 检查四要素： 封闭性、结合律、单位元、逆元。
  • 第1题关键： 单位元是 $2$（因为 $a+2-2=a$）。任意元素 $a$ 的逆元是 $4-a$。
  • 第2题关键： 不是群。虽然满足结合律，但不存在单位元 $e\in {\mathbb{N}}^{+}$ 使得 $a+e+ae=a$（此时 $e(1+a)=0⟹e=0$，但 $0\notin {\mathbb{N}}^{+}$）。

第7、8题：子群与生成元（极高频）

• 【题目 7 & 8】 写出 ${\mathbb{Z}}_{11}^{\ast }$（或 ${\mathbb{Z}}_{12}$）的所有子群及其生成元。
• 核心套路：
  • 加法群 ${\mathbb{Z}}_n$： 子群由 $n$ 的约数 $d$ 生成。例如 ${\mathbb{Z}}_{12}$ 的子群由 $\{1,2,3,4,6,12\}$ 的倍数生成。
  • 乘法群 ${\mathbb{Z}}_n^{\ast }$： 先找原根（生成元），子群是由某个元素 $a$ 的幂次 $\{a^1,a^2,\dots ,a^k=e\}$ 组成的集合。

第23题：商群计算

• 【题目 23】 设 12 阶循环群 $({\mathbb{Z}}_{12},+)$，$H=\{0,3,6,9\}=⟨3⟩$ 是子群，求商群 ${\mathbb{Z}}_{12}/H$。
• 核心套路：
  1. 阶数： $|{\mathbb{Z}}_{12}/H|=|{\mathbb{Z}}_{12}|/|H|=12/4=3$。
  2. 元素形态： 元素是陪集，形如 $a+H$。
  3. 结果： ${\mathbb{Z}}_{12}/H=\{0+H,1+H,2+H\}$。

第二梯队：核心定理的应用（理解结论，直接拿分）

这些结论在判断题和简答题中非常常用。

第12、21题：指数为2的判定

• 【题目内容】 证明：指数为 2 的子群（即 $[G:H]=2$）一定是正规子群（$H◃G$）。
• 考试价值： 结论必记。如果题目问“某个子群是否正规”，先看它的阶是不是大群的一半。

第15题：循环群的性质

• 【题目内容】 证明：一个循环群一定是交换群（Abel群）。
• 考试价值： 基础结论。循环群的所有元素都能表示为 $g^k$，因为 $g^a\cdot g^b=g^{a+b}=g^b\cdot g^a$，所以一定交换。

第18题：素数阶群

• 【题目内容】 证明：阶是素数的群一定是循环群。
• 考试价值： 核心定理。素数阶群没有非平凡子群，任何非单位元都是生成元。

第14题：元素的阶

• 【题目内容】 证明：一个有限群的每一个元素的阶都是有限的。
• 核心结论： 元素的阶 $ord(a)$ 一定能整除群的阶 $|G|$（拉格朗日定理推论）。

第三梯队：有固定模板的证明（考前背诵套路）

如果考卷最后有大题，大概率从这几道里改数。

第3题：Abel群证明

• 【题目内容】 设 $e$ 是群 $G$ 中的单位元，$\forall a\in G$，有 $a^2=e$，证明 $G$ 是 Abel 群。
• 套路模板：
  1. 取 $a,b\in G$，则其积 $ab\in G$。
  2. 根据已知条件，$(ab{)}^2=e$，即 $abab=e$。
  3. 两边同时左乘 $a$，右乘 $b$：$a(abab)b=aeb⟹(aa)ba(bb)=ab$。
  4. 因 $a^2=e,b^2=e$，简化得 $ebae=ab⟹ba=ab$。结论证毕。

第11题：子群交集证明

• 【题目内容】 证明：正规子群的交（或普通子群的交）仍然是正规子群（或子群）。
• 套路模板（证明子群“三部曲”）：
  1. 非空性： 单位元 $e$ 在每个子群里，所以 $e$ 也在交集里。
  2. 封闭性： 设 $x,y\in H_1\cap H_2$，则 $x,y\in H_1$ 且 $x,y\in H_2$。因 $H_1,H_2$ 是子群，故 $xy\in H_1,xy\in H_2$，所以 $xy\in H_1\cap H_2$。
  3. 逆元存在性： 同理证明 $x^{-1}\in H_1\cap H_2$。

环中的考点

一、 核心计算题（必考，拿分项）

1. 多项式运算与逆元（对应原题 7, 12, 13）

• 题干（13）： 在 ${\mathbb{Z}}_3[x]/(x^2+1)$ 中求 $x+2$ 的逆元。
• 重点： 理解模运算。在 ${\mathbb{Z}}_3$ 中，系数只能是 $0,1,2$。
• 题干（12）： 写出 $F_2[x]/(x^2+x+1)$ 的乘法表。

2. 不可约判定与分解（对应原题 9, 11）

• 题干（9）： 将 $x^2+1,x^2+x+1,x^2+x\in F_2[x]$ 分解为不可约多项式的乘积。
• 题干（11）： 给出 1 个 ${\mathbb{Z}}_5[x]$ 中的三次不可约首一多项式。
• 技巧： 代入法。例如第 9 题中 $x^2+x=x(x+1)$，而 $x^2+x+1$ 代入 $0$ 和 $1$ 都不为 $0$，故不可约。

3. 扩展欧几里得算法（对应原题 10）

• 题干（10）： $f(x)=x^7+x^5+x^2+1\in F_2[x],g(x)=x^4+x^2+x\in F_2[x]$，求 $\text{gcd}(f,g)$ 并求 $s,t\in F_2[x]$，使得 $\text{gcd}(f,g)=s\cdot f+t\cdot g$。
• 注意： $F_2$ 下加法等于减法（异或运算），系数没有负数。

二、 核心概念判定（填空/判断）

1. 环、整环、域的包含关系（对应原题 1）

• 结论： 域 $⟹$ 整环 $⟹$ 交换环 $⟹$ 环。
• 常见陷阱：
  • “所有的环都存在一个单位元”（错，如偶数环）。
  • “整数环与偶数环同构”（错，一个有单位元 $1$，一个没有）。
  • “域中的每个子环都没有零因子”（对，因为域本身没零因子，子环自然也没有）。

2. 理想的性质（对应原题 1）

• 结论： 两个理想的交集还是一个理想（对）。

三、 简单证明套路（模版化记忆）

1. 判定一个集合 $I$ 是环 $R$ 的理想（对应原题 14, 15）

• 题干（15）： 设 $R$ 是含单位元的交换环，$I,J$ 是 $R$ 的理想，定义 $I+J=\{x+y\mid x\in I,y\in J\}$。证明：$I+J$ 是 $R$ 的理想。
• 证明三步走模版：
  1. 非空： 因为 $0\in I,0\in J$，所以 $0+0=0\in I+J$。
  2. 加法封闭： 任取 $a_1+b_1,a_2+b_2\in I+J$，则 $(a_1+b_1)-(a_2+b_2)=(a_1-a_2)+(b_1-b_2)\in I+J$。
  3. 乘法吸入： 任取 $r\in R,a+b\in I+J$，则 $r(a+b)=ra+rb$。因 $I,J$ 是理想，故 $ra\in I,rb\in J$，结果仍在 $I+J$ 中。

2. 循环群推导交换环（对应原题 4）

• 题干（4）： 假设一个环 $R$ 作为加群是一个循环群，证明 $R$ 是一个交换环。
• 关键点： 设生成元为 $g$，则任何元素可写为 $mg,ng$。乘积 $mg\cdot ng=(mn)(g\cdot g)=ng\cdot mg$。

有限域中的考点

一、 有限域的存在性与阶（核心判断题）

1. 阶的判定（对应原题 1, 4）

• 考点： 有限域阶数 $q$ 必须是素数的幂，即 $q=p^n$（$p$ 是素数，$n\ge 1$）。
• 判断实例（第1题）：
  • “存在含 5 个元素的域”：对，因为 $5=5^1$（素数阶域就是 ${\mathbb{Z}}_5$）。
  • “存在含 6 个元素的域”：错，因为 6 不是任何素数的幂。
• 构造结论（第4题）： $F_{13}$ 直接取 ${\mathbb{Z}}_{13}$；$F_{16}$ 需要利用 $F_2$ 上的 4 次不可约多项式构造。

2. 域的特征（对应原题 7）

• 结论： 若有限域阶数为 $p^n$，则其特征（Characteristic）一定是素数 $p$。
• 练习（第7题）： 含 $9=3^2$ 个元素的域，其特征是 3。

二、 有限域的子域与哈斯图（高频大题）

1. 子域存在判定（对应原题 3）

• 定理： $F_{p^m}$ 有一个阶为 $p^k$ 的子域，当且仅当 $k$ 整除 $m$（$k|m$）。
• 练习（第3题）： $F_{3^{15}}$ 的子域阶数为 $3^k$，其中 $k$ 是 15 的因子。
  • 15 的因子有：$1,3,5,15$。
  • 所有子域为：$F_3,F_{3^3},F_{3^5},F_{3^{15}}$。
• 哈斯图绘制： 根据因子的整除关系连线。

三、 运算：多项式逆元（必考计算）

1. 求逆元的步骤（对应原题 2）

• 题干： 在 ${\mathbb{Z}}_3[x]/(x^2+1)$ 中求 $x+2$ 的逆元。
• 套路： 使用扩展欧几里得算法。
  1. 令 $x^2+1$ 除以 $x+2$。
  2. $x^2+1=(x-2)(x+2)+5$。
  3. 在 ${\mathbb{Z}}_3$ 下简化：$5\equiv 2(\mathrm{mod}3)$，$-2\equiv 1(\mathrm{mod}3)$。
  4. 即 $x^2+1=(x+1)(x+2)+2$。
  5. 移项并使余数为 1（两边乘 2 的逆元，${\mathbb{Z}}_3$ 中 2 的逆是 2）：$2(x^2+1)-2(x+1)(x+2)=1$。
  6. 得出逆元为 $-2(x+1)=x+1$（系数模 3）。

四、 本原元与多项式表示（综合大题）

1. 本原元的定义与判定（对应原题 5, 9）

• 核心： 域 $F_q$ 的非零元个数为 $q-1$。若 $\alpha$ 的阶正好等于 $q-1$，则称其为本原元。
• 判定方法（第5题）： 对于 $F_{2^4}$（16个元素），非零元 15 个。检查 $\alpha$ 的幂次：如果 ${\alpha }^k\ne 1$（对于所有 $k<15$），则 $\alpha$ 是本原元。

2. 有限域的两种表示法（对应原题 5, 9）

• 多项式表示： 元素表示为系数在 $F_p$ 中的多项式。
• 幂表示： 元素表示为本原元 $\alpha$ 的幂次 $\{0,{\alpha }^0,{\alpha }^1,\dots ,{\alpha }^{q-2}\}$。

五、 补充性质（容易出填空）

• 元素之和（第8题）： 在阶 $q>2$ 的有限域中，所有元素之和必为 0。
• 不可约多项式的积（第10题）： $x^q-x$ 等于 $F_p$ 上所有次数整除 $n$ 的不可约首一多项式的乘积。

后量子密码学中的考点

一、 格密码：多项式环运算（对应原题 4, 6）

这是 PQC 部分最高频的计算考点，核心是多项式乘法 + 模 $x^n+1$ 降次。

• 题干（4）： 在多项式环 $R_{61}={\mathbb{Z}}_{61}[x]/(x^4+1)$ 中，给定 $a(x)=4x^3+16x^2+51$, $s(x)=x^3+x^2$, $e(x)=x^2+60$，求 $t(x)=a(x)\cdot s(x)+e(x)$。
  • 计算要点：
    1. 先做多项式乘法 $a(x)\cdot s(x)$。
    2. 关键降次公式：由于模 $x^4+1$，所以令 $x^4\equiv -1$。
    3. 例如 $x^6=x^4\cdot x^2\equiv -x^2$，系数记得模 61。
• 题干（6）： 在基于 Ring-LWE 的加密算法中，采用多项式环 $R_{61}={\mathbb{Z}}_{61}[x]/(x^8+1)$。给定私钥 $s(x)=x^6+x^4+x^2$ 和密文 $(C_{msg},C_{aux})$，求明文。
  • 解密逻辑：计算 $Dec=C_{msg}-C_{aux}\cdot s(x)(\mathrm{mod}{x}^8+1)$。

二、 编码密码：矩阵与校验（对应原题 3, 5）

这类题主要考 $F_2$（二进制）下的矩阵运算，加法就是异或。

• 题干（3）： 在基于编码的 PQC 算法 Niederreiter 中，已知公钥矩阵 $\tilde{H}$（一个 $3\times 7$ 矩阵）和明文向量 $e=(0,0,1,0,0,0,0)$，求加密结果。
  • 公式：密文 $c=\tilde{H}\cdot e^T(\mathrm{mod}2)$。
• 题干（5）： 给定 $n=7,k=4$ 的线性编码奇偶校验矩阵 $H=(P^T\mid I_{n-k})$，写出其对应的生成矩阵 $G$。
  • 公式：如果 $H=(P^T\mid I_{n-k})$，则 $G=(I_k\mid P)$。

三、 格密码基础：LWE 方案（对应原题 1）

这是最基础的格密码形式，考的是矩阵乘法。

• 题干（1）： 在简单的 LWE 方案中，假设参数 $n=3,k=3,q=61$，给定矩阵 $A$, 公钥 $t$, 私钥 $s$。
  1. 生成辅助变量 $r,e_{aux},e_{msg}$。
  2. 加密和解密消息 $m=0$ 和 $m=1$。

四、 哈希密码：Merkle 树（对应原题 7）

• 题干（7）： 在基于哈希的 PQC 密码系统中，假设 MSS 树的高度为 $t=3$，采用 $f(x)\equiv x^2+3(\mathrm{mod}32)$ 作为哈希函数。根据给定的叶子节点计算树的根节点。

网信院真题（个人回忆版）

神人题型，全是解答，一个解答简单的 5 分，难的 10 分。

1. 证明 $(a,b)=d⟹(\frac{a}{d},\frac{b}{d})=1$

2. 今天是星期三，$2^{2025}$ 天后是周几。

3. 判断 $x^2\equiv 3(\mathrm{mod}17)$ 是否有解

4. 求解一个线性同余方程

5. 求解一个线性同余方程

6. 题目给定 $F_2[x]$ 中两个多项式 $f(x),g(x)$，求带余除法 $f(x)=q(x)g(x)+r(x)$ 中的 $q(x)$ 和 $r(x)$，然后求 $gcd(f(x),g(x))$

7. 给定一个 $(7,4)$ 线性分组码，其奇偶校验矩阵 $H$ 为： $H=\left(\begin{array}{ccccccc}1& 1& 1& 0& 1& 0& 0\\ 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 0& 0& 1\end{array}\right)$ 错误向量 $e=(0,0,1,0,0,0,0)$

题目要求计算伴随式（校验子）：若接收端收到的向量为 $e^T=(0,0,1,0,0,0,0)$（即你图中给出的 $e$），求该接收向量对应的校验子。

8. 在基于哈希的 PQC 密码系统中，假设 MSS 树的高度为 $t=3$，采用 $f(x)\equiv x^2+3(\mathrm{mod}32)$ 和 $h(x_i)\equiv f(\sum x_i)$ 作为哈希函数。树的叶子节点包含以下值： $\begin{array}{c}{v}_0[0]=5,v_0[1]=15,v_0[2]=6,v_0[3]=4,\\ v_0[4]=13,v_0[5]=7,v_0[6]=11,v_0[7]=19\end{array}$ 给定消息 $m=110010101$，假设利用编号 $c=3$ 的密钥生成的 OTS 签名为：$si{g}_{OTS}=(21,3,15,26,17)$请计算消息 $m$ 的完整的签名。

9. 设 $G=\mathbb{R}\setminus \{-1\}$（即所有不等于 $-1$ 的实数集合）。在 $G$ 上定义运算 $\circ$ 如下： $\forall a,b\in G,a\circ b=a+b+ab$ 证明代数系统 $(G,\circ )$ 构成一个群。

10. 令 $f(x)=x^4+x+1\in F_2[x]$，$f(x)$ 是 $F_2[x]$ 上不可约多项式，设 $\alpha$ 是 $f(x)$ 在 $F_2$ 的扩域 $F_{2^4}$ 中的一个根，判断 $\alpha$ 是否是 $F_{2^4}$ 的一个本原元。用两种方式表示扩域 $F_{2^4}$。如果 $\alpha$ 是本原元，用本原元表示 $F_{2^4}$。

11. 设 12 阶循环群 $({\mathbb{Z}}_{12},+)$，$H=\{0,3,6,9\}=⟨3⟩$ 是 ${\mathbb{Z}}_{12}$ 的 4 阶子群，则 $H$ 是 ${\mathbb{Z}}_{12}$ 的正规子群，求 $H$ 的指数，求商群 ${\mathbb{Z}}_{12}/H$ (${\mathbb{Z}}_{12}/⟨3⟩$)。

12. 设整数 $N$ 的 $q$ 进制表示为 $N=(a_n\dots a_1{a}_0{)}_q={\sum }_{i=0}^n{a}_i{q}^i$。

    1. 当 $q=10$ 时，写出 $N$ 能被 $9$ 整除的充要条件。（答案：各位数字之和能被9整除）
    2. AI 还原的，感觉有点像这个，但是应该不是：若除数 $m$ 满足 $(m,q)=1$（即 $m$ 与 $q$ 互质），且 $k$ 是满足 $q^k\equiv 1(\mathrm{mod}m)$ 的最小正整数（即 $k$ 是 $q$ 模 $m$ 的阶，这里对应你记忆中的 $a=b^c$ 形式）。请写出 $N$ 能被 $m$ 整除的充要条件。