二次剩余的数论基础
二次剩余的定义
QR_n \coloneqq {x \in Z_n^* \ | \ \exists y \in Z_n^*: y^2 \equiv x \ \ mod \ n}给定模n乘法群，如果对于x \in Z_n^*，存在群元素y满足y^2 = x，则x是一个二次剩余，此时y是x的一个根。QR_n是模n二次剩余的集合。
一个元素不是二次剩余就是二次非剩余，集合记作QNR_n。
QR_n乘法群
对于QR_n的元素x_1、x_2有以下性质：
-
x_1 \cdot x_2 \in QR_n两个群元相乘结果仍在群中
-
x_1^{-1} \in QR_n存在逆元
素数模二次剩余Z_p^*
当p>2且为素数时，Z_p^*中每个二次剩余都有两个平方根。因此平方取模的函数具有“二对一”的映射关系，这意味着Z_p*中恰好有一半的元素为二次剩余，也即|QR_p| = \frac{p-1}{2}。
讲义上给出的是
Z_p域，有小于等于2个根。当
x \not\equiv 0, p \ne 2时，有0或2个根。
Jacobi符号
设p>2且为素数，x \in Z_p^*，Jacobi符号定义为：
\Bigl(\frac{x}{p}\Bigr) \coloneqq \begin{cases}
1 &\text{if } x \in QR_p\\
-1 &\text{else}
\end{cases}实际上还有一个符号称为Legendre符号，要求模数必须为奇素数。而Jacobi符号的模数可以是任何正整数。所以Jacobi符号是Legendre符号的推广，当模数为奇素数时，Jacobi符号等于Legendre符号。
欧拉准则 Euler Criterion（模p二次剩余的判断）
\Bigl(\frac{x}{p}\Bigr) \equiv x^{\frac{p-1}{2}} mod p欧拉准则用于判断x是否是素数p的二次剩余。
