离散对数
离散对数的定义方式和对数类似.取有原根的正整数模数 \(m\) ,设其一个原根为 \(g\) .对满足 \((a,m)=1\) 的整数 \(a\)，我们知道必存在唯一的整数 \(0\leq k<\varphi(m)\) 使得 \(g^k\equiv a\pmod m\) .
我们称这个 \(k\) 为以 \(g\) 为底,模 \(m\) 的离散对数,记作 \(k=\operatorname{ind}_g a\) ,在不引起混淆的情况下可记作 \(\operatorname{ind} a\) .
看看有啥性质.
设 \(g\) 是模 \(m\) 的原根, \((a,m)=(b,m)=1\) .
- \(\operatorname{ind}_g(ab)\equiv\operatorname{ind}_ga+\operatorname{ind}_gb\pmod{\varphi(m)}\)
,进而对于 \(n\in\mathbf{N}\) 有 \(\operatorname{ind}_g(a^n)\equiv n\operatorname{ind}_ga\pmod{\varphi(m)}\) .