Skip to content

Latest commit

 

History

History
159 lines (89 loc) · 8.98 KB

readme.md

File metadata and controls

159 lines (89 loc) · 8.98 KB
title tags
19. 离散对数问题
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_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)$。证毕。

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)$ 下同余。

点我展开证明👀

必要性

$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}$

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 教程群论部分的内容就完结了,接下来我们会学习环论和域论的内容!