第三章 二次剩余.

Presentation on theme: "第三章 二次剩余."— Presentation transcript:

1 第三章 二次剩余

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

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

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

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

6 无解 无解

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

8

9

10

11

12

13

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

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

16 例1 利用定理判断

17 补充 模重复平方计算法

18 补充 模重复平方计算法

19

20

21

22

23

24

25

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

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

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

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

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

31

32 Legendre符号基本性质

33

34

35

36

37

38

39

40

41

42

43

44 由引理的证明

45 2的倍数

46

47

48

49

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

51

52

53

54

55

56

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

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

59

60

61

62

63

64

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

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

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

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

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

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

71

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

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

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

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

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

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

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

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

80 六 应用

81

82

83

84

85 作业 3月25日 P 4月8 日 P P (利用二次互反律)