离散对数

1. 核心定义

离散对数是实数对数在模运算环境下的推广。建立离散对数的前提是模 $m$ 必须存在原根。

• 定义：设 $g$ 是模 $m$ 的一个 原根，对于任意与 $m$ 互素的整数 $a$（即 $(a,m)=1$），满足以下同余式的唯一整数 $\gamma$： $a\equiv g^{\gamma }(\mathrm{mod}m),0\le \gamma \le \phi (m)-1$ 称为以 $g$ 为底 $a$ 的 离散对数（或指标，Index）。
• 记号：通常记为 $in{d}_g(a)$ 或 ${\log }_{g}a$。

2. 运算性质 (算术规则)

离散对数完美继承了普通对数“将乘法变加法”的特性，但要注意运算是在 模 $\phi (m)$ 的加法群中进行的。

1. 特殊值：
   • $in{d}_g(1)=0$
   • $in{d}_g(g)=1$
2. 乘积变和： $in{d}_g(a\cdot b)\equiv in{d}_g(a)+in{d}_g(b)(\mathrm{mod}\phi (m))$
3. 幂次变乘积： $in{d}_g(a^n)\equiv n\cdot in{d}_g(a)(\mathrm{mod}\phi (m))$
4. 换底公式：若 $g_1$ 也是原根，则 $in{d}_g(a)\equiv in{d}_{g_1}(a)\cdot in{d}_g(g_1)(\mathrm{mod}\phi (m))$

注意

指数形式 mod($x$),对数形式 mod($\varphi (x)$)

进行变形时，需要注意 mod 的增根、少根，代回验证。

3. 重要关联：指数与离散对数

元素 $a$ 的 指数（Order，即阶）可以通过其离散对数直接计算： $or{d}_m(a)=\frac{\phi (m)}{\gcd (in{d}_g(a),\phi (m))}$ 意义：这告诉我们，一个元素的阶取决于它的离散对数与群阶 $\phi (m)$ 的最大公约数。

类比

想象一个圆形跑道，全长 $\phi (m)$ 米。

• 原根 $g$：每次跳 1米。它需要跳 $\phi (m)$ 次才能回到起点（转一圈）。
• 元素 $a$：每次跳 $k$ 米（$k$ 就是离散对数）。

问题：$a$ 需要跳多少次（$d$）才能回到起点？

• 如果 $a$ 每次跳的距离 $k$ 能整除跑道长度 $\phi (m)$，那么它只需要跳 $\phi (m)/k$ 次。
• 如果 $k$ 不能整除跑道长度，它可能需要多跑几圈才能恰好落在起点。
• 公式含义：$\gcd (k,\phi (m))$ 代表了 $a$ 的步长 $k$ 与跑道总长 $\phi (m)$ 的“公共节奏”。去除这个公共部分后，剩下的就是 $a$ 需要跳的次数。

4. 离散对数问题 (DLP)

这是密码学关注的核心。

• 正向计算（易）：给定 $m,g,\gamma$，计算 $a\equiv g^{\gamma }(\mathrm{mod}m)$。这是模幂运算，使用“平方-乘”算法可以非常快地算出。
• 逆向计算（难）：给定 $m,g,a$，求 $\gamma$ 使得 $a\equiv g^{\gamma }(\mathrm{mod}m)$。这就是 离散对数问题 (Discrete Logarithm Problem, DLP)。
  • 当 $m$ 是大素数时，目前没有已知的高效多项式时间算法能解出 $\gamma$。

5. 典型应用

利用 DLP 的困难性构建的密码体制：

1. Diffie-Hellman 密钥交换：允许双方在公开信道协商出共享密钥 $g^{ab}$，攻击者截获 $g^a$ 和 $g^b$ 无法推算出 $g^{ab}$。
2. ElGamal 加密/签名：安全性直接依赖于在有限域上求解离散对数的难度。
3. DSA (Digital Signature Algorithm)：美国国家标准数字签名算法，基于 DLP 变体。

---

计算示例

模数 $m=17$，原根选 $g=3$（$\phi (17)=16$）。

1. 建立表（部分）：
   • $3^1\equiv 3⟹in{d}_3(3)=1$
   • $3^2\equiv 9⟹in{d}_3(9)=2$
   • $3^3\equiv 27\equiv 10⟹in{d}_3(10)=3$
2. 利用性质计算：求 $in{d}_3(13)$。 已知 $13\equiv -4\equiv -1\cdot 2^2(\mathrm{mod}17)$。
   • $in{d}_3(-1)=in{d}_3(16)=in{d}_3(3^8)=8$（威尔逊定理/原根性质）。
   • 我们需要知道 $in{d}_3(2)$。假设已知 $in{d}_3(2)=14$（因为 $3^{14}\equiv 2$）。
   • $in{d}_3(13)=in{d}_3(-1)+2\cdot in{d}_3(2)(\mathrm{mod}16)$
   • $=8+2(14)=8+28=36\equiv 4(\mathrm{mod}16)$。
   • 验证：$3^4=81=4\times 17+13\equiv 13$。正确。