[Def] 离散对数
定义. 设 $p$ 为素数, 对于正整数 $a$, $b$, 若存在 $n$ 使得
\[
a^n\equiv b\pmod p ,
\]
则称 $n$ 为 $b$ 的以 $a$ 为底的离散对数. 记作 $n=\log_a b$.
2024年九省联考的一道题目是这样的.
设 $p$ 为素数, 令 $X_p=\{1,2,\ldots,p-1\}$. 取 $a\in X_p$, 使得满足 $1,a,a^2,\ldots,a^{p-2}$ （在模 $p$ 之下）两两不同余.
1. 求 $a^{p-1}\pmod p$, 其中 $a=2$, $p=11$.
2. 证明, 对任意 $b,c\in X_p$, 下式成立
\[
\log_a (bc \mod p)\equiv \log_a b+\log_a c\pmod{p-1}.
\]
3. 已知 $n=\log_a b$, 对于 $x\in X_p$, $k\in\{1,2,\ldots,p-2\}$. 设 $y_1=a^k$, $y_2=xb^k$, 证明:
\[
x\equiv y_2 y_1^{n(p-2)}\pmod p .
\]