第三章 二次剩余

本章内容 一、二次剩余的概念 二、模为奇素数的平方剩余与平方非剩余 三、勒让德符号 四、雅可比符号 五、小结 重点：二次同余方程有解的判断与求解

§3.1 二次剩余的概念 二次同余式的一般形式是 其中m是正整数， 。 上式等价于同余式 定义1 设m是正整数，若同余式 §3.1 二次剩余的概念 二次同余式的一般形式是 其中m是正整数， 。 上式等价于同余式 定义1 设m是正整数，若同余式 有解，则a叫做模m的平方剩余(或二次剩余)，记为QR；否则a叫做模m的平方非剩余(或二次非剩余)，记为NR 。

例1 分别求出模11，12的二次剩余和二次非剩余。 解： 模11的二次剩余是：1，3，4，5，9； 二次非剩余是：2，6，7，8，10。 模12的二次剩余是：1； 二次非剩余是：5，7，11。

例2 求满足同余式 的所有的点。 解： 模7的二次剩余是：1，2，4；二次非剩余是：3，5，6。 对 ，分别求出 对应的的值为

无解 无解

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

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

模11的平方剩余为1，-2，3，4，5.

例1 利用定理判断

补充 模重复平方计算法

补充 模重复平方计算法

符号表示如下： QR ×QR=QR QR ×NR=NR NR ×NR=QR 若用数字代替符号QR与NR，易见： QR如同+1 NR如同-1

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

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

如, 1与4是模5的平方剩余，2与3是模5的平方非剩余， 定义 设p是素数, 定义勒让德Legendre符号如下： 如, 1与4是模5的平方剩余，2与3是模5的平方非剩余，

定理1 由此定义，欧拉判别法则可以表示成如下形式： 定理2 设p是奇素数，则对任意整数a，有

Legendre符号基本性质

由引理的证明

2的倍数

二次互反律的证明： 证明： 由 定理3 有

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

返回 m是否为素数 是，计算nmodm=q 停止 否 q=0 q=1 q=2 q=-1 out:0 1 为奇数； 为偶数。

四、雅可比符号 对于奇素数p，利用计算Legendre符号可以判定方程 x2  a (mod p) (1) 是否有解。 x2  a (mod m) (2) 是否有解呢？

对于一般的正整数m，如果它的标准分解式是 那么判定方程 x2  a (mod m) (2)是否有解， 可归结为对形如方程x2  a (mod p) (1) 的可解性判定。 因此，在理论上，利用Legendre符号可以判定 方程(2)是否有解。 但是，写出正整数的标准分解式常会遇到实际困难， 所以利用Legendre符号判定方程(2)的可解性并不容 易实现。

例如，取m = 45 = 335，则

（1 i  k）是Legendre符号。 当m为奇素数时，则上式为勒让德符号。 例如，取m = 45 = 335，则 定义 设 是奇素数 的乘积。对任意整数 ，定义雅可比(Jacobi)符号为 （1 i  k）是Legendre符号。 当m为奇素数时，则上式为勒让德符号。 例如，取m = 45 = 335，则

注意：(1) 当m是奇素数时，Jacobi符号就是Legendre符号。 前者是后者的推广。 (2) 雅可比符号为1时，不能判断a是否为模m的平方剩余。例如 因为 ，而同余式组 的每个同余式都无解，所以3是模119的平方非剩余。

设m是奇数，则雅可比符号有以下性质： ， (1) (2) ； ，如果 ，则 ； (3) 如果 ，则 ； (4) (5) 设m,n都是奇数，则 。

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

定理2 设m，n是大于1的奇整数，则 利用以上定理，我们可以很容易地计算Jacobi符 号，特别是Legendre符号的数值。但是，必须注意， 如同在定义的注2中指出的，在判断方程(2)的可解 性时，Legendre符号和Jacobi的作用是不一样的。 对于一般的正奇数m来说， = 1并不能保证 方程(2)有解。

例 判断同余式是否有解？ 解：不用考虑563是否为素数，直接计算雅可比符号: 所以同余式无解。

当n是合数的时候，若（a/n）=1，则a不一定是模n的二次剩余。定义 例： a 1 2 4 5 8 10 11 13 16 17 19 20 -1

例 设a与b是正奇数，求 的关系。

定理3.12 若n=pq，且n的素因子p和q已知，则整数a为模n的二次剩余，当且仅当 结论：猜想二次剩余问题的难度与因子分解难度相当。

五、小结 1、m是正整数 a是m的二次剩余。 2、欧拉判别条件 p是奇素数

3、勒让德符号的定义 设p是素数，定义如下： 4、雅可比符号定义 对任意奇数m，定义为：

六 应用

作业 3月25日 P45 3.3 3.5 3.9 4月8 日 P45 3.6 3.7 P 34 2.7(利用二次互反律)