离散对数 - 小鱼儿clouding的博客

一、初等数论回顾

在后续群（特别是循环群）的运算中，会反复使用到初等数论的一些结论。以下是几个关键概念。

1.1 整除

$A$ 整除 $B$ 意味着存在一个整数 $C$ 使得 $B = C \cdot A$。例如 $4$ 整除 $8$，$3$ 整除 $6$。反之，$3$ 不整除 $8$，$4$ 不整除 $6$。

1.2 因子（因数）

因子是一个通用概念。对于多项式有因式的概念，具体到整数就有因数的概念。例如 $8$ 的因数有 $1, 2, 4, 8$。

注意：在本课程语境中，不考虑负数，所有讨论都发生在自然数的语境下。

1.3 公因数与最大公因数 (GCD)

公因数是针对两个数而言的。例如 $8$ 和 $6$ 的公因数有 $1$ 和 $2$（$3$ 是 $6$ 的因数但不是 $8$ 的因数，$4$ 是 $8$ 的因数但不是 $6$ 的因数）。

$\gcd$ (Greatest Common Divisor) 即最大公因数。

关于”最大”的两种理解:

数值意义上的大: 在所有公因数中数值最大的那一个
整除意义上的大: 所有公因子都整除这个最大公因子

这两种理解是等价的。例如 $36$ 和 $48$ 的最大公因数是 $12$，而 $1, 2, 3, 4, 6, 12$ 全都是 $12$ 的因子。

1.4 带余除法

给定整数 $A$ 和正整数 $B$（$B > 0$），$A$ 可以写作 $Q \cdot B + R$ 的形式，其中 $0 \le R < B$。

要求 $B > 0$ 是为了保证余数 $R$ 落在 $[0, B)$ 的范围内，减轻符号表示的负担。

1.5 裴蜀定理 (Bezout’s Theorem)

对于任意整数 $A$、$B$，设 $D = \gcd(A, B)$，则存在整数 $M$、$N$ 使得:

\[M \cdot A + N \cdot B = D\]

即 $A$ 和 $B$ 的最大公因子可以被 $A$ 和 $B$ 线性组合表示。

推论: 当 $A$、$B$ 互素（$\gcd(A, B) = 1$）时，存在 $M$、$N$ 使得 $M \cdot A + N \cdot B = 1$。

裴蜀定理的证明思路

证明需要用到良序公理: 任何一个非空的非负整数集合一定有最小值。

良序公理与数学归纳法等价
对全体整数不成立（负数可以无限小）
对非负实数也不成立（开区间没有最小值）

证明步骤:

构造集合 $S = { M \cdot A + N \cdot B \mid M \cdot A + N \cdot B \ge 0 }$，即 $A$ 和 $B$ 所有非负线性组合的集合
由良序公理，$S$ 有最小值 $\min(S) = m \cdot A + n \cdot B$
用 $A$ 对 $\min(S)$ 做带余除法: $A = Q_1 \cdot \min(S) + R_1$，其中 $0 \le R_1 < \min(S)$
$R_1 = A - Q_1 \cdot \min(S)$ 也是 $A$、$B$ 的线性组合且非负，故 $R_1 \in S$
若 $R_1 \ne 0$，则 $R_1 < \min(S)$，与 $\min(S)$ 是 $S$ 中最小元素矛盾
因此 $R_1 = 0$，即 $\min(S)$ 整除 $A$；同理 $\min(S)$ 整除 $B$
$\min(S)$ 是 $A$、$B$ 的公因子；又因为任何公因子 $C$ 都整除 $\min(S)$（因为 $\min(S)$ 是 $A$、$B$ 的线性组合），所以 $\min(S)$ 是最大公因子

二、群的习题

2.1 代数结构简介

代数结构的核心思想是抽象/提炼。

许多集合和运算：整数加法/乘法、有理数加法/乘法、实数加法/乘法、模 $P$ 加法/乘法、矩阵加法/乘法、多项式加法/乘法、函数复合等，这些结构本质上有一些共同点。

代数结构就是把这些集合和运算的共同点提炼出来。类比面向对象编程：

代数结构相当于父类 (parent class) 或接口 (interface)，定义了集合和运算应有的性质
具体的集合及其运算是子类的实例化结果

例子: 整数对除法不封闭（$2/4$ 不是整数），所以整数不构成域，只是一个环；有理数对四则运算封闭（除零以外），构成一个域。复数域是实数域的扩张（加入了 $i$，使得 $x^2 + 1 = 0$ 有解）。

