安徽大学信息安全数学基础备考教程

前言：

安徽摆烂大学的大多数课程，都可以考前突击然后低分掠过，对我这种摆子很友好。然而有一个例外是信息安全数学基础，这门课是由近世代数和初等数论拼凑在一起的，网上找不到什么速成资料，如果你像我一样完全不听，会导致下周考试了这周不知道备考啥。现给出安徽大学某年期末考试真题解析，以飨后人。

注意事项：

• 安大的试卷堪称宝宝巴士，这种区域性高校绝对不会难为老乡，所以本备考教程仅适用于安大或比安大更摆的学校，绝对不适用于全国性的高校；
• 题目与题解都写得尽可能好理解，如果你不能理解，将整个题解抄下来作为应试模板都是可以及格的；
• 本文题目来源于本人记忆，仅供学习和参考，不过安大常年不换题目、只改数，参考价值应该比较高。

第一题

解同余式组：

$\begin{cases} 3x \equiv 1 \pmod{10} \\ 5x \equiv 3 \pmod{12} \\ 2x \equiv 9 \pmod{15} \\ \end{cases}$

解：

对应教材（见《信息安全数学基础教程（第二版）》，清华大学出版社，第95页）模数两两不互素的中国剩余定理应用。这教材原文我看得云里雾里。

这里选择先求$a_i$逆元（求逆元过程略），得方程组如下：

$\begin{cases} x \equiv 7 \pmod{10} &(1) \\ x \equiv 3 \pmod{12} &(2) \\ x \equiv 12 \pmod{15} &(3) \\ \end{cases}$

然后判断两两相容性。两个同余方程 $x \equiv a \pmod{m}$ 和 $x \equiv b \pmod{n}$ 相容的充要条件是：

$a \equiv b \pmod{\gcd(m,n)}$

此处显然满足。现将（1）式写为$ x = 7 + 10 t $，将其代入（2）式：

（为什么？因为我们想知道在1式中，t究竟取什么值才能满足2式）

$\begin{aligned} 7 + 10t &\equiv 3 \pmod{12} \\ 10t &\equiv 3 - 7 \pmod{12} \\ 10t &\equiv -4 \pmod{12} \\ 10t &\equiv 8 \pmod{12} \\ 5t &\equiv 4 \pmod{6} \\ t &\equiv -4 \pmod{6} & \text{求逆元} \\ t &\equiv 2 \pmod{6} \end{aligned}$

解得$t=2+6k$，$x=7+10t=27+60k$，解即为：

$x\equiv27\pmod{60}$

对k随意取值（如0、1）计算得到的 x 代入（3）式验证，无误。

第二题

一次同余方程求解：

$20x\equiv16\pmod{24}$

解：

本题 $\gcd(a,m) \mid b$，故有解。化简：

$\begin{aligned} 20x&\equiv16\pmod{24}\\ 5x&\equiv4\pmod{6}\\ x&\equiv2\pmod{6}\\ \end{aligned}$

即 $ x=2+6k $，但原式模数为 24 。改写为对24取模的版本：

$\begin{cases} k=0 & x=2\\ k=1 & x=8\\ k=2 & x=14\\ k=3 & x=20\\ k=4 & x=26 & \text{大于24舍去} \\ \end{cases}$

最终答案：

$x \equiv 2,8,14,20 \pmod{24}$

第三题

用费马小定理化简多项式：

$3x^{14}+4x^{13}+2x^{11}+x^{9}+5x^{8}+x^{6}+x^{3}+12x^{2}+1\equiv0\pmod{5}$

解：

费马小定理，其中 p 为素数，a 为整数：

$a^{p} \equiv a \pmod{p}$

据此有

$x^{5} \equiv x \pmod{5}\\ x^{4} \equiv 1 \pmod{5}\\ x^{6} \equiv x \cdot x^{5} \equiv x \cdot x \pmod{5}\\$

借助上式得到：

$x^{14} \equiv (x^{4})^{3} \cdot x^{2} \equiv x^{2} \pmod{5}\\ x^{13} \equiv (x^{4})^{3} \cdot x \equiv x \pmod{5}\\ x^{12} \equiv (x^{4})^{3} \equiv 1 \pmod{5}\\$

以此类推。

