二次剩余理论的数学基础

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

定义

对于奇素数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\ pd为模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，令：

称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=p1,p2,p3,...,pn.

其中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一定有解。