离散对数

如果模 m 有一个 原根 g，则

$$g^0,g^1,\dots ,g^{\phi (m)-1}$$

组成模 m 的 简化剩余系，也就是对 a，$(a,m)=1$，都可以唯一表示为

$$a\equiv g^{\gamma },0\le \gamma \le \phi (m)-1$$

$\gamma$ 为以 g 为底的 a 对模 m 的离散对数

$$\gamma =in{d}_{g}a⟺a\equiv g^{in{d}_{g}a}(modm)$$

---

有

$$a\equiv b(modm)⟺in{d}_{g}a\equiv in{d}_{g}b(mod\phi (m))$$ $$in{d}_{g}0=1,in{d}_{g}g=1$$ $$in{d}_g(ab)\equiv in{d}_g(a)+in{d}_g(b)(mod\phi (m))$$ $$in{d}_g{a}^n\equiv n\cdot in{d}_{g}a(mod\phi (m))$$

如果 $g_1$ 也是模 m 的一个原根

$$in{d}_{g}a\equiv in{d}_{g_1}a\cdot in{d}_g{g}_1(mod\phi (m))$$

---

和 指数 的关系

$$or{d}_m(a)=\frac{\phi (m)}{(\phi (m),in{d}_{g}a)}$$

离散对数难解问题

DH 密钥交换协议

ElGamal密码体制

数字签名