
解 (1):
- 暴力求解
根据定义,$a^{p-1,\otimes}$ 为 $a^{p-1}$ 除以 $p$ 的余数。带入数值可得
$$
a^{p-1, \otimes} = a^{p-1} \mod p = 2^{10} \mod 11 = 1024 \mod 11 = 1
$$
- 同余性质
因为 $a \in X={1,2,\dots,p-1}$ 且 $p$ 为素数,所以 $1, a, a^{2}, \dots, a^{p-2}$ 都无法被 $p$ 整除,他们的余数一定属于集合 $X$。由于数列 $1, a, a^{2,\otimes}, \dots, a^{p-2,\otimes}$ 的项数与集合 $X$ 元素个数相同,且题目给出 $1, a, a^{2,\otimes}, \dots, a^{p-2,\otimes}$ 两两不同,说明 ${1, a, a^{2,\otimes}, \dots, a^{p-2,\otimes}}$ 与 $X$ 可以建立一一映射关系,且 $a \neq 1$。
根据和的余数与余数的和同余,可得
$$
1 + a + a^2 + \dots + a^{p-2} \equiv 1+2+\dots+(p-1) \mod p
$$
左边是等比数列,根据等比数列求和公式可得 $\frac{a^{p-1}-1}{a-1}$;右边是等差数列,根据等差数列求和公式得 $\frac{p(p-1)}{2}$。很明显 $\frac{p(p-1)}{2}$ 可以被 $p$ 整除,所以 $\frac{a^{p-1}-1}{a-1}$ 也应该被 $p$ 整除。由此可得 $a^{p-1} - 1 \equiv 0 \mod p$,所以 $a^{p-1} \equiv 1 \mod p$。这正是费马小定理。
- 费马小定理
由费马小定理可知,如果 $p$ 为素数,则对于任意 $a \in \mathbb{N}, a^{p-1} \equiv 1 \mod p$ ,所以 $a^{p-1, \otimes} = 1$
解 (2):
设 $\log(p)_a b = n_1, \log(p)_a c = n_2$,则根据离散对数的定义,可得 $a^{n_1, \otimes} = b, a^{n_2, \otimes} = c$。根据 $u^{m,\otimes}$ 的定义,可得进一步改写为_商_乘_除数_加_余数_的形式为:
$$
\begin{align*}
a^{n_1} = k_1p+b \\
a^{n_2} = k_2p+c
\end{align*}
$$
上面两式相乘得
$$
\begin{align*}
a^{n_1+n_2} &= (k_1p+b)(k_2p+c)\\
&= k_1k_2p^2+(k_1c+k_2b)p+bc
\end{align*}
$$
根据 $\oplus$ 的定义,$n_1 \oplus n_2$ 是 $n_1+n_2$ 除以 $p-1$ 的余数,所以 $n_1+n_2 = k(p-1)+(n_1 \oplus n_2)$,则
$$
\begin{align*}
a^{n_1+n_2} &= a^{k(p-1)+(n1 \oplus n_2)} \\
&= (a^{p-1})^k \cdot a^{n_1 \oplus n_2}
\end{align*}
$$
由此我们可得
$$
k_1k_2p^2+(k_1c+k_2b)p+bc = (a^{p-1})^k \cdot a^{n_1 \oplus n_2}
$$
两边同时模 $p$ 取离散对数。
很明显,等式左边除以 $p$ 的余数为 $bc$ 除以 $p$ 的余数,即 $b \otimes c$。根据离散对数的定义其离散对数为 $\log(p)a(b \otimes c)$;
等式右边根据指数的余数与余数的指数同余,可得 $(a^{p-1})^k \equiv (a^{p-1} \mod p)^k \mod p$。根据费马小定理 $a^{p-1} \equiv 1 \mod p$,所以 $(a^{p-1})^k$ 除以 $p$ 的余数为 $1$。根据积的余数与余数的积同余,因此 $(a^{p-1})^k \cdot a^{n_1 \oplus n_2}$ 除以 $p$ 的余数就是 $a^{n_1 \oplus n_2}$ 除以 $p$ 的余数,根据离散对数的定义其离散对数就是 $n_1 \oplus n_2$
因此 $\log(p)_a(b \otimes c) = n_1 \oplus n_2$,即 $\log(p)_a(b \otimes c) = \log(p)_a b \oplus \log(p)_a c$ 。
$\blacksquare$
解 (3):
对 $y_2 \otimes y_1^{n(p-2),\otimes}$ 取以 $b$ 为底的离散对数得:$\log(p)_b y_2 \otimes y_1^{n(p-2),\otimes}$。根据第二问的结论可得
$$
\begin{align*}
\log(p)_b y_2 \otimes y_1^{n(p-2),\otimes}&=\log(p)_b y_2 \oplus \log(p)_b y_1^{n(p-2),\otimes} &(\text{根据第二问的结论})\\
&=\log(p)_b x \otimes b^{k, \otimes} \oplus \log(p)_b (a^{k,\otimes})^{n(p-2),\otimes} &(\text{代入}y_1, y_2)\\
&= \log(p)_b x \oplus \underbrace{\log(p)_b b^{k, \otimes}}_{n_1} \oplus \underbrace{\log(p)_b (a^{k,\otimes})^{n(p-2),\otimes}}_{n_2} &(\text{根据第二问的结论})
\end{align*}
$$
设 $\log(p)_b b^{k, \otimes} = n_1$,设 $\log(p)_b (a^{k,\otimes}) ^ {n(p-2),\otimes}=n_2$,则
$$
\begin{align*}
b^{n_1} &= l_1p+b^{k,\otimes} \\
b^{n_2} &= l_2p+(a^{k,\otimes}) ^ {n(p-2),\otimes}
\end{align*}
$$
根据指数的余数与余数的指数同余,所以 $b^{n_2} = l_2p+(a^{k,\otimes}) ^ {n(p-2),\otimes}=l_2p+(a^{n,\otimes}) ^ {k(p-2),\otimes}$。
因为 $n=\log(p)_a b$,根据定义,$a^{n,\otimes} = b$,所以上面公式可以进一步简化为 $b^{n_2} = l_2p+b^{k(p-2),\otimes}$。
将 $b^{n_1}$ 与 $b^{n_2}$ 相乘得:
$$
\begin{align*}
b^{n_1+n_2} &= (l_1p+b^{k,\otimes})(l_2p+b ^ {k(p-2),\otimes}) \\
&= l_1l_2p^2+(l_1b ^ {k(p-2),\otimes}+l_2b^{k,\otimes})p+b ^ {k,\otimes}\cdot b^{k(p-2),\otimes} \\
&= l_1l_2p^2+(l_1b ^ {k(p-2),\otimes}+l_2b^{k,\otimes})p+b ^ {k(p-1),\otimes} &(\text{积的余数与余数的积同余})
\end{align*}
$$
上面式子两边同时模 $p$,很明显左边式子根据定义可以写成 $b^{n_1+n_2, \otimes}$;右边式子前面两项可以被 $p$ 整除,余数就是 $b^{k(p-1),\otimes}$,由此可得
$$
b^{n_1+n_2, \otimes} = b^{k(p-1), \otimes}
$$
因此
$$
n_1+n_2 = k(p-1)
$$
这意味着 $n_1+n_2$ 可以被 $(p-1)$ 整除,所以根据 $\oplus$ 的定义,$n_1 \oplus n_2 = 0$。将其代入回最初的等式,得
$$
\log(p)_b y_2 \otimes y_1^{n(p-2),\otimes} = \log(p)_b x \oplus 0 = \log(p)_b x
$$
所以 $x = y_2 \otimes y_1^{n(p-2),\otimes}$。
$\blacksquare$