问题及解答

定义.  设 $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 .
\]

1.   $2^{11-1}=1024=93*11+1$, 故 $2^{11-1}\equiv 1\pmod{11}$. 

一般的, 有 Euler 定理, 若 $a$ 与 $m$ 互素, 则存在 $n=\phi(m)$, 使得 $a^{n}\equiv 1\pmod m$.

>> 2^10 mod 11
in> 2^10@11

out> 1
------------------------

2.   设 $a^n\equiv b\pmod p$, $a^m\equiv c\pmod p$, 则

\[
a^n\cdot a^m\equiv bc\pmod p ,
\]

即 

\[
a^{n+m}\equiv (bc\mod p)\ \pmod p .
\]

因此,

\[
n+m=\log_a (bc\mod p).
\]

3.  据条件 $y_1=a^k$, $y_2=xb^k$, 则有

\[
y_2 y_1^{n(p-2)}=xb^k (a^k)^{n(p-2)}
\]

\[
\begin{split}
&a^n\equiv b\pmod p\\
\Rightarrow\ & (a^n)^{k(p-2)}\equiv b^{k(p-2)}\pmod p\\
\Rightarrow\ &a^{nk(p-2)}\equiv b^{k(p-2)}\pmod p\\
\Rightarrow\ &b^k\cdot a^{nk(p-2)}\equiv b^k\cdot b^{k(p-2)}\pmod p\\
\Rightarrow\ &b^k a^{nk(p-2)}\equiv b^{k(p-1)}\pmod p ,
\end{split}
\]

而

\[a^{p-1}\equiv 1\pmod p \Rightarrow a^{n(p-1)}\equiv 1\pmod p\]

\[a^n\equiv b\pmod p \Rightarrow a^{n(p-1)}\equiv b^{p-1}\pmod p\]

故

\[
b^{p-1}\equiv 1\pmod p .
\]

因此,

\[
b^k a^{nk(p-2)}\equiv b^{k(p-1)}\equiv 1\pmod p .
\]

从而

\[
x\equiv y_2 y_1^{n(p-2)}\pmod p .
\]