27、二次剩余与模平方根计算及模块和向量空间基础

二次剩余与模平方根计算及模块和向量空间基础

1. 二次剩余测试

对于奇数 $n > 1$，定义 $G_n := {α ∈Z^_n : α^{(n - 1)/2} = [J_n(α)]_n}$，其中 $J_n : Z^_n →{±1}$ 是雅可比映射。
-$G_n$ 是 $Z^*_n$ 的子群：需要证明 $G_n$ 满足子群的条件，即封闭性、单位元存在和逆元存在。
-若 $n$ 为素数，则 $G_n = Z^*_n$：根据素数的性质和相关定理可以证明。
-若 $n$ 为合数，则 $G_n ⊊Z^*_n$：合数的情况与素数不同，可通过相关理论推导得出。
-素性测试算法：选择一个随机的非零元素 $α ∈Z_n$，测试 $α$ 是否属于 $G_n$。若 $α$ 不属于 $G_n$，则 $n$ 为合数；若 $α$ 属于 $G_n$，则 $n$ 可能为素数。

不同模数下二次剩余的测试方法