$\begin{aligned} 3x^{14} &\equiv 3x^{2} \pmod{5} \\ 4x^{13} &\equiv 4x^{1} \pmod{5} \\ 2x^{11} &\equiv 2x^{3} \pmod{5} \\ x^{9} &\equiv x^{1} \pmod{5} \\ 5x^{8} &\equiv 0 \pmod{5} \quad \text{因为 } 5 \equiv 0 \pmod{5} \\ x^{6} &\equiv x^{2} \pmod{5} \\ x^{3} &\equiv x^{3} \pmod{5} \\ 12x^{2} &\equiv 2x^{2} \pmod{5} \quad \text{因为 } 12 \equiv 2 \pmod{5} \\ 1 &\equiv 1 \pmod{5} \end{aligned}$

替换原式内的每项，然后合并同类项：

$\begin{aligned} &3x^{2} + 4x + 2x^{3} + x + 0 + x^{2} + x^{3} + 2x^{2} + 1 \\ &\equiv (3 + 1 + 2)x^{2} + (4 + 1)x + (2 + 1)x^{3} + 1 \pmod{5} \\ &\equiv 6x^{2} + 5x + 3x^{3} + 1 \pmod{5} \\ &\equiv x^{2} + 0 \cdot x + 3x^{3} + 1 \pmod{5} \\ &\equiv 3x^{3} + x^{2} + 1 \pmod{5} \end{aligned}$

也就是：

$3x^{3} + x^{2} + 1 \equiv 0 \pmod{5}$

依次代入 x=0~4 即可得出结果。

$\begin{aligned} x \equiv 0 \pmod{5}: \quad &3(0)^3 + (0)^2 + 1 \equiv 1 \not\equiv 0 \pmod{5} \\ x \equiv 1 \pmod{5}: \quad &3(1)^3 + (1)^2 + 1 \equiv 3 + 1 + 1 \equiv 5 \equiv 0 \pmod{5} \\ x \equiv 2 \pmod{5}: \quad &3(8) + 4 + 1 \equiv 24 + 5 \equiv 4 \not\equiv 0 \pmod{5} \\ x \equiv 3 \pmod{5}: \quad &3(27) + 9 + 1 \equiv 81 + 10 \equiv 1 \not\equiv 0 \pmod{5} \\ x \equiv 4 \pmod{5}: \quad &3(64) + 16 + 1 \equiv 192 + 17 \equiv 4 \not\equiv 0 \pmod{5} \end{aligned}$

仅在 1 时符合题意，解为$x \equiv 1 \pmod{5}$，即$x=1+5k$。

第四题

在有限域 GF(2)[x] 上检验下列多项式可约性，并分解可约者：

$x^{5}+x^{4}+1\\ x^{5}+x^{2}+1\\$

解：

对于有限域 GF(2)[x] ，有已知的不可约因式如下（五次以内）：

$\begin{cases} 一次因子：x,&x+1\\ \\ 二次因子：x^{2}+x+1\\ \\ 三次因子：x^{3}+x^{2}+1,&x^{3}+x+1\\ \\ 四次因子：x^{4}+x^{3}+x^{2}+x+1 & x^{4}+x^{3}+1 \\ & x^{4}+x+1 \\ \\ 五次因子：& x^{5}+x^{3}+x^{2}+x+1 \\ & x^{5}+x^{4}+x^{2}+x+1 \\ & x^{5}+x^{4}+x^{3}+x+1 \\ & x^{5}+x^{4}+x^{3}+x^{2}+1 \\ & x^{5}+x^{3}+1 \\ & x^{5}+x^{2}+1 \end{cases}$

故$x^{5}+x^{2}+1$不可分解，$x^{5}+x^{4}+1$可分解，以可分解的式子为例，判断过程如下：

$\text{检查一次因子}\begin{cases} \text{代入0} \quad \begin{cases} =0 \quad \text{存在因子x} \\ =1 \quad \text{不存在因子x} \quad \checkmark \\ \end{cases} \\ \text{代入1} \quad \begin{cases} =0 \quad \text{存在因子x+1} \\ =1 \quad \text{不存在因子x+1} \quad \checkmark \\ \end{cases} \\ \end{cases}$

故可以排除一次-四次分解，再检查二次-三次分解。列方程：

$(x^{2}+x+1)\cdot(x^{3}+ax^{2}+bx+c)=x^{5}+x^{4}+1$

解得$x^{3}-x+1$，其中减法在有限域 GF(2)[x] 内与加法等价，最终分解为：

$(x^{2}+x+1)\cdot(x^{3}+x+1)$

第五题

请利用勒让德符号的性质，判别 -35 是否为模 97 的二次剩余。

解：

由于97是素数，我们可以使用勒让德符号来判断。我们需要计算 $(\frac{-35}{97})$。

$(\frac{-35}{97}) = (\frac{-1 \cdot 5 \cdot 7}{97}) = (\frac{-1}{97}) (\frac{5}{97}) (\frac{7}{97})$