2.2 群的定义（从半群到群）

代数结构 = 集合 + 运算

半群

非空集合 $G$ 和一个封闭的二元运算，满足:

封闭性: $G$ 中两个元素运算后仍在 $G$ 中
结合律: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$

注意: 结合律比交换律更基本、更常见。矩阵乘法满足结合律但不满足交换律。

幺半群（含单位元的半群）

在半群基础上增加:

幺元（单位元）: 存在元素 $e \in G$，使得对任意 $a \in G$，$e \cdot a = a \cdot e = a$

（类似于加法中的 $0$ 或乘法中的 $1$）

注意: 定义中 $e \cdot a = a \cdot e = a$ 两个等式都要写完全，因为一般不假设交换律成立。

群

在幺半群基础上增加:

逆元: 对任意 $a \in G$，存在 $a^{-1} \in G$，使得 $a^{-1} \cdot a = a \cdot a^{-1} = e$

整数加法群为例: 单位元是 $0$，任意整数 $a$ 的逆元是 $-a$。

交换群（阿贝尔群）

在群的基础上增加:

交换律: 对任意 $a, b \in G$，$a \cdot b = b \cdot a$

交换律在数学中是非常珍贵、非常罕见的性质。

2.3 重要的群：模 $P$ 加法群与模 $P$ 乘法群

模 $P$ 加法群 $\mathbb{Z}_P$

元素: ${0, 1, 2, \ldots, P-1}$（共 $P$ 个元素），每个元素代表一个等价类（不是具体的数，而是一类数）。

运算: 加法后取模
单位元: $0$
$a$ 的逆元: $P - a$
对 $P$ 没有特殊要求

模 $P$ 乘法群 $\mathbb{Z}_P^*$

元素: ${ a \mid \gcd(a, P) = 1 }$，即与 $P$ 互素的数构成的集合。

运算: 乘法后取模
单位元: $1$
逆元由裴蜀定理保证存在：若 $\gcd(a, P) = 1$，则存在 $M$ 使得 $M \cdot a \equiv 1 \pmod{P}$

为什么要求元素与 $P$ 互素: 不与 $P$ 互素的元素没有乘法逆元。例如在 $\mathbb{Z}_4$ 中，$2 \times 2 = 4 \equiv 0 \pmod{4}$，无论怎么乘都得不到 $1$。解决方案是把没有逆元的元素”赶出去”，剩下有逆元的元素构成群。

封闭性: 若 $A$ 和 $P$ 互素，$B$ 和 $P$ 互素，则 $AB$ 和 $P$ 也一定互素（乘起来不可能产生新的公因子）。

若 $P$ 是素数: $\mathbb{Z}_P^* = {1, 2, 3, \ldots, P-1}$，共 $P-1$ 个元素。

具体例子:

$\mathbb{Z}_2^* = {1}$
$\mathbb{Z}_3^* = {1, 2}$
$\mathbb{Z}_4^* = {1, 3}$（$2$ 和 $4$ 不互素）
$\mathbb{Z}_7^* = {1, 2, 3, 4, 5, 6}$（$7$ 是素数）
$\mathbb{Z}_{12}^* = {1, 5, 7, 11}$

*$\mathbb{Z}_P$ 与 $\mathbb{Z}_P^$ 的区别*: | | 模 $P$ 加法群 $\mathbb{Z}_P$ | 模 $P$ 乘法群 $\mathbb{Z}_P^$ | |—|—|—| | 元素 | $0, 1, \ldots, P-1$ | 与 $P$ 互素的数 | | 元素个数 | $P$ | $\varphi(P)$ | | 对 $P$ 的要求 | 无 | 无（但 $P$ 为素数时最简单） | | 单位元 | $0$ | $1$ |

三、子群的习题

3.1 子群的定义

给定群 $(G, )$，若 $S$ 是 $G$ 的非空子集，且 $S$ 对同一个运算 $$ 也构成群（满足封闭性、结合律、有幺元、有逆元），则称 $S$ 是 $G$ 的子群。

关键: 运算必须相同。例如整数加法群 $(\mathbb{Z}, +)$ 是群，${1, -1}$ 对乘法也构成群，但 ${1, -1}$ 不是 $(\mathbb{Z}, +)$ 的子群，因为运算不同。

3.2 子群的判别法

判定 $S$ 是 $G$ 的子群有三种方法:

