二次剩余理论的数学基础

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

定义

对于奇素数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 4end{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}2frac{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^2equiv d mod p一定有解。