网安数学期中考试 ​

1. 设是n两个不同素数的乘积，若知道n=437和$\varphi (n)=396$ ，用欧拉函数的性质求的因数分解式。 ​

解答： ​

$ n = 437 $，$ \varphi(n) = 396 $$ n $ 是两个不同素数的乘积，即 $ n = p \cdot q $，其中 $ p $ 和 $ q $ 是互异的素数。

用欧拉函数的性质来求出 $ n $ 的因数分解式，即找出 $ p $ 和 $ q $。

第一步：回顾欧拉函数的性质

对于两个不同的素数 $ p $ 和 $ q $，有：

所以：

而：

第二步：设方程

我们有：

展开式 (2)：

代入 $ pq = 437 $：

所以我们现在有两个方程： $ p + q = 42 $$ pq = 437 $

第三步：解二次方程

设 $ p $ 和 $ q $ 是方程的根：

解这个方程：

所以： $ x = \frac{42 + 4}{2} = \frac{46}{2} = 23 $$ x = \frac{42 - 4}{2} = \frac{38}{2} = 19 $

因此，两个素数是：

第四步：验证 $ 19 \times 23 = 437 $ $ \varphi(437) = (19 - 1)(23 - 1) = 18 \times 22 = 396 $

答案：

这就是 $ n = 437 $ 的因数分解式。

2.（1）根据同余的性质，求${353}^{48}\times {723}^{25}\times 309\times 2022$被10除的余数。 ​

解答： ​

也就是这个大数 除以 10 的余数，即它的 个位数字。

第一步：模 10 只看个位

因为一个整数模 10 的结果就是它的个位数字，而且乘积的个位只由各个因子的个位决定，所以我们可以只保留每个数的个位： $353\equiv 3(\mathrm{mod}10)$$723\equiv 3(\mathrm{mod}10)$$309\equiv 9(\mathrm{mod}10)$$2022\equiv 2(\mathrm{mod}10)$

所以原式模 10 等价于：

合并同底幂：

所以变成：

注意：$9=3^2$，所以也可以写成：

所以我们现在要计算：

第二步：找 $3^n\mathrm{mod}10$ 的周期

观察 $3^n\mathrm{mod}10$ 的循环： $3^1=3$$3^2=9$$3^3=27\equiv 7$$3^4=81\equiv 1$$3^5=3$，开始循环！

所以 周期为 4。

因此：

第三步：计算最终结果

最终答案：

（2）写出模28的最小非负简化剩余系，绝对值最小简化剩余系，并算出欧拉函数。 ​

一、模 28 的简化剩余系（既约剩余系） ​

定义回顾：
模 $ n $ 的简化剩余系（或称既约剩余系）是指在mod n 的完整剩余系中且与 $ n $ 互素（即 $gcd(a,n)=1$）的元素集合。

1. 最小非负简化剩余系（mod 28） ​

我们要找出所有满足：

• $ 1 \leq a < 28 $
• $ \gcd(a, 28) = 1 $

最小非负简化剩余系 mod 28 是：

共有 12 个元素。

2. 绝对值最小简化剩余系（mod 28） ​

是指在mod n 的与n互素的剩余类中，选出绝对值最小的代表元。 由于模 28，完整对称区间通常取为：

在模28的简化剩余类中，选出绝对值最小的代表元，从上面的最小非负简化剩余系出发，将大于 14 的数转换成负数形式（减去 28）：

• [1] → 1
• [3] → 3
• [5] → 5
• [9] → 9
• [11] → 11
• [13] → 13
• [15] → 15 − 28 = −13
• [17] → 17 − 28 = −11
• [19] → −9
• [23] → −5
• [25] → −3
• [27] → −1

绝对值最小简化剩余系 mod 28 为：

也就是：

共 12 个数，每个都满足 $gcd(a,28)=1$，且绝对值 ≤13（最小可能）。

3. 欧拉函数 φ(28) ​

欧拉函数公式：若 $ n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} $，则

对 $ 28 = 2^2 \cdot 7 $，有：

与前面数出的元素个数一致。

