Mythsman


乐极生悲,苦尽甘来。


二次剩余理论的数学基础

二次剩余理论在密码学中占有重要的地位,很多密码学的加密方案都是基于二次剩余的难解问题。高斯称它为“算术中的宝石”,可见其重要性。这里列举关于二次剩余的常见定理,方便日后查阅。

定义

对于奇素数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$符号。

性质

  1. $(\frac{d}{p})=d^{(p-1)/2}\ mod\ p$
  2. $(\frac{d}{p})=(\frac{d+p}{p})$
  3. $(\frac{dc}{p})=(\frac{d}{p})(\frac{c}{p})$
  4. $(\frac{-1}{p})=\left\{\begin{aligned}1,&& p \equiv 1\ mod\ 4\\ -1&& p \equiv 3\ mod\ 4\end{aligned}\right.$
  5. $\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$符号。

性质

  1. $(\frac{1}{P})=1$
  2. $(d,P)\neq 1,(\frac{d}{P})=0$
  3. $(d,P)= 1,(\frac{d}{P})=\pm 1$
  4. $(\frac{d}{P})=(\frac{d+P}{P})$
  5. $(\frac{dc}{P})=(\frac{d}{P})(\frac{c}{P})$
  6. $\frac{-1}{P}=(-1)^{(P-1)/2}$
  7. $\frac{2}{P}=(-1)^{(P^2-1)/8}$

说明
$Jacobi$符号也满足二次互反定律,特别的,$Legendre$符号也可以当作$Jacobi$符号来计算,但是与$Legendre$符号不同,$Jacobi$符号$(\frac{d}{P})=1$并不代表二次同余方程$x^2\equiv d\ mod\ p$一定有解。