19.离散对数问题

title: 19. 离散对数问题 tags: zk abstract algebra group theory primitive root DLP discrete logarithm problem WTF zk 教程第 19 讲：离散对数问题 这一讲，我们将探讨群的原根和离散对数问题。离散对数问题是很多加密算法的基础。 1 乘法阶 我们通常在整数模 $n$ 乘法群 $Zn^$ 中讨论原根这个概念。所以，在引入原根的定义之前，我们先介绍乘法阶。 乘法阶的定义： 在群 $Zn^$ 中，对于任意元素 $a$，它的乘法阶定义为使得 $a^k \equiv 1 \mod n$ 成立的最小正整数 $k$。乘法阶通常用符号 $\text{ord}n(a)$ 表示。 简而言之，乘法阶是元素自身与自身相乘，直到得到群的单位元素所需要的最小次数。 举个例子，考虑模 $5$ 的乘法群 $Z5^ = \set{1,2,3,4}$。我们可以验证 $4$ 的乘法阶为 $2$，因为： $4^1 \equiv 4 \mod 5$ $4^2 \equiv 1 \mod 5$ 原根 原根的定义： 对于 $Z^ n...