最终答案： ​

• 模 28 的最小非负简化剩余系：

  $$\{1,3,5,9,11,13,15,17,19,23,25,27\}$$

• 模 28 的绝对值最小简化剩余系：

  $$\{-13,-11,-9,-5,-3,-1,1,3,5,9,11,13\}$$

• 欧拉函数值：

  $$\varphi (28)=12$$

3. 证明对于任意整数n有 24 | n(n+1)(n+2)(n+3) ​

对任意整数 $ n $，都有

方法一：利用整除性质（分解为 3 和 8）

注意到：

若3 ｜ n(n+1)(n+2)(n+3)； 8 ｜ n(n+1)(n+2)(n+3)； 并且由于 3 与 8 互素，因此n(n+1)(n+2)(n+3)能被 $ \text{lcm}(3,8) = 24 $ 整除，即 24=lcm(3,8) ｜ n(n+1)(n+2)(n+3)

第一步：能被 3 整除

在任意三个连续整数中，必有一个是 3 的倍数。 在四个连续整数：$ n, n+1, n+2, n+3 $，其中当然包含三个连续整数，所以其中至少有一个是 3 的倍数。

⇒ 因此，$ 3 \mid n(n+1)(n+2)(n+3) $

第二步：能被 8 整除

需要证明：四个连续整数的乘积中，至少含有因子 $ 2^3 = 8 $。

考虑四个连续整数中偶数的个数： 在任意两个连续整数中，必有一个是偶数； 所以在四个连续整数中，至少有两个偶数； 更精确地，四个连续整数模 2 的奇偶性为：奇、偶、奇、偶 或 偶、奇、偶、奇，取决于起始值。

同时，在任意四个连续整数中，必有一个是 4 的倍数（因为每四个整数就出现一个 4 的倍数）。

所以： 有一个数是 4 的倍数 ⇒ 至少提供因子 $ 4 $ 还有另一个偶数（不是 4 的倍数） ⇒ 提供至少一个额外的因子 2

因此，总共有至少 $ 2^2 \times 2 = 2^3 = 8 $ 作为因子。

举例验证： 若 $ n \equiv 0 \pmod{4} $，则 $ n $ 是 4 的倍数，$ n+2 $ 是偶数 ⇒ 2的幂次 $v_2$ $ \geq 2 + 1 = 3 $ 若 $ n \equiv 1 \pmod{4} $，则 $ n+1 \equiv 2 \pmod{4} $（\mathrm{偶}\mathrm{但}\mathrm{非}4\mathrm{倍}），$ n+3 \equiv 0 \pmod{4} $ ⇒ 同样 $ v_2 \geq 1 + 2 = 3 $ 若 $ n \equiv 2 \pmod{4} $，则 $ n $ 是偶非 4 倍，$ n+2 \equiv 0 \pmod{4} $ 若 $ n \equiv 3 \pmod{4} $，则 $ n+1 \equiv 0 \pmod{4} $，$ n+3 \equiv 2 \pmod{4} $

在所有情况下，2 的幂次$v_2$ ≥ 3 ⇒ 改乘积被 8 整除。

结论

3｜ $ n(n+1)(n+2)(n+3) $： 8｜ $ n(n+1)(n+2)(n+3) $：

$ \gcd(3,8)=1 $ 且lcm（3，8）=24

⇒ 24｜ $ n(n+1)(n+2)(n+3) $。

即：

4. 假如是X明文，Y是密文，可以构造仿射密码：Y=aX+b mod 77，分析一下这个仿射密码的密钥空间大小，并给出解密的算法或过程。 ​

仿射密码的加密公式为：Y=aX+b mod m，其中：

仿射密码的加密公式为：$Y=aX+b\mathrm{mod}m$，其中： $X$ 是明文字符对应的数值 $Y$ 是密文字符对应的数值 $a$ 和 $b$ 是密钥 $m$ 是字符集的大小（通常 $m=26$，对应英文字母表） 密钥空间的确定

为了使加密过程可逆（即可以解密），需要满足条件：gcd(a,m)=1（即 a 与 m 互质）。这是因为我们需要 a 在模 m 下存在乘法逆元。

