| title |
tags |
19. 离散对数问题 |
zk |
abstract algebra |
group theory |
primitive root |
DLP |
discrete logarithm problem |
|
这一讲，我们将探讨群的原根和离散对数问题。离散对数问题是很多加密算法的基础。
我们通常在整数模 $n$ 乘法群 $Z_n^*$ 中讨论原根这个概念。所以，在引入原根的定义之前，我们先介绍乘法阶。
乘法阶的定义： 在群 $Z_n^*$ 中，对于任意元素 $a$，它的乘法阶定义为使得 $a^k \equiv 1 \mod n$ 成立的最小正整数 $k$。乘法阶通常用符号 $\text{ord}_n(a)$ 表示。
简而言之，乘法阶是元素自身与自身相乘，直到得到群的单位元素所需要的最小次数。
举个例子，考虑模 $5$ 的乘法群 $Z_5^* = \set{1,2,3,4}$。我们可以验证 $4$ 的乘法阶为 $2$，因为：
- $4^1 \equiv 4 \mod 5$
- $4^2 \equiv 1 \mod 5$
原根的定义： 对于 $Z^* _n$ 中的一个元素 $g$，如果 $g$ 的各次幂能够生成群 $Z^* _n$ 中的所有元素，则称 $g$ 为 $Z^* _n$ 的原根。
换句话说，对于每个 $a \in Z_n^*$，存在一个整数 $k$ 使得 $g^k \equiv a \mod n$。
原根这个概念和循环群的生成元联系紧密：当整数模 $n$ 乘法群不一定是循环群，但当它是循环群时原根是它的生成元。因此，生成元的性质也都可以放到原根上。原根的阶（乘法阶）等于 $Z_n^*$ 的阶，也就是 $\phi(n)$。
举个例子，考虑模 $7$ 的乘法群 $Z_7^* = \set{1, 2, 3, 4, 5, 6}$。我们可以验证 $3$ 是一个原根，因为：
- $3^1 \equiv 3 \mod 7$
- $3^2 \equiv 2 \mod 7$
- $3^3 \equiv 6 \mod 7$
- $3^4 \equiv 4 \mod 7$
- $3^5 \equiv 5 \mod 7$
- $3^6 \equiv 1 \mod 7$
在这个例子中，$3$ 的各次幂生成了群 $Z_7^*$ 的所有元素。
再举个例子，考虑模 $8$ 的乘法群 $Z_8^* = \set{1, 3, 5, 7}$。我们依次计算其中元素的各次幂：
- $1^1 \equiv 1 \mod 8$
-
$3^1 \equiv 3 \mod 8$, $3^2 \equiv 1 \mod 8$
-
$5^1 \equiv 5 \mod 8$, $5^2 \equiv 1 \mod 8$
-
$7^1 \equiv 7 \mod 8$, $7^2 \equiv 1 \mod 8$
我们发现没有元素的各次幂可以生成整个群，因此 $Z_8^*$ 不存在原根，它也不是循环群。
性质1. 原根的存在性： 当且仅当 $n = 2, 4, p^k, 2p^k$ 的形式时，$Z_n^*$ 存在原根，其中 $p$ 是奇素数， $k$ 是正整数。
证明比较复杂，超出本教程的范围，大家记住结论就好。
举几个例子， $Z_5^$ 存在原根，比如 $2$； $Z_7^$ 存在原根，比如 $3$，这两个也都是循环群。而 $Z_8^*$ 不存在原根，也不是循环群，因为 $8 = 2^3$，不符合 $n = 2, 4, p^k, 2p^k$ 的形式。
性质2. 原根的个数： 当 $Z_n^*$ 存在原根时（ $n = 2, 4, p^k, 2p^k$），原根的个数为 $\phi(\phi(n))$。
点我展开证明👀
假设 $Z_n^$ 的原根为 $g$，它的阶与群 $Z_n^$ 的阶相等，为 $\phi(n)$。根据循环群的阶的性质 5，它的生成元数量为 $\phi(\phi(n))$。证毕。
举几个例子， $Z_5^*$ 存在 $\phi(\phi(5)) = \phi(4) = 2^2-2$ 个生成元。
性质3. 原根的个数推论： 当 $p$ 为质数时， $Z_p^*$ 的原根的个数为 $\phi(p-1)$。
点我展开证明👀
当 $p$ 为质数时， $\phi(p) = p-1$，根据上一条性质，得到 $Z_p^*$ 的原根的个数为 $\phi(p-1)$。
性质4. 乘法阶和欧拉函数的关系： 对于 $a \in Z^*_n$，有 $\text{ord}_n(a)|\phi(n)$。
点我展开证明👀
$Z_n^*$ 的阶为 $\phi(n)$。根据循环群的阶的性质 6，元素 $a$ 的阶整除群的阶，即 $\text{ord}_n(a)|\phi(n)$。证毕。
离散对数通常是是在整数模 $n$ 乘法群 $Z^* _n$。当 $n = 2, 4, p^k, 2p^k$ 的形式时， $Z^* _n$ 是循环群，存在原根。
对于群 $Z^*_n$，其中的原根 $g$ 和元素 $a$，离散对数 $\log_gb$ 是使得 $g^x \equiv a$ 成立的 $x$，记为 $x = \log_gb$。
性质1. 离散对数与欧拉函数的关系 对于群 $Z^*_n$，若 $\gcd(g,n) = 1$，那么 $a \equiv g^r \pmod{n}$，当且仅当 $\log_ga=r \pmod{\phi(n)}$，即离散对数与 $r$ 在模 $\phi(n)$ 下同余。
点我展开证明👀
必要性
设 $x = \log_ga$，根据 $a \equiv g^r \pmod{n}$，那么有 $g^x \equiv g^r \pmod{n}$。根据欧拉公式：如果整数 $a$ 和正整数 $n$ 互质（即 $\gcd(g,n)=1$），那么 $g^{\phi(n)} \equiv 1 \pmod{n}$。也就是说，我们可以在等式的任意地方乘以 $g^{\phi(n)}$，同余关系仍然存在。对于任意整数 $k$，有 $g^x \equiv g^r g^{k\phi(n)} \equiv g^{r +k\phi(n)}\pmod{n}$，也就是 $x = r +k\phi(n)$，即 $x \equiv r \pmod{\phi(n)}$。证毕。
充分性
若 $x \equiv r \pmod{\phi(n)}$，即 $x = r + k\phi(n)$。有 $g^x \equiv g^{r + k\phi(n)} \equiv g^{r} g^{k\phi(n)} \pmod{n}$ 成立。根据欧拉公式， $g^{\phi(n)} = 1$，因此有 $g^x \equiv g^r \pmod{n}$。
举个例子，对于 $Z^*_5$，它的一个原根为 $2$，欧拉函数 $\phi(5) = 4$。有 $4 \equiv 2^2 \pmod{5}$，那么 $4 \equiv 2^6 \pmod{5}$ 和 $4 \equiv 2^{10} \pmod{5}$ 也成立。你可以在指数上任意加减 $\phi(n)$ 的倍数，同余关系在模 $n$ 下仍然成立。
我们也可以利用这个性质简化模幂的求解。对于 $Z^*_7$，它的一个原根为 $3$，欧拉函数 $\phi(7) = 6$。有 $3^{100} \equiv 3^{100 \pmod{6}} \equiv 3^{4 \pmod{6}} \equiv 81 \equiv 4 \pmod{7}$。
离散对数问题（Discrete Logarithm Problem, DLP）是对于群 $Z^*_p$，其中 $p$ 为质数，给定生成元 $g$ 和元素 $a$，找到离散对数 $x$ 使得 $a \equiv g^x \pmod{n}$ 成立。这个问题在计算上是难解的，因为目前没有已知的高效算法可以在多项式时间内解决它。
正向计算很容易：给定 $a$ 和 $x$，计算 $a^x$ 很容易，存在有效算法。
逆向计算很难：给定 $a$ 和 $b$，计算 $x = \log_a{b}$ 非常困难，主要有以下原因：
-
非线性：群的乘法运算通常是一种非线性运算，找到符合条件的指数通常需要遍历整个群。
-
无有效算法：当 $n$ 为大素数时，还没有发现可以在多项式时间解决该问题的算法。
-
穷举空间大：离散对数问题的难度也取决于是否存在原根。当模数 $n$ 存在原根时，离散对数问题通常是困难的，因为原根 $g$ 的幂运算形成了模 $n$ 的一个全体剩余系。相反，如果不存在原根，离散对数问题的解可能更容易找到。
我们先举一个简答的例子：对于 $Z^*_5$，找到满足 $3^x \equiv 2 \pmod{5}$ 的整数 $x$。我们可以遍历 $3$ 的各次幂：
-
$3^2 \equiv 4 \pmod{5}$
-
$3^3 \equiv 2 \pmod{5}$
因此，对于 $Z^*_5$ 中， $3 = \log_3{2}$。
在举一个难的例子：对于 $Z^*_{31}$，找到满足 $13^x \equiv 17 \pmod{31}$ 的整数 $x$。你可以尝试一下。当 $n$ 继续增大，难度会继续上升。
离散对数问题在密码学中具有广泛的应用，尤其是在公钥密码学中，下面是一些例子：
-
RSA 加密算法： 我们在数论基础的里程碑课程介绍过RSA 算法。它是一种非对称加密算法，基于大整数分解和离散对数问题的难解性。
-
Diffie-Hellman 密钥交换： Diffie-Hellman 密钥交换协议是一种通过不安全的通信渠道协商密钥的方法。它基于离散对数问题，其中两个通信方选择一个大素数和一个生成元，然后各自选择私钥，通过对生成元的离散对数运算得到公钥，最终计算出共享的密钥。离散对数问题的难解性确保了即使攻击者截获了公开的信息，也难以推导出私钥。
-
ElGamal 加密算法： ElGamal 加密算法是一种基于离散对数问题的公钥加密算法。在 ElGamal 加密中，加密者选择一个生成元和私钥，通过对生成元的离散对数运算生成公钥。解密者使用他们的私钥进行解密。离散对数问题的难解性确保了算法的安全性。
-
椭圆曲线密码学： 椭圆曲线密码学使用椭圆曲线上的点进行加密和签名。椭圆曲线离散对数问题（ECDLP）是在椭圆曲线上寻找点的难解问题。椭圆曲线密码学提供了与传统 RSA 相比更高效的加密算法，同时提供相同或更高的安全性。
这一讲，我们介绍了原根和离散对数问题。原根就是整数模 $n$ 乘法群的生成元，在数论中很重要。离散数学问题与原根相关，在密码学中是一个重要的难题，很多加密算法的安全性由离散数学问题的难度保证。
至此，WTF zk 教程群论部分的内容就完结了，接下来我们会学习环论和域论的内容！