二次剩余课件

第三章二次剩余第三章二次剩余本章内容一、二次剩余的概念二、模为奇素数的平方剩余与平方非剩余三、勒让德符号四、雅可比符号五、小结重点：二次同余方程有解的判断与求解本章内容一、二次剩余的概念§3.1二次剩余的概念二次同余式的一般形式是其中m是正整数，。上式等价于同余式

定义1设m是正整数，若同余式有解，则a叫做模m的平方剩余(或二次剩余)，记为QR；否则a叫做模m的平方非剩余(或二次非剩余)，记为NR。§3.1二次剩余的概念二次同余式的一般形式是其中m是正例1分别求出模11，12的二次剩余和二次非剩余。解：模11的二次剩余是：1，3，4，5，9；二次非剩余是：2，6，7，8，10。模12的二次剩余是：1；二次非剩余是：5，7，11。例1分别求出模11，12的二次剩余和二次非剩余。解：模例2求满足同余式的所有的点。解：模7的二次剩余是：1，2，4；二次非剩余是：3，5，6。对，分别求出对应的的值为例2求满足同余式无解无解无解无解§3.2模为奇素数的平方剩余

与平方非剩余§3.2模为奇素数的平方剩余

与平方非剩余二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件可以验证：∴模11的平方剩余为1，-2，3，4，5；平方非剩余为-1，2，-3，-4，-5.可以验证：∴模11的平方剩余为1，-2，3，4，5；平方非模11的平方剩余为1，-2，3，4，5.模11的平方剩余为1，-2，3，4，5.例1

利用定理判断例1利用定理判断补充模重复平方计算法补充模重复平方计算法补充模重复平方计算法补充模重复平方计算法二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件符号表示如下：QR×QR=QRQR×NR=NRNR×NR=QR若用数字代替符号QR与NR，易见：QR如同+1NR如同-1符号表示如下：

定理2设p是奇素数，则模p的简化剩余系中平方剩余与平方非剩余的个数各为，且个平方剩余与序列中的一个数同余，且仅与一个数同余。模7的平方剩余为1，2，-3；平方非剩余为-1，-2，3.定理2设p是奇素数，则模p的简化剩余系中§3.3

勒让德符号利用欧拉判别条件虽然可以判定x2

a(modp)

的解的存在性，但对较大的素数模，实际运用很困难。通过引入勒让德符号，本节给出了较方便的判别方法。目的：快速判断整数a是否为素数p的平方剩余。§3.3勒让德符号利用欧拉判别条件虽然可以判定x2

定义设p是素数,定义勒让德Legendre符号如下：如,1与4是模5的平方剩余，2与3是模5的平方非剩余，定义设p是素数,定义勒让德Legendre符由此定义，欧拉判别法则可以表示成如下形式：定理2设p是奇素数，则对任意整数a，有定理1由此定义，欧拉判别法则可以表示成如下形式：定理2设p二次剩余课件

Legendre符号基本性质Legendre符号基本性质二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件由引理的证明由引理的证明2的倍数2的倍数二次剩余课件二次剩余课件二次剩余课件二次剩余课件证明：由定理3有二次互反律的证明：证明：二次互反律的证明：二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件例

计算如下勒让德符号的值。(1)

(2)

(3)例计算如下勒让德符号的值。(1)(2)(3)m是否为素数q=0q=1q=-1q=2out:01停止否是，计算nmodm=q返回为奇数；为偶数。m是否为素数q=0q=1q=-1q=2out:01停止否是，二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件二次剩余课件对于奇素数p，利用计算Legendre符号可以判定方程x2

a(modp)(1)是否有解。对于一般的正整数m，

如何判定方程是否有解呢？x2

a(modm)(2)

四、雅可比符号对于奇素数p，利用计算Legendre符号可以判定方程x2对于一般的正整数m，如果它的标准分解式是那么判定方程x2

a(modm)(2)是否有解，可归结为对形如方程x2

a(modp)(1)的可解性判定。

因此，在理论上，利用Legendre符号可以判定方程(2)是否有解。

但是，写出正整数的标准分解式常会遇到实际困难，所以利用Legendre符号判定方程(2)的可解性并不容易实现。对于一般的正整数m，如果它的标准分解式是那么判定方程例如，取m=45=3

3

5，则例如，取m=45=335，则

定义设是奇素数的乘积。对任意整数，定义雅可比(Jacobi)符号为（1

i

k）是Legendre符号。

例如，取m=45=3

3

5，则当m为奇素数时，则上式为勒让德符号。定义设

注意：(1)当m是奇素数时，Jacobi符号就是Legendre符号。前者是后者的推广。(2)雅可比符号为1时，不能判断a是否为模m的平方剩余。例如

因为，而同余式组的每个同余式都无解，所以3是模119的平方非剩余。注意：(1)当m是奇素数时，Jacobi符号就是Lege

如果，则；设m是奇数，则雅可比符号有以下性质：

，如果，则；(3)(2)；(1)，(4)(5)设m,n都是奇数，则。如果，则二次剩余课件定理1

设m=p1p2

pk是奇数，其中p1,p2,pk是素数，则下面的结论成立：定理1设m=p1p2pk是奇数，其中p1,p2定理2

设m，n是大于1的奇整数，则

利用以上定理，我们可以很容易地计算Jacobi符号，特别是Legendre符号的数值。但是，必须注意，如同在定义的注2中指出的，在判断方程(2)的可解性时，Legendre符号和Jacobi的作用是不一样的。

方程(2)有解。对于一般的正奇数m来说，=1并不能保证定理2设m，n是大于1的奇整数，则利用以上例判断同余式是否有解？解：不用考虑563是否为素数，直接计算雅可比符号:所以同余式无解。例判断同余式是否有解？解：不用考虑563是否为素数，直接当n是合数的时候，若（a/n）=1，则a不一定是模n的二次剩余。定义则有。集合中的数称为模n的伪二次剩余。124581011131617192014164116161416411-11-1-11-111-11-1111-11-11-11-1-1-11-111-1-1-1-111-11例：a当n是合数的时候，若（a/n）=1，则a不一例

设a与b是正奇数，求的关系。例设a与b是正奇数，求结论：猜想二次剩余问题的难度与因子分解难度相当。定理3.12若n=pq，且n的素因子p和q已知，则整数a为模n的二次剩余，当且仅当结论：猜想二次剩余问题的难度与因子分解难度相当。五、小结1、m是正整数a是m的二次剩余。2、欧拉判别条件p是奇素数五、小结1、m是正整数a是m的二次剩余。2、欧拉判别条件p是3、勒让德符号的定义设p是素数，定义如下：4、雅可比符号定义对任意奇数m，定义