模97乘法群中离散对数奇偶性的疑问
嘿，同学，这个问题其实和二次剩余（也就是模p下能不能写成某个数的平方）的概念直接相关，咱们一步步拆解来看，绝对不是巧合哦！
首先，先明确$Z_{97}^*$这个乘法群的核心性质：
- 因为97是质数，所以$Z_{97}*$（所有1到96之间与97互质的数，也就是所有非0数模97）是一个**阶为96的循环群**。意思是存在一个“生成元”$k$，每一个数都能写成$kx \mod 97$的形式，其中$x$是0到95之间的整数。
- 在循环群里，一个数是二次剩余（能写成某个数的平方，即存在$m$使得$a = m^2 \mod 97$）的充要条件是：它对应的指数$x$是偶数。原因很简单：如果$a = m^2$，而$m = k^t$，那么$a = (kt)2 = k^{2t}$，指数是$2t$（偶数）；反过来，如果$a = kx$且$x$是偶数，那$x=2t$，$a=(kt)^2$，自然是平方数。反过来，非二次剩余对应的指数必然是奇数。
接下来咱们验证2和5是不是二次剩余，这里用欧拉判别法：对于质数$p$，非0数$a$是二次剩余当且仅当$a^{\frac{p-1}{2}} \equiv 1 \mod p$；如果结果是$-1$，那就是非二次剩余。
验证2是二次剩余
$\frac{p-1}{2} = \frac{97-1}{2} = 48$，咱们一步步计算$2^{48} \mod 97$：
- $2^6 = 64 \mod 97$
- $2^{12} = 64^2 = 4096$，$4096 - 42\times97 = 4096 - 4074 = 22$，所以$2^{12} \equiv 22 \mod 97$
- $2^{24} = 22^2 = 484$，$484 - 5\times97 = 484 - 485 = -1$，所以$2^{24} \equiv -1 \mod 97$
- $2^{48} = (2{24})2 = (-1)^2 = 1 \mod 97$
结果是1，说明2是二次剩余，所以不管用哪个生成元$k$，$k^{x_1}=2$中的$x_1$必然是偶数。
验证5是非二次剩余
同样计算$5^{48} \mod 97$：
- $5^2 = 25 \mod 97$
- $5^4 = 25^2 = 625$，$625 - 6\times97 = 625 - 582 = 43$，所以$5^4 \equiv 43 \mod 97$
- $5^8 = 43^2 = 1849$，$1849 - 19\times97 = 1849 - 1843 = 6$，所以$5^8 \equiv 6 \mod 97$
- $5^{16} = 6^2 = 36 \mod 97$
- $5^{24} = 5^{16} \times 5^8 = 36\times6 = 216$，$216 - 2\times97 = 216 - 194 = 22$，所以$5^{24} \equiv 22 \mod 97$
- $5^{48} = (5{24})2 = 22^2 = 484 \equiv -1 \mod 97$
结果是-1，说明5是非二次剩余，所以对应的$x_2$必然是奇数。
为什么换生成元奇偶性不变？
假设你换另一个生成元$k'$，那$k'$一定可以写成$kt$的形式，其中$t$和96互质（只有这样$k'$才能生成整个群）。96是$25 \times 3$，所以$t$不能是偶数（否则$t$和96有公约数2，$k'$的阶就不是96了），也就是说$t$是奇数。
对于2来说：$2 = k^{x_1} = (k')^{y_1} = (kt){y_1} = k^{t y_1}$，所以$x_1 \equiv t y_1 \mod 96$。因为$t$是奇数，奇数乘$y_1$的奇偶性和$y_1$本身一致，$x_1$是偶数，所以$y_1$也必须是偶数。
同理，对于5来说：$5 = k^{x_2} = (k')^{y_2} = k^{t y_2}$，$x_2 \equiv t y_2 \mod 96$，$x_2$是奇数，$t$是奇数，所以$y_2$也必须是奇数。
这就说明不管选哪个生成元，指数的奇偶性都不会变，完全是由数本身是不是二次剩余决定的，绝非巧合！
备注：内容来源于stack exchange，提问作者user1260466
