二次剩余理论在密码学中占有重要的地位,很多密码学的加密方案都是基于二次剩余的难解问题。高斯称它为“算术中的宝石”,可见其重要性。这里列举关于二次剩余的常见定理,方便日后查阅。
对于奇素数p,p和d互素,如果x^2 \equiv d\ mod\ p,那么称d是模p的二次剩余,否则称称d是模p的二次非剩余。记模p的二次剩余的全体为QR_p,模p的二次非剩余的全体为QNR_p。
模p的既约剩余系中,二次剩余与二次非剩余各占一半:|QR_p|=|QNR_p|=\frac{p-1}{2}
设素数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
若p \equiv 1\ mod\ 4,则-1是模p的二次剩余;若p \equiv 3\ mod\ 4,则-1是模p的二次非剩余。(由Euler判别法易证得)
对于奇素数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符号。
定义对于奇素数p,令:
称d/p为模p的Legendre符号。
性质
设p,q均为奇素数,p \neq q,那么(\frac{p}{q})(\frac{q}{p})=(-1)^{\frac{p-1}2\frac{q-1}2}
定义设奇数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符号。
性质
说明
Jacobi符号也满足二次互反定律,特别的,Legendre符号也可以当作Jacobi符号来计算,但是与Legendre符号不同,Jacobi符号(\frac{d}{P})=1并不代表二次同余方程x^2\equiv d\ mod\ p一定有解。