二次剩余理论在密码学中占有重要的地位，很多密码学的加密方案都是基于二次剩余的难解问题。高斯称它为“算术中的宝石”，可见其重要性。这里列举关于二次剩余的常见定理，方便日后查阅。
定义
对于奇素数p，p和d互素，如果$x^2 \equiv d\ mod\ p$，那么称d是模p的二次剩余，否则称称d是模p的二次非剩余。记模p的二次剩余的全体为$QR_p$，模p的二次非剩余的全体为$QNR_p$。
定理(1)
模p的既约剩余系中，二次剩余与二次非剩余各占一半：$|QR_p|=|QNR_p|=\frac{p-1}{2}$
Euler判别法
设素数p为奇素数，p和d互素，那么d为模p的二次剩余的充要条件是：$d^{\frac{p-1}{2}}\equiv 1\ mod\ p$
d为模p的二次剩余的充要条件是：$d^{\frac{p-1}{2}}\equiv -1\ mod\ p$
注意到由欧拉定理，有$(d^{\frac{p-1}{2}}- 1)*(d^{\frac{p-1}{2}}+ 1)\equiv 0 \ mod\ p$
推论(1)
若$p \equiv 1\ mod\ 4$,则-1是模p的二次剩余；
若$p \equiv 3\ mod\ 4$,则-1是模p的二次非剩余。
(由Euler判别法易证得)
推论(2)
对于奇素数p，$(p,d_1)=1$，$(p,d_2)=1$，那么$d_1 d_2$是模p的二次剩余的充要条件是$d_1$和$d_2$均为模p的二次剩余或二次非剩余；$d_1 d_2$是模p的二次非剩余的充要条件是$d_1$和$d_2$一个为模p的二次剩余另一个为模p的二次非剩余。
接下来介绍两个重要的符号：$Legendre$符号和$Jacobi$符号。
Legendre符号
定义
对于奇素数p，令：
$$(\frac{d}{p})=\left\{\begin{aligned}& 0, & p|d\\& 1, & d \in QR_p\\&-1, & d \in QNR_p\end{aligned}\right.$$
称$\frac{d}{p}$为模p的$Legendre$符号。
性质
- $(\frac{d}{p})=d^{(p-1)/2}\ mod\ p$
- $(\frac{d}{p})=(\frac{d+p}{p})$
- $(\frac{dc}{p})=(\frac{d}{p})(\frac{c}{p})$
- $(\frac{-1}{p})=\left\{\begin{aligned}1,&& p \equiv 1\ mod\ 4\\ -1&& p \equiv 3\ mod\ 4\end{aligned}\right.$
- $\frac{2}{p}\equiv(-1)^{(p^2-1)/8}$
Gauss二次互反定律
设p,q均为奇素数，$p \neq q$，那么$(\frac{p}{q})(\frac{q}{p})=(-1)^{\frac{p-1}2\frac{q-1}2}$
Jacobi符号
定义
设奇数p>1，$ P=p_1,p_2,p_3,…,p_n $.
其中$p_i$是素数，我们把
$(\frac{d}{P})=(\frac{d}{p_1})(\frac{d}{p_2})…(\frac{d}{p_n})$
称为$Jacobi$符号，此处$(\frac{d}{p_i})$是$Legendre$符号。
性质
- $(\frac{1}{P})=1$
- $(d,P)\neq 1,(\frac{d}{P})=0$
- $(d,P)= 1,(\frac{d}{P})=\pm 1$
- $(\frac{d}{P})=(\frac{d+P}{P})$
- $(\frac{dc}{P})=(\frac{d}{P})(\frac{c}{P})$
- $\frac{-1}{P}=(-1)^{(P-1)/2}$
- $\frac{2}{P}=(-1)^{(P^2-1)/8}$
说明
$Jacobi$符号也满足二次互反定律，特别的，$Legendre$符号也可以当作$Jacobi$符号来计算，但是与$Legendre$符号不同，$Jacobi$符号$(\frac{d}{P})=1$并不代表二次同余方程$x^2\equiv d\ mod\ p$一定有解。