安徽理工大学 2023--2024 (2) 信息安全的数学基础

试卷概览

安徽理工大学 2023–2024（2）信息安全的数学基础

试卷重排：anyunyeyi

---

一、 基础计算题

• 1. 求 $(2n, 2(n+1))$
• 2. 求 $2^{47} \pmod{47}$ 的余数
• 3. $a = 47^{11} 79^{111} 101^{1001}, \quad b = 41^{11} 83^{111} 101^{1000}$ 求 $(a,b)$ 和 $[a,b]$.

二、 伪素数证明

证明：1387 是对于基 2 的伪素数，但不是对于基 2 的强伪素数。

三、 同余式求解

求解同余式：

$$3x^{14} + 4x^{13} + 2x^{11}+x^9 + x^6 + x^3 + 12x^2 + x \equiv 0 \pmod{7}$$

四、 置换计算

设 $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\\\ 2 & 3 & 4 & 5 & 6 & 1 \end{pmatrix}$, $\tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\\\ 5 & 3 & 4 & 2 & 6 & 1 \end{pmatrix}$，计算 $\sigma\tau$, $\tau\sigma$, $\sigma^{-1}$。

五、 广义欧几里得除法

运用广义欧几里得除法求整数 $s,t$ 使得 $s \cdot a + t \cdot b = (a,b)$：
$(1613, \quad 3589)$

六、 孙子定理应用

一个数大概四、五千，除以 7 余 6，除以 5 余 2，除以 11 余 4。这样的四位数共有几个？分别写出符合条件的数？

七、 剩余系

1. 请写出模 10 的一个完全剩余系。
2. 请写出模 30 的简化剩余系。

八、 二次剩余判断

判断同余式 $x^2 \equiv 186 \pmod{401}$ 是否有解。

九、 原根求解

求模 41 的所有原根。求模 $41^2$ 的原根。

十、 指数同余式

求解同余式 $x^{22} \equiv 33 \pmod{41}$

个位数 \ 十位数	0	1	2	3	4	5	6	7	8	9
0		40	26	15	12	22	1	39	38	30
1	8	3	27	31	25	37	24	33	16	9
2	34	14	29	36	13	4	17	5	11	7
3	23	28	10	18	19	21	2	32	35	6
4	20