算法复杂度与古典密码系统深度解析

### 算法复杂度与古典密码系统深度解析 #### 1. 模幂运算的时间复杂度 模幂运算是计算 $x^y \pmod{n}$ 的最小非负余数，其时间复杂度为 $O(k^2l)$，其中 $n$ 是 $k$ 位自然数，$y$ 是 $l$ 位自然数，且 $|x| < n$。具体步骤如下： 1. 将 $y$ 写成二进制形式：$y = e_{l - 1}2^{l - 1} + e_{l - 2}2^{l - 2} + \cdots + e_12 + e_0$，则 $x^y = x^{e_{l - 1}2^{l - 1} + e_{l - 2}2^{l - 2} + \cdots + e_12 + e_0} \pmod{n}$。 2. 依次计算 $x^{2^j} \pmod{n}$，对于 $j = 1, \cdots, l - 1$。计算 $x^{2^j} \pmod{n}$ 时，可利用 $x^{2^j} \equiv (x^{2^{j - 1}})^2 \pmod{n}$。由于每个 $x^{2^j} \pmod{n}$ 的大小最多为 $k$ 位，所以每次计算的时间复杂度为 $O(k^2)$。 3. $y$ 的二进制表示中最多有 $l$ 个 1，因此最多需要 $l$ 次乘法运算。所以，重复平方算法的时间复杂度为 $O(k^2l)$。 例如，计算 $2^{14} \pmod{21}$： - 因为 $14 = 2^3 + 2^2 + 2$，所以 $2^{14} \equiv 2^{2^3 + 2^2 + 2} \equiv 2^2 \cdot 2^{2^2} \cdot 2^{2^3} \pmod{21}$。 - 具体计算过程为： - $2^2 \pmod{21} = 4$ - $4^2 \pmod{21} = 16$ - $16^2 \pmod{21} = 4$ - 则 $2^{14} \equiv 4 \cdot 16 \cdot 4 \equiv 4 \pmod{21}$ #### 2. 算法类型 根据运行时间复杂度，算法可分为以下几类： | 算法类型 | 定义 | | --- | --- | | 多项式时间算法 | 存在正常数 $c$，使得算法的运行时间为 $O(k^c)$，则该算法为多项式时间算法。 | | 指数时间算法 | 存在正常数 $c$，使得算法的运行时间为 $O(e^{ck})$，则该算法为指数时间算法。 | | 亚指数时间算法 | 算法的运行时间介于多项式时间和指数时间之间，即比任何多项式算法都慢，但仍比指数算法快得多。设 $n, \gamma, c$ 为实数，且 $n > e$，记 $L_n[\gamma, c] = O(e^{c(\log n)^{\gamma}(\log \log n)^{1 - \gamma}})$。当 $0 < \gamma < 1$ 时，运行时间为 $L_n[\gamma, c]$ 的算法为亚指数时间算法。 | | 确定性算法 | 对于给定的特定输入，算法总是产生相同的唯一输出，其输出仅取决于输入。每次使用相同输入执行时，确定性算法遵循相同的执行路径。 | | 随机化算法 | 算法的输出不仅取决于给定输入，还取决于算法执行路径中某些点选择的随机数。对于相同的输入，算法可能产生不同的输出。随机化算法在实际中更高效。 | #### 3. 复杂度类 算法用于解决问题，问题可分为计算/搜索问题和决策问题。 | 复杂度类 | 定义 | | --- | --- | | 决策问题 | 问题的解（输出）仅取决于“是”或“否”的决策，例如判断给定数字是否为合数。 | | 计算问题 | 所需解不仅取决于“是”或“否”的决策，还需要进行一些计算，例如判断数字是否为合数，若是则找出其因数。 | | 复杂度类 P | 所有可在多项式时间内解决的决策问题的集合。 | | 复杂度类 NP | 所有决策问题的集合，对于这些问题，在给定一些额外信息（称为证书）的情况下，“是”的答案可以在多项式时间内验证。 | | 复杂度类 Co - NP | 所有决策问题的集合，对于这些问题，在给定一些额外信息（称为证书）的情况下，“否”的答案可以在多项式时间内验证。 | | 多项式时间约简 | 设 $A_1$ 和 $A_2$ 是两个决策问题。若存在一个多项式时间算法（作为 $A_1$ 的函数），对于 $A_1$ 的任何实例 $I_1$，都能构造出 $A_2$ 的实例 $I_2$，使得 $I_1$ 的答案与 $I_2$ 的答案相同，则称 $A_1$ 可在多项式时间内约简为 $A_2$，记为 $A_1 \leq_P A_2$。 | | 计算等价 | 若 $A_1 \leq_P A_2$ 且 $A_2 \leq_P A_1$，则称 $A_1$ 和 $A_2$ 计算等价。 | | NP 完全问题 | 决策问题 $A$ 满足：(i) $A \in NP$；(ii) 对于每个 $A_1 \in NP$，都有 $A_1 \leq_P A$，则称 $A$ 为 NP 完全问题。NP 完全问题是 NP 类中最难的问题。 | | NP 难问题 | 若存在某个 NP 完全问题可以在多项式时间内约简为该问题，则该问题（决策或计算/搜索问题）为 NP 难问题。NP 完全问题也是 NP 难问题。 | | 复杂度类 PP | 若存在一个概率多项式时间算法 $A$，使得 $A$ 以一定的错误概率识别 $A$ 中的任何实例 $I$，则问题 $A$ 属于类 PP。错误概率的计算公式为：$Prob[A 识别 I | I \in A] \geq \varepsilon$ 和 $Prob[A 识别 I | I \notin A] \leq \delta$，其中 $\varepsilon \in (1/2, 1]$，$\delta \in [0, 1/2)$。 | #### 4. 古典密码系统分类 古典密码系统可根据加密过程进行分类： 1. **替换密码** - **单字母替换** - **移位密码**：明文空间 $P$、密文空间 $C$ 和密钥空间 $K$ 均为 $Z_{26}$。加密算法 $E_k(x) = (x + k) \pmod{26}$，解密算法 $D_k(Y) = (Y - k) \pmod{26}$。由于密钥空间大小为 26，可进行穷举密钥搜索攻击。例如，凯撒密码是一种著名的移位密码，其中 $k = 3$。 - **仿射密码**：明文空间 $P$ 和密文空间 $C$ 为 $Z_{26}$，密钥空间 $K = \{(a, b) \in Z_{26} \times Z_{26} : \gcd(a, 26) = 1\}$。加密算法 $E_{(a, b)}