所以要求 $a<77$ 且（a， 77）= 1， a的取值范围为：$\varphi (77)$=$\varphi (11)\times \varphi (7)=10\times 6=60$ (11 和7 互素) b的取值范围为：b 可以是0到m-1中的任意整数（共m=77种可能）

密钥空间大小$\varphi (77)\times 77=60\times 77=4620$

解密过程步骤

1. 计算 $a$ 的乘法逆元 $a^{-1}$： 使用扩展欧几里得算法找到 $a\cdot a^{-1}\equiv 1\mathrm{mod}77$ 的 $a^{-1}$

2. 对每个密文字符 $Y$： 计算 $X=a^{-1}(Y-b)\mathrm{mod}77$ 将数值 $X$ 转换回对应的字母 示例

仿射密码示例（m=77） 密钥选择 模数 $ m = 77 $ 选择密钥 $ a = 2 $（因为 $gcd(2,77)=1$，满足互质条件） 选择密钥 $ b = 5 $ 计算 $ a $ 在模 77 下的乘法逆元 $ a^{-1} $：

加密示例 明文字符：假设明文数字 $ X = 10 $（例如，在字符集映射中，10 可能代表某个字符，如 'K' 或特定符号）

加密公式：

计算过程：

密文：$ Y = 25 $

解密示例 密文：$ Y = 25 $

解密公式：

计算过程：

1. 计算 $ Y - b = 25 - 5 = 20 $
2. 计算 $ a^{-1} \cdot 20 = 39 \times 20 = 780 $
3. 计算 $ 780 \mod 77 $：

解密结果：$ X = 10 $

验证 加密：$ (2 \times 10 + 5) \mod 77 = 25 $\mathrm{解}\mathrm{密}：$ 39 \times (25 - 5) \mod 77 = 39 \times 20 \mod 77 = 780 \mod 77 = 10 $ 结果与原始明文一致

5. 给出一次同余方程 $6x\equiv 12\mathrm{mod}18$ 有多少解？并计算出所有的结果。 ​

要确定这个同余方程有多少个解，我们需要检查解的存在性条件。

对于一次同余方程 $ax\equiv b(\mathrm{mod}m)$，其有解的充要条件是 $gcd(a,m)\mid b$$a=6$, $b=12$, $m=18$$gcd(6,18)=6$ 检查 $6\mid 12$，所以条件满足。 因此，该方程有解。

当 $gcd(a,m)=d$ 且 $d\mid b$ 时，方程恰有 $d$ 个解。

这里 $d=6$，所以该方程有 6 个解。

将原方程约简：

两边同时除以 $gcd(6,18)=6$：

$a^{\prime }=\frac{6}{6}=1$, $b^{\prime }=\frac{12}{6}=2$, $m^{\prime }=\frac{18}{6}=3$

先构造特殊方程：$$x \equiv 1 \pmod{3}$$ 其解$x_0$=1

这意味着在模 18 下，通解的形式为：

计算所有解： $k=0$: $x=2+3\times 0=2$$k=1$: $x=2+3\times 1=5$$k=2$: $x=2+3\times 2=8$$k=3$: $x=2+3\times 3=11$$k=4$: $x=2+3\times 4=14$$k=5$: $x=2+3\times 5=17$ 验证

验证 $x=2,5,8,11,14,17$ 是否满足原方程： $x=2$: $6\times 2=12\equiv 12(\mathrm{mod}18)$ ✓ $x=5$: $6\times 5=30\equiv 12(\mathrm{mod}18)$ ✓ $x=8$: $6\times 8=48\equiv 12(\mathrm{mod}18)$ ✓ $x=11$: $6\times 11=66\equiv 12(\mathrm{mod}18)$ ✓ $x=14$: $6\times 14=84\equiv 12(\mathrm{mod}18)$ ✓ $x=17$: $6\times 17=102\equiv 12(\mathrm{mod}18)$ ✓ 结论

一次同余方程 $6x\equiv 12(\mathrm{mod}18)$ 有 6 个解，分别是：

