title: 19. 离散对数问题
tags:
  - zk
  - abstract algebra
  - group theory
  - primitive root
  - DLP
  - discrete logarithm problem​

WTF zk 教程第 19 讲：离散对数问题

这一讲，我们将探讨群的原根和离散对数问题。离散对数问题是很多加密算法的基础。

1 乘法阶

我们通常在整数模 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

2. 原根

原根的定义： 对于 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^* 不存在原根，它也不是循环群。

2.1 原根的性质

性质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_5^* 存在 \phi(\phi(5)) = \phi(4) = 2^2-2 个生成元。

性质3. 原根的个数推论： 当 p 为质数时， Z_p^* 的原根的个数为 \phi(p-1)。

性质4. 乘法阶和欧拉函数的关系： 对于 a \in Z^*_n，有 \text{ord}_n(a)|\phi(n)。

3. 离散对数

离散对数通常是定义在整数模 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。

3.1 离散对数的性质

性质1. 离散对数与欧拉函数的关系 对于群 Z^*_n，若 \gcd(g,n) = 1，那么 a \equiv g^r \pmod{n}，当且仅当 \log_ga=r \pmod{\phi(n)}，即离散对数与 r 在模 \phi(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}。

4. 离散对数问题

离散对数问题（Discrete Logarithm Problem, DLP）是对于群 Z^*_p，其中 p 为质数，给定生成元 g 和元素 a，找到离散对数 x 使得 a \equiv g^x \pmod{n} 成立。这个问题在计算上是难解的，因为目前没有已知的高效算法可以在多项式时间内解决它。

4.1 问题的难易程度

正向计算很容易：给定 a 和 x，计算 a^x 很容易，存在有效算法。

逆向计算很难：给定 a 和 b，计算 x = \log_a{b} 非常困难，主要有以下原因：

1. 非线性：群的乘法运算通常是一种非线性运算，找到符合条件的指数通常需要遍历整个群。

2. 无有效算法：当 n 为大素数时，还没有发现可以在多项式时间解决该问题的算法。

3. 穷举空间大：离散对数问题的难度也取决于是否存在原根。当模数 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 继续增大，难度会继续上升。

4.2 密码学中的应用

离散对数问题在密码学中具有广泛的应用，尤其是在公钥密码学中，下面是一些例子：

1. RSA 加密算法： 我们在数论基础的里程碑课程介绍过RSA 算法。它是一种非对称加密算法，基于大整数分解和离散对数问题的难解性。

2. Diffie-Hellman 密钥交换： Diffie-Hellman 密钥交换协议是一种通过不安全的通信渠道协商密钥的方法。它基于离散对数问题，其中两个通信方选择一个大素数和一个生成元，然后各自选择私钥，通过对生成元的离散对数运算得到公钥，最终计算出共享的密钥。离散对数问题的难解性确保了即使攻击者截获了公开的信息，也难以推导出私钥。

3. ElGamal 加密算法： ElGamal 加密算法是一种基于离散对数问题的公钥加密算法。在 ElGamal 加密中，加密者选择一个生成元和私钥，通过对生成元的离散对数运算生成公钥。解密者使用他们的私钥进行解密。离散对数问题的难解性确保了算法的安全性。

4. 椭圆曲线密码学： 椭圆曲线密码学使用椭圆曲线上的点进行加密和签名。椭圆曲线离散对数问题（ECDLP）是在椭圆曲线上寻找点的难解问题。椭圆曲线密码学提供了与传统 RSA 相比更高效的加密算法，同时提供相同或更高的安全性。

5. 总结

这一讲，我们介绍了原根和离散对数问题。原根就是整数模 n 乘法群的生成元，在数论中很重要。离散数学问题与原根相关，在密码学中是一个重要的难题，很多加密算法的安全性由离散数学问题的难度保证。

至此，WTF zk 教程群论部分的内容就完结了，接下来我们会学习环论和域论的内容！