定义法: 直接验证 $S$ 是 $G$ 的子集且对同一运算构成群（太繁琐，一般不用）。

两步判别法:

对任意 $a, b \in S$，$a * b \in S$（封闭性）
对任意 $a \in S$，$a^{-1} \in S$（逆元存在）

第2条同时保证了单位元的存在：$a$ 在，$a$ 的逆元也在，则 $a * a^{-1} = e$ 也在。

一步判别法:

对任意 $a, b \in S$，$a * b^{-1} \in S$。

由此可推出：

取 $b = a$，则 $a * a^{-1} = e \in S$（单位元存在）
取 $a = e$，则 $e * b^{-1} = b^{-1} \in S$（逆元存在）
由上两条即可得封闭性和群的所有性质

3.3 阶的概念

阶 (order) 在群中有两种含义:

群的阶 $|G|$

群 $G$ 的元素个数。可以是有限的，也可以是无限的。

无限阶的例子: $(\mathbb{Z}, +)$，$(\mathbb{Q} \setminus {0}, \times)$
有限阶的例子: $\mathbb{Z}_P$（阶为 $P$），$\mathbb{Z}_P^*$（阶为 $\varphi(P)$）

欧拉函数 $\varphi(N)$

$\varphi(N) =

\mathbb{Z}_N^*

$ = 与 $N$ 互素的 ${1, 2, \ldots, N-1}$ 中元素的个数。

具体计算:

$\varphi(2) = 1$
$\varphi(3) = 2$
$\varphi(7) = 6$
$\varphi(12) = 4$

若 $P$ 是素数: $\varphi(P) = P - 1$

一般公式: 若 $N = p_1^{k_1} \cdot p_2^{k_2} \cdots p_m^{k_m}$（素因子分解），则:

\[\varphi(N) = N \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right)\]

例:

\[\varphi(90) = 90 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) \times \left(1 - \frac{1}{5}\right) = 90 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = 24\]

直觉理解: $N$ 的每一个素因子都会”消灭”一批不互素的数。素因子越小，消灭的越多（模 $2$ 的偶数占一半，模 $3$ 的倍数占三分之一…）。素因子出现的次数（$k_1, k_2, \ldots$）不影响公式，因为只要有了一个素因子 $p$，所有含 $p$ 的数就已经不互素了。

元素的阶 $\operatorname{ord}(a)$

对于 $a \in G$，$a$ 的阶定义为使得 $a^n = e$ 的最小正整数 $n$。若不存在这样的 $n$，则定义为 $+\infty$。

整数加法群中的例子:

$\operatorname{ord}(0) = 1$（一个 $0$ 相加就等于 $0$）
$\operatorname{ord}(a) = +\infty$（$a \ne 0$ 时，多少个 $a$ 相加都不等于 $0$）

模 $14$ 加法群 $\mathbb{Z}_{14}$ 中的例子:

$\operatorname{ord}(0) = 1$
$\operatorname{ord}(1) = 14$（$14$ 个 $1$ 相加 $\equiv 0 \pmod{14}$）
$\operatorname{ord}(2) = 7$
$\operatorname{ord}(3) = 14 / \gcd(3, 14) = 14$（需要逐步计算验证）

模 $10$ 乘法群 $\mathbb{Z}_{10}^* = {1, 3, 7, 9}$ 中的例子:

$\operatorname{ord}(1) = 1$
$\operatorname{ord}(3) = 4$（$3, 9, 7, 1$）
$\operatorname{ord}(7) = 4$（$7, 9, 3, 1$）
$\operatorname{ord}(9) = 2$（$9, 1$）

拉格朗日定理: 元素的阶一定是群的阶的因子。例如 $\mathbb{Z}_{10}^*$ 的阶为 $4$，元素的阶只能是 $1$、$2$ 或 $4$。

四、循环群的习题

4.1 由单个元素生成的子群

对于群 $G$ 和元素 $a \in G$，定义:

\[\langle a \rangle = \{ a^n \mid n \in \mathbb{Z} \}\]

即 $a$ 的所有幂次构成的集合。$\langle a \rangle$ 是 $G$ 的子群（单位元 $a^0 = e$ 在其中，逆元 $a^{-n}$ 也在其中）。

4.2 循环群的定义

若存在元素 $a \in G$ 使得 $\langle a \rangle = G$，则称 $G$ 为循环群，$a$ 为 $G$ 的生成元。

