问题：
离散对数在密码学中有重要的应用。设$p$是素数，集合$X=\{1,2,\cdots,p-1\}$，若$u,v\in{X}$，$m\in\mathbb{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}}$.
解答如下：
第(1)小题最简单，只需注意到$2^{10}=93\times11+1$，可知$2^{10,\otimes}=1$. 后面两道题目，需要一些准备知识：
(i)首先应该注意到$p$不能整除$a$否则$a,a^2,\cdots,a^{p-2}$除以$p$的余数都是0，矛盾。当$p$不整除$a$时，由于$p$是素数，那么$p$和$a$时互素的，即$(p,a)=1$，更进一步有$(p,a^k)=1$。
(ii)我们证明，如果$a^{m,\otimes}=a^{n,\otimes}=r$,这里$m>n$，那么必有$a^{m-n,\otimes}=1$，设$a^m=pM+r$, $a^n=pN+r$, 那么
\[a^m-a^n=a^n(a^{m-n}-1)=p(M-N)\]
可是$a^n$与$p$互素，所以必有$p$整除$(a^{m-n}-1)$，这就说明$a^{m-n}-1=pK$,$a^{m-n}=pK+1$，也就是$a^{m-n,\otimes}=1$.
有了这个结论，可以知道必有$a^{p-1,\otimes}=1$，否则，由于一个整数除以$p$的余数只能是$0,1,\cdots,p-1$中的一个，那么按照假设，$a^{p-1}$的余数必然是和$a^{k}$相同，这里$k=1,2,\cdots,p-2$，于是$a^{p-1-k,\otimes}=1$，而这个$p-1-k$是在$1$到$p-2$之内的，与假设$1,a,\cdots,a^{p-2,\otimes}$两两不同矛盾。
(iii)$a^{(p-1)k,\otimes}=1$, $a^{p-1}=pX+1$,$a^{(p-1)k}=(pX+1)^k$，二项式展开，
\[\begin{aligned}(pX+1)^k&={n \choose 0}(pX)^n+{n\choose 1}(pX)^{n-1}+\cdots+{n \choose n-1}(pX)^{1}+{n \choose n}\\ &=pM+1 \end{aligned}\]
接下来可以证明第(2)和(3)小题：
(2)设$m=\log(p)_{a}{b}$,$n=\log{(p)}_{a}{c}$,也就是说$a^m=pM+b$, $a^n=pN+c$，于是
\[a^{m+n}=a^ma^n=p(pMN+Mc+Nb)+bc\]
记$r=b\otimes{c}$，$s=m\oplus{n}$，也就是$bc=pX+r$, $m+n=(p-1)Y+s$，于是
\[\begin{aligned}a^{(p-1)Y+s}&=p(pMN+Mc+Nb+X)+r=(a^{p-1})^Ya^s\\&=(pZ+1)a^{s}=pZa^s+a^s\end{aligned}\]
由此就可以得到$a^s=p(pMN+Mc+Nb+X-Za^s)+r$，也就是$\log(p)_{a}{r}=s$，这就是所要证明的。
(3)首先从$n=\log(p)_{a}{b}$，存在$A\in\mathbb{Z}$，使得$a^n=pA+b$，从$y_1=a^{k,\otimes}$，存在$Y_1\in\mathbb{Z}$，使得$y_1=a^k-pY_1$，为了方便记$z=b^{k,\otimes}$，于是存在$Z\in\mathbb{Z}$，使得$z=b^k-pZ$，而从$y_2=x\otimes{z}$，可知存在$Y_2\in\mathbb{Z}$使得$xz=pY_2+y_2$，有了这些，就可以直接计算
\[ \begin{aligned} y_2y_1^{n(p-2)}&=(xz-pY_2)(a^k-pY_1)^{n(p-2)} = (x(b^k-pZ)-pY_2)(a^{kn(p-2)}+pM)\\ &=(xb^k-pxZ-pY_2)(a^{kn(p-2)}+pM) = xb^ka^{kn(p-2)}+pM’\\ &=x(a^n-pA)^ka^{kn(p-2)}+pM’=x(a^{kn}+pN)a^{kn(p-2)}+pM’\\ &=xa^{kn}a^{kn(p-2)}+pM”=xa^{kn(p-1)}+pM”=x(pN’+1)+pM”\\ &=x+pM”’ \end{aligned} \]
这就完成了证明：$x=\log(p)_{a}{y_2\otimes{y_1^{n(p-2),\otimes}}}$.上面$(a^k-pY_1)^{n(p-2)} = (a^{kn(p-2)}+pM)$这一步再次使用了二项式定理。
这道题目的背景知识显然是初等数论及其在密码学中的应用。余数相同在初等数论中可以用同余式表示，也就是如果$a$和$b$除以$p$的余数相同，就有这样的等式：$a\equiv{b}(\bmod{p})$。问题中的$a$称为模$p$的原根，而对于整数$b$，$\log(p)_{a}{b}$则称作$b$对于原根$a$模$p$的指数，数论中常用的记号是$\operatorname{ind}_{a}(b)$，甚至直接把$a$省略，记作$\operatorname{ind}(b)$。
第(1)小题的答案为1也不是巧合，实际上使用初等数论中的欧拉定理可以直接写出答案，欧拉定理是这样的：设$m$为正整数，如果$a$和$m$互素，那么必有$a^{\varphi(m)}\equiv1(\bmod{m})$，首先注意这里没有要求$m$为素数，其次这里对符号$\varphi(m)$是整数$m$的欧拉函数，表示的是不超过$m$的与$m$互素正整数的个数，当$m$为素数的时候，恰有$\varphi(m)=m-1$。
第(2)小题使用同余式相关的结论，实际上非常简单，同余式中，当$p$为素数的时候，实际上是可以作加减乘除运算的，只是这里的四则运算和常规的四则运算稍微有点差异。
\[a^{\operatorname{ind}(m)+\operatorname{ind}(n)}=a^{\operatorname{ind}(m)}\cdot{}a^{\operatorname{ind}(n)}\equiv{mn}=a^{\operatorname{ind}(mn)}(\bmod{p})\]
于是必有$\operatorname{ind}(m)+\operatorname{ind}(n)\equiv\operatorname{ind}(mn)(\bmod{\varphi(p)})$
第(3)小题则是公钥加密中ElGamal方案。计算机在处理文本的时候，实际上就是在处理整数序列，所以我们只需要对整数进行考虑即可。而加密的过程就是对于整数$x$，通过加密过程变成$y$，解密的过程就是能够从$y$重新得到$x$。第(3)小题，我们对$x$加密的结果是$(y_1,y_2)$，然后从$(y_1,y_2)$可以重新得到$x$。这里面需要保密的是其中的$n$，而素数$p$，整数$a,b$都可以公开，它所依赖的原则是：对于给定的原根$a$，由$n$计算$b$是比较容易的，但是对于比较大的素数$p$（例如大于130位），由$b$计算$n$（离散对数）则是比较困难的。值得注意的是，我们解密的时候并不依赖于$k$，所以加密的时候可以变换$k$的选择。