6. 根据给出欧拉定理并根据欧拉定理求$4^{25}\times 7^{24}\times 2^{26}(mod15)$的值. ​

答案 ​

我们要求：

我们要求：

第一步：理解模数 15 的结构

注意到： $15=3\times 5$，不是质数； 欧拉函数 $\phi (15)=15(1-\frac{1}{3})(1-\frac{1}{5})=15\cdot \frac{2}{3}\cdot \frac{4}{5}=8$

所以 $\phi (15)=8$。

欧拉定理（Euler's Theorem）指出： 若 $gcd(a,m)=1$，则 $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$

15 不是素数，但是）4，7，2均予15互素。分别求出各部分mod 15 的结果计算乘积即可。

第二步：分别计算各部分模 15

1. 计算 $4^{25}mod15$

先看 $gcd(4,15)=1$，满足欧拉定理条件。

所以：

那么：

所以 $4^{25}\equiv 4(\mathrm{mod}15)$

2. 计算 $7^{24}mod15$

$gcd(7,15)=1$，也满足欧拉定理。

所以 $7^{24}\equiv 1(\mathrm{mod}15)$

3. 计算 $2^{26}mod15$

$gcd(2,15)=1$，满足条件。

所以 $2^{26}\equiv 4(\mathrm{mod}15)$

第三步：合并结果

最终答案：

7. 费马素性检测的原理是什么？用费马素性检测方法来判断31是否为素数，并使其是素数的可能性大于$1-\frac{1}{2^3}$。 ​

答案 ​

费马素性检测（Fermat Primality Test）是一种基于费马小定理的概率性素性检验方法。

一、费马素性检测的原理 费马小定理（Fermat's Little Theorem）： 若 $ p $ 是一个素数，且整数 $ a $ 满足 $ 1 < a < p $ 且 $ \gcd(a, p) = 1 $，则有：

费马素性检测思想： 给定一个奇整数 $ n \geq 3 $，我们随机选取若干个底数 $ a \in [2, n-2] $，检查是否满足：

如果对某个 $ a $ 不成立，则 $ n $ 一定是合数； 如果对所有选取的 $ a $ 都成立，则 $ n $ 可能是素数（但不能完全确定，因为存在“伪素数”，如 Carmichael 数）。

该方法是概率性的：重复测试次数越多，误判（将合数当作素数）的概率越低。

二、目标：判断 31 是否为素数，并使它是素数的置信度大于 $ 1 - \frac{1}{2^3} = 1 - \frac{1}{8} = \frac{7}{8} $

这意味着我们需要进行 至少 $ k = 3 $ 次独立的费马测试（每次选不同的 $ a $），如果全部通过，则认为 31 是素数的概率 ≥ $ 1 - \frac{1}{2^3} $。 注：严格来说，错误概率上界 $ \leq \frac{1}{2^k} $ 成立的前提是 $ n $ 不是 Carmichael 数。而 31 是较小的数，我们可以直接验证。

三、对 $ n = 31 $ 进行费马素性检测（做 3 次）

因为 31 是奇数且 > 2，我们选取 3 个不同的 $ a \in [2, 29] $，\mathrm{例}\mathrm{如}：$ a = 2, 3, 5 $

我们要计算： $ 2^{30} \bmod 31 $$ 3^{30} \bmod 31 $$ 5^{30} \bmod 31 $

由于 31 实际上是素数，根据费马小定理，这些结果都应为 1。

我们逐个验证（可用快速幂或已知结论）：

1. $ 2^{30} \bmod 31 $

由费马小定理（若 31 是素数）→ 应为 1。 计算（或查表）可知：

✅ 通过

1. $ 3^{30} \bmod 31 $

因为 31 是素数，$gcd(3,31)=1$，所以由费马小定理：

✅ 通过（也可用快速幂验证） 3. $ 5^{30} \bmod 31 $

同理，$gcd(5,31)=1$，31 若为素数 ⇒ $5^{30}\equiv 1(\mathrm{mod}31)$

✅ 通过