循环群的关键特征: 用一个元素就能描述整个群。

4.3 循环群的例子

$\mathbb{Z}_{14}$ 是循环群: $1$ 是生成元（$\operatorname{ord}(1) = 14$），$3$ 也是生成元（$\operatorname{ord}(3) = 14$）。但 $2$ 不是生成元（$\operatorname{ord}(2) = 7$，只能生成偶数元素）。

$\mathbb{Z}_{10}^* = {1, 3, 7, 9}$ 是循环群: $3$ 和 $7$ 是生成元（阶都为 $4$），$1$ 和 $9$ 不是生成元。

$\mathbb{Z}_8^* = {1, 3, 5, 7}$ 不是循环群:

$\operatorname{ord}(1) = 1$
$\operatorname{ord}(3) = 2$（$3^2 = 9 \equiv 1 \pmod{8}$）
$\operatorname{ord}(5) = 2$（$5^2 = 25 \equiv 1 \pmod{8}$）
$\operatorname{ord}(7) = 2$（$7^2 = 49 \equiv 1 \pmod{8}$）

所有元素的阶（$1$ 或 $2$）都不等于群的阶 $4$，因此没有生成元，不是循环群。

4.4 关于模 $P$ 乘法群是否为循环群

若 $P$ 是素数，则 $\mathbb{Z}_P^*$ 一定是循环群
若 $P$ 不是素数，$\mathbb{Z}_P^$ 不一定是循环群（如 $\mathbb{Z}_8^$ 就不是）

重要区分:

$\langle a \rangle$ 作为 $G$ 的子群总是存在的
循环群要求存在某个 $a$ 使得 $\langle a \rangle = G$

五、循环群上的离散对数问题

5.1 问题定义

给定循环群 $G$，生成元 $a$，任取元素 $b$，求 $x$ 使得:

\[a^x = b\]

在实数域上这很简单（取对数即可），但在离散群上这是一个非常困难的问题。

5.2 例题

例 1: $\mathbb{Z}_7^*$ 中，生成元为 $3$，求 $3^x = 4$。答: $x = 4$（逐步验证: $3^1 = 3,\ 3^2 = 2,\ 3^3 = 6,\ 3^4 = 4$）。

例 2: $\mathbb{Z}_{41}^*$ 中，生成元为 $6$，求 $6^x = 29$。答: $x = 7$（逐步验证: $6^1 = 6,\ 6^2 = 36,\ 6^3 = 11,\ 6^4 = 25,\ 6^5 = 27,\ 6^6 = 39,\ 6^7 = 29$，所有运算 $\bmod\ 41$）。

例 3: $\mathbb{Z}_{41}^*$ 中，求 $6^x = 15$。答: $x = 37$（穷举法不现实，需要更好的算法）。

5.3 大步小步算法 (Baby-step Giant-step)

穷举法的时间复杂度为 $O(N)$。大步小步算法将复杂度降低到 $O(\sqrt{N})$。

算法原理:

设群的阶为 $N$，取 $M = \lceil \sqrt{N} \rceil$
对 $x$ 做带余除法: $x = iM + j$，其中 $0 \le j < M$，$0 \le i \le M$
则 $a^x = b$ 变为 $a^{iM + j} = b$，即 $a^j = b \cdot (a^{-M})^i$
预计算左边的表: $a^0, a^1, a^2, \ldots, a^M$（Baby steps）
逐步计算右边: $b,\ b \cdot a^{-M},\ b \cdot a^{-2M}, \ldots$（Giant steps）
当右边某一项与左边表中的某项匹配时，就找到了 $i$ 和 $j$，从而得到 $x = iM + j$

复杂度: 约 $O(2\sqrt{N})$。例如 $N = 40$ 时，穷举需要约 $40$ 次，大步小步只需约 $14$ 次。

5.4 离散对数问题的困难性

离散对数是计算机科学中少有的确认困难的问题。在实际信息安全应用中:

群的阶可能取到 $2^{256}$
即使用大步小步算法，复杂度也是 $2^{128}$
宇宙大小约 $2^{90}$，即动用全宇宙资源也无法求解

5.5 离散对数求解示例

给定具体的 $A$、$B$、$N$，目标是求解满足 $A^x \equiv B \pmod N$ 的 $x$。当 $N$ 约为 $10^{11}$ 量级时，穷举法会超时，必须使用大步小步算法，将计算量降到约 $10^6$ 量级。