二次剩余的数论基础
二次剩余的定义
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的二次剩余。