四、结论 三次测试均通过； 因此，根据费马素性检测，31 很可能是素数； 错误概率 ≤ $ \frac{1}{2^3} = \frac{1}{8} $，即我们有 至少 $ \frac{7}{8} $ 的置信度认为 31 是素数； 实际上，31 确实是素数（可直接验证：不能被 2,3,5 整除，且 $ \sqrt{31} \approx 5.5 $）。

✅ 最终答案：

费马素性检测基于费马小定理：若 $ p $ 为素数且 $ \gcd(a,p)=1 $，则 $ a^{p-1} \equiv 1 \pmod{p} $。 对 $ n = 31 $ 选取 $ a = 2, 3, 5 $ 进行三次测试，均有 $ a^{30} \equiv 1 \pmod{31} $，因此判定 31 为素数的置信度大于 $ 1 - \frac{1}{2^3} = \frac{7}{8} $。 故 31 被判断为素数，且满足题目要求的可靠性。

8. 设正整数n有因式分解式$n=p_1^{a_1}{p}_2^{a_2}...p_s^{a_s}$, 其中$a_i>0$, i=1,2,...s. 求n的因式分解的个数$d(n)$. ​

我们要求正整数 $ n $ 的正因数个数，通常记作 $ d(n) $（也常记为 $ \tau(n) $）。

已知： $ n $ 的素因数分解为：

其中 $ p_1, p_2, \dots, p_s $ 是互不相同的素数，且每个指数 $ a_i > 0 $。

目标： 求 $ n $ 的正因数的个数 $ d(n) $。

分析：

任何一个正因数 $ d $ of $ n $ 都可以唯一表示为：

其中每个指数 $ b_i $ 满足：

对于 $ p_1 $，指数 $ b_1 $ 有 $ a_1 + 1 $ 种选择（0 到 $ a_1 $）； 对于 $ p_2 $，指数 $ b_2 $ 有 $ a_2 + 1 $ 种选择； … 对于 $ p_s $，指数 $ b_s $ 有 $ a_s + 1 $ 种选择。

由于各素因子的选择相互独立，根据乘法原理，总共有：

个不同的正因数。

答案：

9. 证明：模m的一组简化剩余系的所有元素之和对模m必同余为0。 ​

证明：模m的一组简化剩余系的所有元素之和对模m必同余为0 定理 设 $ m > 2 $，$ S $ 是模 $ m $ 的一组简化剩余系，则 $ S $ 中所有元素之和对模 $ m $ 同余于 0。 证明

首先，简化剩余系（又称既约剩余系或缩系）是模 $ m $ 的完全剩余系中与 $ m $ 互素的数组成的子集。简化剩余系的元素个数为欧拉函数 $ \varphi(m) $。 步骤1：分析 $ \varphi(m) $ 的奇偶性

当且仅当 $ m = 1 $ 或 $ m = 2 $ 时，$ \varphi(m) $ 为奇数；当 $ m > 2 $ 时，$ \varphi(m) $ 为偶数。

证明： 若 $ m $ 有奇质因数 $ p $，则 $ \varphi(m) $ 包含因子 $ p-1 $（偶数），因此 $ \varphi(m) $ 为偶数。 原因如下：

如果 $ p $ 是奇质数（如 3, 5, 7, 11...），那么 $ p-1 $ 一定是偶数（因为奇数减1是偶数）。 例如：$ 3-1=2 $（\mathrm{偶}\mathrm{数}），$ 5-1=4 $（\mathrm{偶}\mathrm{数}），$ 7-1=6 $（偶数）

当 $ m $ 有质因数 $ p $ 时，$ \varphi(m) $ 的计算公式包含 $ p-1 $。

具体来说： 如果 $ m = p^k $（$ p $ 是质数），则 $ \varphi(m) = p^k - p^{k-1} = p^{k-1}(p-1) $ 由于 $ p-1 $ 是偶数，所以 $ \varphi(m) $ 也是偶数 更一般的情况：

如果 $ m $ 有多个质因数$p_1,p_2$...，例如 $ m = p_1^{k_1} \cdot p_2^{k_2} \cdots p_s^{k_s} $，那么：