根据勒让德符号的性质：

1. 计算 $(\frac{-1}{97})$:
   因为 $97 \equiv 1 \pmod{4}$，所以 $(\frac{-1}{97}) = 1$。

2. 计算 $(\frac{5}{97})$:
   根据二次互反律，因为 $5 \equiv 1 \pmod{4}$ 且 $97 \equiv 1 \pmod{4}$，我们有 $(\frac{5}{97}) = (\frac{97}{5})$。
   $97 \equiv 2 \pmod{5}$，所以 $(\frac{97}{5}) = (\frac{2}{5})$。
   因为 $5 \equiv 5 \pmod{8}$，所以 $(\frac{2}{5}) = -1$。

3. 计算 $(\frac{7}{97})$:
   根据二次互反律，因为 $97 \equiv 1 \pmod{4}$，我们有 $(\frac{7}{97}) = (\frac{97}{7})$。
   $97 = 13 \cdot 7 + 6$，所以 $97 \equiv 6 \pmod{7}$。
   $(\frac{97}{7}) = (\frac{6}{7}) = (\frac{2}{7})(\frac{3}{7})$。
   因为 $7 \equiv 7 \pmod{8}$，所以 $(\frac{2}{7}) = 1$。
   对于 $(\frac{3}{7})$，根据二次互反律，因为 $3 \equiv 3 \pmod{4}$ 且 $7 \equiv 3 \pmod{4}$，我们有 $(\frac{3}{7}) = -(\frac{7}{3})$。
   $7 \equiv 1 \pmod{3}$，所以 $(\frac{7}{3}) = (\frac{1}{3}) = 1$。
   因此，$(\frac{3}{7}) = -1$。
   所以 $(\frac{7}{97}) = 1 \cdot (-1) = -1$。

综合起来：

$(\frac{-35}{97}) = (1) \cdot (-1) \cdot (-1) = 1$

结果为1，所以-35是97的平方剩余。

第六题

求满足以下条件的正整数 n 的个数：n 整除 $10^{40}$ 或 n 整除 $20^{30}$。

解：

设 A 是 $10^{40}$ 的正因子集合，B 是 $20^{30}$ 的正因子集合。题目要求计算 $|A \cup B|$。
根据容斥原理， $|A \cup B| = |A| + |B| - |A \cap B|$。
$A \cap B$ 是 $10^{40}$ 和 $20^{30}$ 的公因子集合，即 $\gcd(10^{40}, 20^{30})$ 的因子集合。

1. 计算 $|A|$:
   $10^{40} = (2 \cdot 5)^{40} = 2^{40} \cdot 5^{40}$。
   因子个数为 $\tau(10^{40}) = (40+1)(40+1) = 41 \times 41 = 1681$。

2. 计算 $|B|$:
   $20^{30} = (2^2 \cdot 5)^{30} = 2^{60} \cdot 5^{30}$。
   因子个数为 $\tau(20^{30}) = (60+1)(30+1) = 61 \times 31 = 1891$。

3. 计算 $|A \cap B|$:
   $\gcd(10^{40}, 20^{30}) = \gcd(2^{40} \cdot 5^{40}, 2^{60} \cdot 5^{30}) = 2^{\min(40, 60)} \cdot 5^{\min(40, 30)} = 2^{40} \cdot 5^{30}$。
   其因子个数为 $\tau(2^{40} \cdot 5^{30}) = (40+1)(30+1) = 41 \times 31 = 1271$。

4. 计算 $|A \cup B|$:
   $|A \cup B| = 1681 + 1891 - 1271 = 2301$。

所以，满足条件的正整数n的数目为2301个。

第七题

设 G 是一个由元素 a 生成的 n 阶循环群，即 $G = \langle a \rangle$ 且 $|G| = n$。若正整数 m 与 n 互素，即 $\gcd(m, n) = 1$，请证明 $a^m$ 也是 G 的一个生成元。

解：

设 $G = \langle a \rangle$ 是一个由元素 $a$ 生成的 n 阶循环群。这意味着 $a$ 的阶是 $n$，即 $o(a) = n$。
我们需要证明 $a^m$ 也是 $G$ 的一个生成元。
一个元素是生成元，当且仅当它的阶等于群的阶。所以，我们只需证明 $o(a^m) = n$。

根据循环群中元素阶的性质，我们有公式：

$o(a^k) = \frac{n}{\gcd(k, n)}$

将 $k=m$ 代入公式，我们得到：

$o(a^m) = \frac{n}{\gcd(m, n)}$

