二次剩余
若同余式
$$
x^2 \equiv a \quad (mod \; m), \qquad (a, m) = 1
$$
有解，则 $a$ 叫做模 $m$ 的平方/二次剩余，否则称为平方/二次非剩余
模为奇素数的平方剩余
欧拉判别条件
$a$ 是模 $p$ 的平方剩余的充要条件是
$$
a^{(p-1)/2} \equiv 1 \quad (mod \; p)
$$
$a$ 是模 $p$ 的平方非剩余的充要条件是
$$
a^{(p-1)/2} \equiv -1 \quad (mod \; p)
$$
并且当 $a$ 是模 $p$ 的平方非剩余时，恰有两解
例子：判断 $137$ 是否是 $227$ 的平方剩余
由 $137^{(227-1)/2} \equiv -1 \quad (mod \; 227)$，知 $137$ 是 $227$ 的平方非剩余
定理二
设 $p$ 是奇素数，则模 $p$ 的简化剩余系中平方剩余与平方非剩余的个数各为 $(p-1)/2$，且 $(p-1)/2$ 个平方非剩余与序列：
$$
1^2, 2^2, \dots , (\cfrac{p-1}{2})^2
$$
中一个数同余，且仅与一个数同余
勒让德符号
$$
(\cfrac{a}{p}) = \begin{cases}
1, \quad & 若 a 是模 p 的平方剩余 \\
-1, & 若 a 是模 p 的平方非剩余 \\
0, & 若 p | a
\end{cases}
$$
高斯引理
$p$ 是奇素数，$a$ 是整数，$(a, p) = 1$，如果整数
$$
a \cdot 1, a \cdot 2, \dots, a \cdot \frac{p-1}{2}
$$
中模 $p$ 的最小正剩余中大于 $\frac{p}{2}$ 的个数是 $m$ ，则
$$
(\cfrac{a}{p}) = (-1)^m
$$
性质
$(\cfrac{a}{p}) \equiv a^{(p-1) / 2} \quad (mod \; p)$
$(\cfrac{a}{p}) = (\cfrac{a+kp}{p})$
$(\cfrac{a}{p})(\cfrac{b}{p}) = (\cfrac{ab}{p})$
若$(a, p) = 1$，则 $(\cfrac{a^2}{p}) = 1$
$(\cfrac{2}{p}) = (-1)^{\frac{p^2-1}{8}}$
若 $(a, 2p) = 1$， 则 $(\cfrac{a}{p}) = (-1)^{T(a,p)}$
$$
T(a, p) = \sum_{k=1}^{(p-1)/2} [\cfrac{ak}{p}]
$$
二次互反律
$p, q$ 是互素的奇素数，则
$$
(\cfrac{p}{q}) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}} (\cfrac{q}{p})
$$
注：二次互反律成立的条件必须是奇素数
例子：判断同余式 $x^2 \equiv 137 \quad (mod \; 227)$ 是否有解
$$
\begin{align}
(\cfrac{137}{227}) = & (-1)^{(\frac{137-1}{2}) \times (\frac{227-1}{2})} \times (\cfrac{90}{137}) \\
= & (\cfrac{2}{137}) \times (\cfrac{5}{137}) \times (\cfrac{3^2}{137}) \\
= & (-1)^{(137^2-1)/8} \times (-1)^{2 \times 68} \times (\cfrac{2}{5}) \\
= & 1 \times (-1)^{(5^2-1)/8} \\
= & -1
\end{align}
$$
雅可比符号
雅可比符号同勒让德符号的书写一样，且只要求 $m$ 是奇数，$a$ 可以为任意整数
$$
\frac{a}{m}
$$
但是要注意的是，雅可比符号只能用来判断是否是二次非剩余，而不能判断是否是二次剩余
雅可比符号具有和勒让德符号一样的性质，包括二次互反律
注：二次互反律只在 $a,m$ 均是奇数的时候成立
例子：判断同余式
$$
x^2 \equiv 286 \quad (mod \; 563)
$$
是否有解
$$
\begin{align}
(\cfrac{286}{563}) = & (\cfrac{2}{563}) \times (\cfrac{143}{563}) \\
= & (-1)^{(563^2-1)/8} \times (-1)^{\frac{143-1}{2} \times \frac{563-1}{2}} \times (\cfrac{-9}{143}) \\
= & (\cfrac{-1}{143}) \\
= & -1
\end{align}
$$
故无解
模 $p$ 平方根
设 $p$ 是形如 $4k+3$ 型的素数，则同余式
$$
x^2 \equiv a \quad (mod \; p)
$$
的解为
$$
x \equiv \pm a^{\frac{p+1}{4}} \quad (mop \; p)
$$
更复杂的情况暂时略
Rabin密码体制
随机选择两个形如 $4k+3$ 的大素数 $p, q$，计算 $n = p \times q$，以 $n$ 作为公开密钥，$p, q$ 作为私有密钥，则密文 $c \equiv m^2 \quad (mod \; n)$，解密即为求方程组
$$
\begin{cases}
x^2 \equiv c \quad (mod \; q) \\
x^2 \equiv c \quad (mod \; p)
\end{cases}
$$
由中国剩余定理可知解共有 $4$ 个，于是需要在明文 $m$ 中添加某些信息来确保解密的结果唯一
例子：取 $p=7, q = 11$
- 若明文 $m = 16$，求加密后的密文 $c$
- 若密文 $c = 23$，求对应的 $4$ 个明文
一：
$$
c = 16 ^ 2 \equiv 25 \quad (mod \; 77) \\
$$
二：
$$
\begin{cases}
x^2 \equiv 23 \equiv 2 \quad (mod \; 7) \\
x^2 \equiv 23 \equiv 1 \quad (mod \; 11)
\end{cases}
$$
故解为
$$
\begin{cases}
x \equiv \pm 2^{(7+1)/4} \quad (mod \; 7) \\
x \equiv \pm 1^{(11+1)/4} \quad (mod \; 11)
\end{cases}
$$
再有中国剩余定理可知四个解为
$$
x \equiv \pm 4 \times 22 + \pm 1 \times 56 \equiv 10、32、45、67
$$