公式中每一项均为偶数, 结果为偶数。

所以，如果 $ m $ 有奇质因数 $ p $，那么 $ \varphi(m) $ 必然包含因子 $ p-1 $（偶数），因此 $ \varphi(m) $ 一定是偶数。

举例说明：

1. $ m = 15 = 3 \times 5 $$ \varphi(15) = \varphi(3) \cdot \varphi(5) = (3-1) \cdot (5-1) = 2 \cdot 4 = 8 $ 8 是偶数，因为 $ \varphi(15) $ 包含因子 $ 3-1 = 2 $ 和 $ 5-1 = 4 $

2. $ m = 9 = 3^2 $$ \varphi(9) = 9 - 3 = 6 $ 6 是偶数，因为 $ \varphi(9) $ 包含因子 $ 3-1 = 2 $

3. $ m = 2 $（\mathrm{没}\mathrm{有}\mathrm{奇}\mathrm{质}\mathrm{因}\mathrm{数}）$ \varphi(2) = 1 $（奇数） 这是唯一的例外，因为 $ m = 2 $ 没有奇质因数

若 $ m = 2^k $ 且 $ k > 1 $，则 $ \varphi(m) = 2^k - 2^{k-1} = 2^{k-1} $，也为偶数。

因此，当 $ m > 2 $ 时，$ \varphi(m) $ 为偶数，设 $ \varphi(m) = 2k $。 步骤2：元素配对 设 $ S = {a_1, a_2, \dots, a_{\varphi(m)}} $ 是模 $ m $ 的一组简化剩余系。

对于 $ S $ 中的任意元素 $ a （a<m）$：$ \gcd(a, m) = 1 $（因为 $ a \in S $）$ \gcd(m-a, m) = \gcd(a, m) = 1 $（因为 $ \gcd(m-a, m) = \gcd(a, m) $） 所以 $ m-a $ 也在 $ S $ 中

此外，$ a \neq m-a $（否则 $ 2a = m $，即 $ m $ 为偶数且 $ a = m/2 $，此时 $ \gcd(a, m) = \gcd(m/2, m) = m/2 \geq 2 $，与 $ a \in S $ 矛盾）。

因此，$ S $ 中的元素可以两两配对：$ (a, m-a) $，每对的和为 $ m $。 步骤3：计算总和

每对元素 $ (a, m-a) $ 的和为 $ m $，所以：

由于 $ \varphi(m) $ 为偶数，$ S $ 中的所有元素可以完全配对，共有 $ \varphi(m)/2 = k $ 对。

因此，$ S $ 中所有元素之和为：

结论

当 $ m > 2 $ 时，模 $ m $ 的一组简化剩余系的所有元素之和对模 $ m $ 同余于 0。 附加说明 当 $ m = 1 $ 时，$ \varphi(1) = 1 $，简化剩余系为 $ {0} $，和为 $ 0 \equiv 0 \pmod{1} $。 当 $ m = 2 $ 时，$ \varphi(2) = 1 $，简化剩余系为 $ {1} $，和为 $ 1 \not\equiv 0 \pmod{2} $。

因此，定理的条件是 $ m > 2 $。\mathrm{示}\mathrm{例}\mathrm{验}\mathrm{证}$ m = 3 $：简化剩余系 $ {1, 2} $，和为 $ 3 \equiv 0 \pmod{3} $$ m = 4 $：简化剩余系 $ {1, 3} $，和为 $ 4 \equiv 0 \pmod{4} $$ m = 5 $：简化剩余系 $ {1, 2, 3, 4} $，和为 $ 10 \equiv 0 \pmod{5} $$ m = 6 $：简化剩余系 $ {1, 5} $，和为 $ 6 \equiv 0 \pmod{6} $

结论

当 $ m > 2 $ 时，模 $ m $ 的一组简化剩余系的所有元素之和对模 $ m $ 同余于 0。

10. 假设，p=5,q=7，根据给出的p和q和构建一个RSA加解密算法，给出其公钥与私钥，并对31进行加解密。(加解密时需要用模重复平方算法)。 ​

