《2025年金考卷特快专递高中数学》

19. (17分)离散对数在密码学中有重要的应用. 设$p$是素数,集合$X = \{1,2,\cdots,p - 1\}$,若$u,v\in X,m\in\mathbf{N}$,记$u\otimes v$为$uv$除以$p$的余数,$u^{m,\otimes}$为$u^{m}$除以$p$的余数;设$a\in X,1,a,a^{2,\otimes},\cdots,a^{p - 2,\otimes}$两两不同,若$a^{n,\otimes}=b(n\in\{0,1,\cdots,p - 2\})$,则称$n$是以$a$为底$b$的离散对数,记为$n=\log(p)_{a}b$.
(1)若$p = 11,a = 2$,求$a^{p - 1,\otimes}$;
(2)对$m_{1},m_{2}\in\{0,1,\cdots,p - 2\}$,记$m_{1}\oplus m_{2}$为$m_{1}+m_{2}$除以$p - 1$的余数(当$m_{1}+m_{2}$能被$p - 1$整除时,$m_{1}\oplus m_{2}=0$). 证明:$\log(p)_{a}(b\otimes c)=\log(p)_{a}b\oplus\log(p)_{a}c$,其中$b,c\in X$;
(3)已知$n=\log(p)_{a}b$. 对$x\in X,k\in\{1,2,\cdots,p - 2\}$,令$y_{1}=a^{k,\otimes},y_{2}=x\otimes b^{k,\otimes}$. 证明:$x=y_{2}\otimes y_{1}^{n(p - 2),\otimes}$.

答案： 19. 新定义问题 + 同余问题 + 离散对数
解：
(1)$2^{10}=93×11 + 1$,所以$2^{10,\textcircledast}=1$. (4分)
(2)第1步:证明$a^{n_{1},\textcircledast}\textcircledast a^{n_{2},\textcircledast}=a^{n_{1}+n_{2},\textcircledast}$
记$a^{n_{1}}=a^{n_{1},\textcircledast}+m_{1}p,a^{n_{2}}=a^{n_{2},\textcircledast}+m_{2}p,a^{n_{1},\textcircledast}×a^{n_{2},\textcircledast}=a^{n_{1},\textcircledast}\textcircledast a^{n_{2},\textcircledast}+kp$,其中$m_{1},m_{2},k$是整数,则$a^{n_{1}+n_{2}}=a^{n_{1}}\cdot a^{n_{2}}=a^{n_{1},\textcircledast}\textcircledast a^{n_{2},\textcircledast}+(m_{1}a^{n_{2},\textcircledast}+m_{2}a^{n_{1},\textcircledast}+m_{1}m_{2}p + k)p$,可知$a^{n_{1},\textcircledast}\textcircledast a^{n_{2},\textcircledast}=a^{n_{1}+n_{2},\textcircledast}$.
第2步:证明$a^{p - 1,\textcircledast}=1$
因为$1,a,a^{2,\textcircledast},\cdots,a^{p - 2,\textcircledast}$两两不同,所以存在$i\in\{0,1,\cdots,p - 2\}$,使得$a^{p - 1,\textcircledast}=a^{i,\textcircledast}$,即$a^{p - 1}-a^{i}=a^{i}(a^{p - 1 - i}-1)$可以被$p$整除,于是$a^{p - 1 - i}-1$可以被$p$整除,即$a^{p - 1 - i,\textcircledast}=1$. 若$i\neq0$,则$p - 1 - i\in\{1,2,\cdots,p - 2\},a^{p - 1 - i,\textcircledast}\neq1$,因此$i = 0,a^{p - 1,\textcircledast}=1$. (11分)
第3步:由上述两个结论证明$\log(p)_{a}(b\textcircledast c)=\log(p)_{a}b\oplus\log(p)_{a}c$
记$n=\log(p)_{a}b,m=\log(p)_{a}c,n + m=n\oplus m + l(p - 1)$,其中$l$是整数,则$b\textcircledast c=a^{n,\textcircledast}\textcircledast a^{m,\textcircledast}=a^{n + m,\textcircledast}=a^{n\oplus m + l(p - 1),\textcircledast}=a^{n\oplus m,\textcircledast}\textcircledast a^{l(p - 1),\textcircledast}=a^{n\oplus m,\textcircledast}$,即$\log(p)_{a}(b\textcircledast c)=\log(p)_{a}b\oplus\log(p)_{a}c$. (13分)
(3)第1步:根据题设和前面的结论写出$y_{2}$和$y_{1}^{n(p - 2),\textcircledast}$的式子
由题设和
(2)的证明知
$y_{2}=x\textcircledast b^{k,\textcircledast}$
$=x\textcircledast\overbrace{(b\textcircledast b\textcircledast\cdots\textcircledast b)}^{k}$
$=x\textcircledast\overbrace{a^{n,\textcircledast}\textcircledast a^{n,\textcircledast}\textcircledast\cdots\textcircledast a^{n,\textcircledast}}^{k}$
$=x\textcircledast\overbrace{a\textcircledast a\textcircledast\cdots\textcircledast a}^{nk}$,
$y_{1}^{n(p - 2),\textcircledast}=\overbrace{y_{1}\textcircledast y_{1}\textcircledast\cdots\textcircledast y_{1}}^{n(p - 2)}$
$=\overbrace{a^{k,\textcircledast}\textcircledast a^{k,\textcircledast}\textcircledast\cdots\textcircledast a^{k,\textcircledast}}^{n(p - 2)}$
$=\overbrace{a^{p - 2,\textcircledast}\textcircledast a^{p - 2,\textcircledast}\textcircledast\cdots\textcircledast a^{p - 2,\textcircledast}}^{nk}$.
第2步:由上面两个式子得到$y_{2}\textcircledast y_{1}^{n(p - 2),\textcircledast}$的式子
故$y_{2}\textcircledast y_{1}^{n(p - 2),\textcircledast}=x\textcircledast\overbrace{a\textcircledast a\textcircledast\cdots\textcircledast a}^{nk}\textcircledast\overbrace{a^{p - 2,\textcircledast}\textcircledast a^{p - 2,\textcircledast}\textcircledast\cdots\textcircledast a^{p - 2,\textcircledast}}^{nk}$
$=x\textcircledast\overbrace{a^{p - 1,\textcircledast}\textcircledast a^{p - 1,\textcircledast}\textcircledast\cdots\textcircledast a^{p - 1,\textcircledast}}^{nk}$
第3步:由结论$a^{p - 1,\textcircledast}=1$得到$y_{2}\textcircledast y_{1}^{n(p - 2),\textcircledast}$的结果
由
(2)的证明知$a^{p - 1,\textcircledast}=1$,所以$y_{2}\textcircledast y_{1}^{n(p - 2),\textcircledast}=x$. (17分)