题目给出条件，$m$ 和 $n$ 互素，这意味着 $\gcd(m, n) = 1$。
因此，

$o(a^m) = \frac{n}{1} = n$

由于 $a^m$ 的阶为 $n$，与群 $G$ 的阶相等，所以 $a^m$ 能够生成 $G$ 中所有的 $n$ 个元素。
因此，$a^m$ 也是群 $G$ 的一个生成元。证明完毕。

第八题

已知 10 是模 19 的一个原根。请完成以下两个任务：
a) 构造以 10 为底的模 19 离散对数表，并找出所有模 19 的原根。
b) 求解二次同余方程 $4x^2+5x-8 \equiv 0 \pmod{19}$。

解：

a) 构造离散对数表 & 给出所有原根

首先，我们计算以10为底，模19的幂，直到覆盖所有非零余数：

（注意下列式子绝非暴力计算，而是将上一式的余数乘以底数10作为对19取模的数，并不真正地计算10的高次幂）

$\begin{aligned} 10^{1} &\equiv 10 \pmod{19}\\ 10^{2} &\equiv 100 \equiv 5 \pmod{19}\\ 10^{3} &\equiv 50 \equiv 12 \pmod{19}\\ 10^{4} &\equiv 120 \equiv 6 \pmod{19}\\ 10^{5} &\equiv 60 \equiv 3 \pmod{19}\\ 10^{6} &\equiv 30 \equiv 11 \pmod{19}\\ 10^{7} &\equiv 110 \equiv 15 \pmod{19}\\ 10^{8} &\equiv 150 \equiv 17 \pmod{19}\\ 10^{9} &\equiv 170 \equiv 18 \pmod{19}\\ 10^{10} &\equiv 180 \equiv 9 \pmod{19}\\ 10^{11} &\equiv 90 \equiv 14 \pmod{19}\\ 10^{12} &\equiv 140 \equiv 7 \pmod{19}\\ 10^{13} &\equiv 70 \equiv 13 \pmod{19}\\ 10^{14} &\equiv 130 \equiv 16 \pmod{19}\\ 10^{15} &\equiv 160 \equiv 8 \pmod{19}\\ 10^{16} &\equiv 80 \equiv 4 \pmod{19}\\ 10^{17} &\equiv 40 \equiv 2 \pmod{19}\\ 10^{18} &\equiv 20 \equiv 1 \pmod{19} \end{aligned}$

离散对数表 (ind(N) = L):

	0	1	2	3	4	5	6	7	8	9
0	-	18	17	5	16	2	4	12	15	10
1	1	6	3	13	11	7	14	8	9	-

如果 $g$ 是模 $n$ 的一个原根，那么其他原根的形式为 $g^k \pmod n$，其中 $\gcd(k, \phi(n))=1$。
这里 $n=19$, $\phi(19)=18$。我们需要找到与18互素的 $k$ ( $1 \le k < 18$ )。
这些 $k$ 是：1, 5, 7, 11, 13, 17。
对应的原根为：
$10^1 \equiv 10$
$10^5 \equiv 3$
$10^7 \equiv 15$
$10^{11} \equiv 14$
$10^{13} \equiv 13$
$10^{17} \equiv 2$
所以，模19的所有原根是 {2, 3, 10, 13, 14, 15}。

b) 解同余方程

$4x^2+5x-8 \equiv 0 \pmod{19}$

使用二次公式 $x \equiv (-b \pm \sqrt{b^2-4ac})(2a)^{-1} \pmod p$。
$a=4, b=5, c=-8 \equiv 11 \pmod{19}$。
判别式 $\Delta = b^2 - 4ac = 5^2 - 4(4)(-8) = 25 + 128 = 153$。
$153 = 8 \times 19 + 1$, 所以 $\Delta \equiv 1 \pmod{19}$。
$\sqrt{\Delta} \equiv \sqrt{1} \equiv \pm 1 \pmod{19}$。
$2a = 8$。我们需要计算 $8^{-1} \pmod{19}$。
$8x \equiv 1 \pmod{19}$，解得 $x \equiv 12 \pmod{19}$。所以 $(2a)^{-1} = 12$。
代入公式：

$x \equiv (-5 \pm 1) \cdot 12 \pmod{19}$

两个解：

1. $x_1 \equiv (-5+1) \cdot 12 = -4 \cdot 12 = -48 \equiv 9 \pmod{19}$
2. $x_2 \equiv (-5-1) \cdot 12 = -6 \cdot 12 = -72 \equiv 4 \pmod{19}$

所以方程的解为 $x \equiv 4 \pmod{19}$ 和 $x \equiv 9 \pmod{19}$。