RSA 加解密算法：p=5, q=7 步骤 1：生成密钥对

1. 选择质数： $ p = 5 $$ q = 7 $

2. 计算模数 $ n $：

3. 计算欧拉函数 $ \varphi(n) $：

4. 选择公钥指数 $ e $： 需满足 $ 1 < e < \varphi(n) $ 且 $ \gcd(e, \varphi(n)) = 1 $ 选择 $ e = 5 $（因为 $ \gcd(5, 24) = 1 $）

5. 计算私钥指数 $ d $： 需满足 $ e \times d \equiv 1 \pmod{\varphi(n)} $ 解 $ 5d \equiv 1 \pmod{24} $ 通过扩展欧几里得算法得 $ d = 5 $（因为 $ 5 \times 5 = 25 \equiv 1 \pmod{24} $）

6. 密钥对： 公钥：$ (e, n) = (5, 35) $\mathrm{私}\mathrm{钥}：$ d = 5 $（私钥通常包含 $ d $，$ n $ 是公开的）

步骤 2：加密明文 $ m = 31 $

加密公式：$ c \equiv m^e \pmod{n} $

计算 $ c = 31^5 \mod 35 $，使用模重复平方算法： 模重复平方算法步骤：

1. 将指数 $ e = 5 $ 转换为二进制：$ 5_{10} = 101_2 $

2. 初始化： $ \text{result} = 1 $$ \text{base} = 31 \mod 35 = 31 $$ \text{exponent} = 5 $

3. 遍历指数的二进制位（从低位到高位）： 位 0 (2^0)：位为 1 $ \text{result} = (\text{result} \times \text{base}) \mod n = (1 \times 31) \mod 35 = 31 $$ \text{base} = (\text{base} \times \text{base}) \mod n = (31 \times 31) \mod 35 = 961 \mod 35 = 16 $\mathrm{位}1(2^1)：\mathrm{位}\mathrm{为}0$ \text{result} $ 不变（仍为 31） $ \text{base} = (\text{base} \times \text{base}) \mod n = (16 \times 16) \mod 35 = 256 \mod 35 = 11 $\mathrm{位}2(2^2)：\mathrm{位}\mathrm{为}1$ \text{result} = (\text{result} \times \text{base}) \mod n = (31 \times 11) \mod 35 = 341 \mod 35 = 26 $$ \text{base} = (\text{base} \times \text{base}) \mod n = (11 \times 11) \mod 35 = 121 \mod 35 = 16 $（不需要）

4. 结果：

✅ 加密结果：$ 31^5 \mod 35 = 26 $

步骤 3：解密密文 $ c = 26 $

解密公式：$ m \equiv c^d \pmod{n} $

计算 $ m = 26^5 \mod 35 $，使用模重复平方算法： 模重复平方算法步骤：

1. 将指数 $ d = 5 $ 转换为二进制：$ 5_{10} = 101_2 $

2. 初始化： $ \text{result} = 1 $$ \text{base} = 26 \mod 35 = 26 $$ \text{exponent} = 5 $

3. 遍历指数的二进制位（从低位到高位）： 位 0 (2^0)：位为 1 $ \text{result} = (\text{result} \times \text{base}) \mod n = (1 \times 26) \mod 35 = 26 $$ \text{base} = (\text{base} \times \text{base}) \mod n = (26 \times 26) \mod 35 = 676 \mod 35 = 11 $\mathrm{位}1(2^1)：\mathrm{位}\mathrm{为}0$ \text{result} $ 不变（仍为 26） $ \text{base} = (\text{base} \times \text{base}) \mod n = (11 \times 11) \mod 35 = 121 \mod 35 = 16 $\mathrm{位}2(2^2)：\mathrm{位}\mathrm{为}1$ \text{result} = (\text{result} \times \text{base}) \mod n = (26 \times 16) \mod 35 = 416 \mod 35 = 31 $

4. 结果：

✅ 解密结果：$ 26^5 \mod 35 = 31 $