当前位置：文档之家 › 《数论算法》教案4章(二次同余方程与平方剩余)

《数论算法》教案4章(二次同余方程与平方剩余)

  • 格式：doc
  • 大小：2.57 MB
  • 文档页数：49

下载文档原格式

  / 49

合集下载

第4讲二次同余与平方剩余

第4讲二次同余与平方剩余

二次同余式的一般形式ax2＋bx＋c≡0(mod m)由算术基本定理知道m可以分解成一些素数乘积,再由孙子定理知道ax2＋bx＋c≡0(mod m)可以转化为同余式组ax2＋bx＋c≡0(mod pα)因此,本章只讨论模为素数幂pα的同余式设p是素数，我们来研究素数模p的二次同余方程ax2+bx+c≡0 (mod p)。

(1)如果p= 2，则可以直接验证x≡0或1 (mod 2)是否方程(1)的解。

如果(a, p) = p，则方程(1)成为一元一次同余方程。

因此，只需考察p > 2，(a, p) = 1的情形。

此时，因为(4a, p) = 1，所以，方程(1)等价于方程4a2x2+4abx+4ac≡0 (mod p)，即(2ax+b)2≡b2-4ac(mod p)。

这样，研究方程(1)归结为对方程x2≡a(mod m) (2)定义１给定整数m，对于任意的整数a，(a，m) = 1，若方程x2 a(mod m)有解，则称a是模m的二次剩余；否则，称a是模m的二次非剩余.例1验证1是模4的平方剩余,‐1是是模4的非平方剩余 例21,2,4 是模7的平方剩余,‐1,3,5是模7的非平方剩余解因为,12≡1, 22≡4, 32≡2, 42≡2，52≡4，62≡1（mod7），例3 求满足方程E:y2≡x3+x+1(mod 7)的所有点 解x ≡0, y2 ≡1(mod 7) y ≡1,6 (mod 7)x ≡1, y2 ≡3(mod 7) 无解x ≡2, y2 ≡4(mod 7) y ≡2,5 (mod 7)x ≡3, y2 ≡3(mod 7) 无解x ≡4, y2 ≡6(mod 7) 无解x ≡5, y2 ≡5(mod 7) 无解x ≡36, y2 ≡6(mod 7) 无解4.2模为奇素数的平方剩余与非平方剩余 在这节里讨论模为素数的二次同余式定理１(欧拉判别条件) 若(a , p ) = 1，p 是奇素数则 (ⅰ) a 是模p 的二次剩余的充要条件是≡1 (mod p )；(3) (ⅱ) 若a 是模p 的二次剩余，则方程(2)有两个解； (ⅲ) a 是模p 的二次非剩余的充要条件是 ≡-1 (mod p )。

《平方剩余》课件

《平方剩余》课件
《平方剩余》PPT课件
探索《平方剩余》的奥秘：从基础概念到应用的完整介绍。
什么是平方剩余？
学习平方剩余是理解数论中重要概念的关键。了解平方剩余是什么以及其与 数学中其他概念的联系。
平方剩余的相关概念和定义
探索平方剩余的核心概念，包括剩余类，勒让德符号等。了解这些定义对后 续内容的重要性。
二次剩余和二次非剩余
探索平方剩余定理及其在数学竞赛中的应用。
Euler判别定理
深入研究Euler判别定理的原理和证明，并探讨其在平方剩余问题中的应用。
Jacobi符号和Legendre符号
介绍Jacobi符号和Legendre符号的定义和性质，以及在数论中的重要作用。
平方剩余的判别方法
二次探测法
解释如何使用Leabharlann 次探测法判断数 的平方剩余。Hensel定理和Hensel引理
研究Hensel定理和Hensel引理的证明和应用，以及其在平方剩余问题中的重要性。
费马小定理和欧拉定理
解释费马小定理和欧拉定理以及它们与平方剩余的关系和应用。
平方剩余与离散对数问题
深入研究平方剩余与离散对数问题之间的联系和应用。
平方剩余在数学竞赛中的应用
探索平方剩余在数学竞赛中的应用，包括奥林匹克竞赛和其他数学竞赛中的 典型问题。
深入研究平方剩余的分类，了解二次剩余和二次非剩余之间的关系以及其在 数论中的应用。
模意义下的平方剩余
将平方剩余的概念引入模意义中，探讨模意义下平方剩余的特性和运算规律。
平方剩余的性质
欧拉判别准则
解释欧拉判别准则在判断平方剩余的作用和重要性。
二次互反律
介绍二次互反律对平方剩余的影响和应用。
平方剩余定理
2 ElGamal加密算法

数论01二次同余式与平方剩余共32页

数论01二次同余式与平方剩余共32页

21、要知道对好事的称颂过于夸大，也会招来人们的反感轻蔑和嫉妒。——培根 22、业精于勤，荒于嬉；行成于思，毁于随。——韩愈
23、一切节省，归根到底都归结为时间的节省。——马克思 24、意志命运往往背道而驰，决心到最后会全部推倒。——莎士比亚
数论01二次同余式与平方剩余
•
6、黄金时代是在我们的前面，而ห้องสมุดไป่ตู้在 我们的 后面。
•
7、心急吃不了热汤圆。
•
8、你可以很有个性，但某些时候请收 敛。
•
9、只为成功找方法，不为失败找借口 (蹩脚 的工人 总是说 工具不 好)。
•
10、只要下定决心克服恐惧，便几乎 能克服 任何恐 惧。因 为，请 记住， 除了在 脑海中 ，恐惧 无处藏 身。-- 戴尔． 卡耐基 。
25、学习是劳动，是充满思想的劳动。——乌申斯基
谢谢！

二次同余式和平方剩余

二次同余式和平方剩余

又因p为奇素数，所以有(p，2）=1
则 ( p,2x0 ) 1，所以有( p, f , (x0 )) ( p,2x0 ) 1 由上一章的定理知x2 a(mod p) 有解，并由
2、雅可比符号为1时，x2 a(mod m) 不一定
有解。例
(2) (2)(2) 1 ,但 x2 2(mod 9) 无解。
9 33
3、雅可比符号为-1时，则 x2 a(mod m)
一定无解。
因为若
(a) m
=-1，则至少有一个i使得
(
即 x2 a(mod pi ) 无解，则 x2 a(mod
(
2) p
(1)
p2 1 8
1, p 8k 1 1, p 8k 3
证：因为 p 1 (1)1(mod p)
2 2(1)2 p 3 3(1)3(mod p)
r
p 1, 2
p 1,
p p
4k 4k
1 3
r
p
1
(1)
p 1 2
(mod
p)
2
2
把上述
p 2
1
个式子相乘得
2 4 6( p 3)( p 1)
∵ 17≡1(mod 4) ∴ (17) (23) ( 6 ) ( 2 )( 3 ) ( 3 ) (17) ( 2) 1
23 17 17 17 17 17 3 3
∴ x2≡17(mod 23)无解，即原方程无解。
例4：若3是素数p平方剩余，问p是什么形式
的素数？
解：∵ 由反转定律
(
3
定理：在模P的简化系中，平方剩余和平方非
剩余余各为 p 1个
p 1
2
且 余，2而个且平仅方与乘一余数分一别同与余。1,22

二次同余式的解法

二次同余式的解法

二次同余式的解法一、什么是二次同余式二次同余式是指形如ax2+bx+c≡0(mod m)的同余方程，其中a,b,c,m是给定的整数，x是未知数，≡表示模同余。

二、二次同余式的解法解二次同余式的一种常用方法是通过模平方根的性质。

下面介绍二次同余式的两种解法：平方剩余和二次非剩余。

2.1 平方剩余如果存在一个整数x，使得x2≡c(mod m)，则称c是模m的平方剩余。

我们可以通过以下步骤求解二次同余式：1.计算模m的平方剩余集合{02,12,22,…,(m−1)2}。

2.判断c是否在平方剩余集合中。

–如果在集合中，即存在x满足x2≡c(mod m)，则可以得到两个解：x≡±√c(mod m)。

–如果不在集合中，则二次同余式无解。

2.2 二次非剩余如果不存在一个整数x，使得x2≡c(mod m)，则称c是模m的二次非剩余。

解决二次同余式的方法如下：1.计算模m的平方剩余集合{02,12,22,…,(m−1)2}。

2.判断c是否在平方剩余集合中。

–如果在集合中，则二次同余式无解。

–如果不在集合中，可以通过以下步骤求解二次同余式：1.找到一个整数y，使得y2≡c⋅a(mod m)，其中a是模m的一个非平方剩余。

2.利用模m的平方剩余集合求解y的平方根。

3.根据平方根的性质，可以得到两个解：x≡±y(mod m)。

2.3 例子假设我们要解决二次同余式3x2+5x+2≡0(mod11)。

按照上述方法，我们可以进行如下步骤：1.计算模11的平方剩余集合：{02,12,22,…,102}={0,1,4,9,5,3,3,5,9,4,1}。

2.判断2是否在平方剩余集合中，发现不在集合中。

3.找到一个整数y，使得y2≡2⋅a(mod11)，其中a是模11的一个非平方剩余。

可以选择a=3，则62≡2⋅3(mod11)。

4.利用模11的平方剩余集合求解6的平方根，发现6在平方剩余集合中。

5.得到两个解：x≡±6(mod11)。

第四章 二次剩余

第四章 二次剩余
第四章 二次同余式与平方剩余
4.1 二次同余式与平方剩余
二次同余式的一般形式是：
ax2＋bx＋c ≡0 (mod m)
(1)
其中 a ≡ 0 (mod m) ,
设 m 有素因数分解：
m
p1 1
p2 2 …
pk k
定理2.1.11和定理2.1.12(定理3.3.1)，二次同余式
ax2＋bx＋c ≡0 (mod m)
(2) n1＝0 , 计算 a1＝a0≡137, b2≡b12 ≡ 1552 ≡190 (mod 227)
(3) n2＝0, 计算 a2＝a1≡137, b3≡b22 ≡ 190 2 ≡7 (mod 227)运用模重复平方法Fra bibliotek依次计算如下：
(4) n3＝0 , 计算 a 3＝a2≡137, b4≡b32 ≡72 ≡49 (mod 227)
例5 求解同余式：x2 ≡ 46(mod 105) 。
由中国剩余定理解这些同余式组： 令 m1 ＝3, m2 ＝5, m3 ＝7, m ＝ m1 ·m2 ·m3 ＝105 M1 ＝ m2 ·m3 ＝35, M2 ＝ m1 ·m3 ＝21 , M3 ＝ m1 ·m2 ＝15 分别求解同余式 35M1≡1 (mod 3)，21M2≡1 (mod 5) ， 15M2≡1 (mod 7) 得 M1 ≡ 2 (mod 3)，M2 ≡ 1 (mod 5)，M3 ≡ 1 (mod 7)
x ≡1(mod 3) x ≡1(mod 5) x ≡2(mod 7)
x ≡1(mod 3) x ≡ 1(mod 5) x ≡－2 (mod 7)
x ≡1(mod 3) x ≡ － 1(mod 5) x ≡2(mod 7)
x ≡1(mod 3) x ≡ － 1(mod 5) x ≡ － 2(mod 7)

数论01二次同余式与平方剩余

数论01二次同余式与平方剩余

平方非剩余
如果一个数$a$模$p$同余于$x^2$模$p$ ，则称$a$为$x^2$的平方非剩余。
判定法则
判定法则一
费马小定理，若$p$是质数，且$(a, p)=1$，则有$a^{p-1} equiv 1 pmod{p}$。
判定法则二
二次互反律，设$p, q$是两个不同的奇素数，且$(p, q)=1$，则有$(p equiv q pmod{4}) Leftrightarrow (q equiv p pmod{4})$。
03
具体的证明过程需要用到一些较为复杂的数学符号 和逻辑推导，这里不再赘述。
应用案例
01
02
03
在密码学中，二次同余 式与平方剩余的概念被 广泛应用于一些加密算 法的设计，如 RSA 算法
。
在数论研究中，这些概 念也是重要的工具，可 以帮助我们解决一些数
论中的难题。
在实际生活中，这些概 念在金融、物流等领域 也有一定的应用，例如 在电子支付和电子签名 的安全性验证等方面。
解释
这是一个关于 (x) 的二次方程，但它 的解必须满足同余条件，即解必须是 模 (m) 的同余类。
性质
性质1
如果 (a, b, c, m) 满足二次同余式的定义，那么对于任意整数 (x)，如果 (x^2 + bx + c equiv 0 (mod m)) 成立 ，那么 (ax^2 + bx + c equiv 0 (mod m)) 也一定成立。
THANKS
感谢观看
应用实例
在密码学中的应用
平方剩余在密码学中有重要的应用，例如RSA公钥密码算法中就使用了平方剩余的性质 。
在数论中的应用
平方剩余是数论中的一个重要概念，它在证明费马大定理、哥德巴赫猜想等数学问题中 发挥了重要作用。

数论基础

数论基础

第二节 孙 子 定 理
• 术曰： • 三三数之剩二, 置一百四十； • 五五数之剩三, 置六十三； • 七七数之剩二，置三十， • 并之，得二百三十三； • 以二百一十减之即得。
第二节 孙 子 定 理
• 凡三三数之剩一, 置七十； • 五五数之剩一, 置二十一； • 七七数之剩一，置十五， • 一百以上，以二百一十减之， • 即得。 （求一术）
(3)
• 因此，因此由第二章第一节定理1知 (2)有解的充要条件是 d|b。
第一节 同余方程的基本概念
• 若同余方程(2)有解x0，则存在y0，使得x0， y0是(3)式的解，此时，(3)式的全部解是
• 由式(4)所xy 确xy定00 的mddaxtt都满足，式t(2Z)。。
初等数论(四)
Number Theory （Chap4）
信阳职业技术学院 夏子厚
第四章 同余方程
• 教学目的和要求 • （1）理解同余方程（组）的基本概念， • （2）熟练掌握一次同余方程的解法，掌握质数模
的同余方程解的定理及其联系。
• （3）熟练掌握奇质数p的平方剩余和平方非剩余 的欧拉判别条件，会求模p的平方（非）剩余。
第二节 孙 子 定 理
• 题文是说:求解同余方程组n 2 (mod 3)， n 3(mod 5)，n 2 (mod 7)
• 术文（即解答）中指出解题的关键是找出 辅助系数F1，F2，F3，使其满足同余方程 35 F1≡1 (mod 3)
• 21F2≡1 (mod 5) • 15F3≡1 (mod 7) • 结果求得F1＝2，F2＝1，F3＝1。
• ab (p-1)(p-2) ······(p-a+1)
• (-1)a-1ba ! (mod p)

(完整word版)《数论算法》教案4章(二次同余方程与平方剩余)

(完整word版)《数论算法》教案4章(二次同余方程与平方剩余)

第 4 章 二次同余方程与平方剩余 内容 1. 二次同余方程，平方剩余2. 模为奇素数的平方剩余3. 勒让德符号、雅可比符号4. 二次同余方程的求解要点 二次同余方程有解的判断与求解4.1 一般二次同余方程(一) 二次同余方程2ax ＋bx ＋c ≡0（mod m ），（a 0（mod m ））（1） (二) 化简设m ＝k k p p p ααα 2121，则方程（1）等价于同余方程⎪⎪⎩⎪⎪⎨⎧≡++≡++≡++）（）（）（k k p c bx ax p c bx ax p c bx ax αααmod 0mod 0mod 02221221问题归结为讨论同余方程2ax ＋bx ＋c ≡0（mod αp ）， （p a ）（2） (三) 化为标准形式p ≠2，方程（2）两边同乘以4a ，422x a ＋4abx ＋4ac ≡0（mod αp ）()22b ax +≡2b －4ac （mod αp ）变量代换，y ＝2ax ＋b（3）有2y ≡2b －4ac （mod αp ） （4）当p 为奇素数时，方程（4）与（2）等价。

即● 两者同时有解或无解；有解时，对（4）的每个解()p y y mod 0≡，通过式（3）（x 的一次同余方程，且（p , 2a ）＝1，所以解数为1）给出（2）的一个解()p x x mod 0≡，由（4）的不同的解给出（2）的不同的解；反之亦然。

● 两者解数相同。

结论：只须讨论以下同余方程2x ≡a （mod αp ）（5）【例】化简方程7x 2＋5x －2≡0（mod 9）为标准形式。

（解）方程两边同乘以4a ＝4×7＝28，得196x 2＋140x －56≡0（mod 9）配方 (14x ＋5) 2－25－56≡0（mod 9）移项 (14x ＋5) 2≡81（mod 9）变量代换 y ＝14x ＋5得 y 2≡0（mod 9）（解之得y ＝0, ±3，从而原方程的解为x ≡114-(y －5)≡15- (y －5)≡2(y －5)≡2y －10≡2y －1≡－7, －1, 5≡－4, －1, 2（mod 9））(四) 二次剩余【定义4.1.1】设m 是正整数，a 是整数，m a 。

初等数论-第5章-二次同余式与平方剩余

初等数论-第5章-二次同余式与平方剩余

2023/11/11
7
例3. 解同余式 x2 x 1 0(mod72 ) (1)
解：x2 x 1 0(mod72 ) 4( x2 x 1) 0(mod72 )
即(2x 1)2 3 0(mod72 ) 令y 2x 1,
y2 3 0(mod72 )
(2)
而y2 3 0(mod7)的解为y 2(mod7). 令y 7t 2,代入(2)， 4t 1 0(mod7).
2023/11/11
19
定理2的证明：
由定理1知，平方剩余的个数等于同余式
p1
p1
x 2 1(mod p) 的解数，由 x 2 1 x p x，
所以据§4.4-TH5[P86]知，平方剩余的个数等于p
2
1
.
又模p的简化系中含有p-1个元素，
从而平方非剩余的个数等于 p 1 .
2
显然数列12 , 22 , ,( p 1)2中含有 p 1 个数，
第五章 二次同余式与平方剩余
§5.1一般二次同余式
2023/11/11
1
一、一般二次同余式的转化
二次同余式的一般形式为
ax2 bx c 0 (mod m)。
(1)
ax2
bx
c
0(mod
p ai i
),
i
1, 2,
,k.
其中，m
p p a1 a2 12
pkak , p1, p2 , . pk 为素数.
2023/11/11
4
ax2 bx c 0(mod p ), p (a,b,c) (2) 4、当p 2, 2 a,2 b时，(2)有解 2 c
f '( x) 2ax b 0(mod 2)无解 由§4.3－TH2〔P82〕知

二次同余式的解法

二次同余式的解法

二次同余式的解法1. 引言在数论和抽象代数中，同余是一个重要的概念。

同余关系是指两个整数之间具有相同的余数，即它们除以某个整数所得的余数相等。

在解决一些问题时，我们经常会遇到二次同余式，即形如x^2 ≡ a (mod m)的方程。

本文将介绍二次同余式的解法，并详细讨论三种常用的解法：勒让德符号、平方剩余和中国剩余定理。

2. 勒让德符号勒让德符号是二次剩余理论中一个重要的工具。

对于给定的整数a和素数p，勒让德符号(a/p)定义为：(a/p) = { 1, 若存在整数x满足x^2 ≡ a (mod p) -1, 若不存在整数x满足x^2 ≡ a (mod p) }根据勒让德符号，可以判断一个整数是否为平方剩余。

如果(a/p) = 1，则a是p模意义下的平方剩余；如果(a/p) = -1，则a是p模意义下的非平方剩余。

使用勒让德符号可以解决一些特殊情况下的二次同余式。

例如，当p是奇素数且a是整数时，如果(a/p) = 1，则二次同余式x^2 ≡ a (mod p)有两个解；如果(a/p) = -1，则无解。

3. 平方剩余平方剩余是指对于给定的整数a和模m，存在一个整数x使得x^2 ≡ a (mod m)成立。

平方剩余是二次同余式的一种特殊情况。

为了判断一个整数是否为平方剩余，可以使用勒让德符号。

对于给定的素数p和整数a，如果(a/p) = 1，则a是p模意义下的平方剩余；如果(a/p) = -1，则a是p 模意义下的非平方剩余。

当我们确定一个整数a是模m意义下的平方剩余后，可以进一步求解二次同余式x^2 ≡ a (mod m)。

其中m可以是任意正整数。

求解二次同余式有多种方法，如试位法、勒让德符号法和Tonelli-Shanks算法等。

这些方法都可以根据给定的模m和平方剩余a来找到所有满足条件的x。

4. 中国剩余定理中国剩余定理是一种用于求解一组同余方程组的方法。

对于给定的一组同余方程：x ≡ a1 (mod m1) x ≡ a2 (mod m2) … x ≡ an (mod mn)其中m1, m2, …, mn两两互质，中国剩余定理可以找到一个解x，且满足0 ≤ x < M = m1 * m2 * … * mn。

第五讲 二次剩余

第五讲 二次剩余

4、雅可比符号定义 对任意奇数m，定义为：
a a a m p1 pr
1, 1, 0,
a不一定是模m的平方剩余 若a是模m的平方非剩余 若(m, a) 1
课后作业
（1）习题1、3、8 （2）复习数论知识、 预习群
例2 判断同余式
x 2 1(mod305)
是否有解？有解时，求出其解数。 例3 判断同余式
x 2 2(mod413 )
是否有解？有解时，求出其解数。
四、雅可比符号
定义 设 m p1 pr 是奇素数 pi 的乘积。对任意整 数 a ，定义雅可比(Jacobi)符号为
a a a m p1 pr
m
n (5) 设m,n都是奇数，则 (1) m
m1 n1 2 2
m 。 n
例 判断同余式是否有解？
x2 286(mod563)
解：不用考虑563是否为素数，直接计算雅可比符号:
5635631 1431 5631 563 286 2 143 8 2 2 (1) (1) 563 563 563 143 1431 9 1 2 1 (1) 143 143
李艳俊一二次剩余的概念二模为奇素数的平方剩余与平方非剩余三勒让德符号四雅可比符号五小结一二次剩余的概念二次同余式的一般形式是bxax定义1设m是正整数若同余式有解则a叫做模m的平方剩余或二次剩余
第5讲 二次剩余
教师：李艳俊
本讲内容
一、二次剩余的概念
二、模为奇素数的平方剩余与平方非剩余
三、勒让德符号

信息安全数学第四章 二次同余式与平方剩余

信息安全数学第四章 二次同余式与平方剩余

4.1二次剩余与二次非剩余
定理3-2
在模p的缩系1,2,…,p-1中. 有(p-1)/2个模p的二 次剩余和(p-1)/2个模p的二次非剩余, 且： 12,22,…,((p-1)/2)2 是模p一缩系中的全部二次剩余
思路：r是解，则p-r也是，所以必有一解满足1≤x≤(p1)/2；再证这个范围的(p-1)/2个数d的平方两两不同余， 所以有(p-1)/2个模p的二次剩余, 从而模p的二次非剩 余也有: (p-1)-(p-1)/2=(p-1)/2 个.
性质3-1 ④ 若p是奇素数,则

2 p


1 ( p2 1) / 8
思路：在高斯引理中, 令a=2, 则:
2,2·2,2·3,…,3,(p-1)/2·2
已在1与p之间, 令计算满足p/2<2k<p,有p/4<k<p/2的k个数
则：m


p 2



p 4
高斯（gauss）引理
现ri要+s证j0这(m(po-1d)/p2).个数各不相同,只需证ri=p-sj,若ri=p-sj, 则
又于因(为p-r1i)/ta2(的m两od个p正),整sj数u.a于(m是o,d(t+p)u, )其a中(mt和odu是p)小. 因于为或, 等
(a,p)=1, 所以(t+u)0(mod p), 这是不可能的, 因为
(1≤i≤k, 1≤j≤m), 因此得:
p2 1
1
1 2 ( p 1) R mp S
8
2
又
p2
1a

( p1) / 2
ka

8
k 1

《数论算法》教案 4章同余方程

《数论算法》教案 4章同余方程

第 4 章 同余方程内容 1. 同余方程概念 2. 解同余方程3. `解同余方程组要点解同余方程 4.1 基本概念（一） 同余方程（1） 同余方程【定义4.1.1】设m 是一个正整数，f(x)为n 次多项式()0111a x a x a x a x f n n n n ++++=--其中i a 是正整数（n a 0（mod m ）），则f (x)≡0（mod m ） （1）叫做模m 的（n 次）同余方程（或模m 的（n 次）同余式），n 叫做f(x)的次数，记为deg f 或()[]x f ∂。

（2） 同余方程的解若整数a 使得 f (a)≡0（mod m ）成立，则a 叫做该同余方程的解。

（3） 同余方程的解数若a 是同余方程（1）的解，则满足x ≡a （mod m ）的所有整数都是方程（1）的解。

即剩余类a C ＝{x ｜x ∈Z ，x ≡a （mod m ）}中的每个剩余都是解。

故把这些解都看做是相同的，并说剩余类a C 是同余方程的一个解。

记为x ≡a （mod m ）当21,c c 均为同余方程(1)的解，且对模m 不同余时，就称它们是同余方程的不同的解，所有对模m 的两两不同余的解的个数，称为同余方程的解数，记作()m f T ;。

显然()m f T ;≤m若两个同余方程的解和解数相同，则称两个方程同解。

（4） 同余方程的解法一：穷举法任意选定模m 的一组完全剩余系，并以其中的每个剩余代入方程，在这完全剩余系中解的个数就是解数()m f T ;。

【例4.1.1】解同余方程15++x x ≡0（mod 7）。

（解）穷举：50＋0＋1＝1≡1 mod 751＋1＋1＝3≡3 mod 752＋2＋1＝35≡0 mod 753＋3＋1＝247≡2 mod 754＋4＋1＝1029≡0 mod 755＋5＋1＝3131≡2 mod 756＋6＋1＝7783≡6 mod 7【例2】求同余方程122742-+x x ≡0（mod 15）的解。

《数论算法》教案 5章(二次同余方程与平方剩余)共43页文档

《数论算法》教案 5章(二次同余方程与平方剩余)共43页文档

第5章 二次同余方程与平方剩余内容 1. 二次同余方程，平方剩余 2. 模为奇素数的平方剩余3. 勒让德符号、雅可比符号4. 二次同余方程的求解要点二次同余方程有解的判断与求解 5.1 一般二次同余方程（一） 二次同余方程2ax ＋bx ＋c ≡0（mod m ），（a 0（mod m ）） （1）（二） 化简设m ＝k kp p p αααΛ2121，则方程（1）等价于同余方程组 ⇒ 2ax ＋bx ＋c ≡0（mod αp ）， （pa ） （2）（三） 化为标准形式p ≠2，方程（2）两边同乘以4a ， 422x a ＋4abx ＋4ac ≡0（mod αp ）()22b ax +≡2b －4ac （modαp ）变量代换， y ＝2ax ＋b （3）有2y ≡2b －4ac （mod αp ） （4） 当p 为奇素数时，方程（4）与（2）等价。

即两者同时有解或无解；有解时，对（4）的每个解()p y y mod 0≡，通过式（3）（x 的一次同余方程，且（p ,2a ）＝1，所以解数为1）给出（2）的一个解()p x x mod 0≡，由（4）的不同的解给出（2）的不同的解；反之亦然。

两者解数相同。

结论：只须讨论方程 2x ≡a （mod αp ） （5）【例5.1.1】化简方程7x 2＋5x －2≡0（mod 9）为标准形式。

（解）方程两边同乘以4a ＝4×7＝28，得196x 2＋140x －56≡0（mod 9）配方 (14x ＋5) 2－25－56≡0（mod 9）移项 (14x ＋5) 2≡81（mod 9）变量代换 y ＝14x ＋5得 y 2≡0（mod 9）（解之得y ＝0, ±3，从而原方程的解为x ≡114-(y －5)≡15- (y －5)≡2(y －5)≡2y －10≡2y －1≡－7, －1, 5≡－4, －1, 2（mod 9））（四） 平方剩余【定义5.1.1】设m 是正整数，a 是整数，m a 。

二次同余式与平方剩余

二次同余式与平方剩余

本章的目的是较深入地讨论 1.一般二次 了解一般二次及：教学过程:本节主要讨论 2.单质数的 了解单质数的：教学过程:这节我们讨论单质数p 的)(mod 121p ap ≡-：而)(mod 121p ap -≡-单质数p 的使的)(mod ),(mod 222121p a r p a r ≡≡于是有)(mod )(21221p a a r r ≡ 这说明一般二次同余式在第四章中，我们讨论了高次同余式的解的一般理论，但在实际中，要解一个高次同余式一般比较困难。

在本章我们重点讨论二次同余式的解法。

思路是先把一般二次同余式化为特殊的二次同余式，再引入平方剩余与平方非剩余，并利用勒让得符号来判断特殊二次同余式是否有解。

二次同余式的一般形式 二次同余式的一般形式是，0 （） （1）化一般二次同余式为特殊二次同余式 由高次同余式的理论知，若的标准分解式为，则（1）有解的充要条件是下面同余式组中每个同余式有解。

于是要判别（1）是否有解及如何解（1），我们可重点讨论为质数。

（2）下面对（2）分情况进行讨论。

找到（2）有解的判别法。

由于（2）为二次同余式，故可假定，若有但(,,)，则（2）化为。

而。

故还可假定(,,)。

1) |，|。

则。

因而同余式无解。

故（2）设有解。

2)|，。

则无解，故（2）有解的充要条件是有解，即有解。

但（，）＝1。

故有解，从而（2）有解，且（2）的解可由的解求出。

3) ，>2。

则。

用4乘（2）后再配方，即得（3）易证（2）和（3）等价。

用代2＋得（4）则（2）有解的充要条件是（4）有解，于是将（2）化为（4）讨论。

4)，＝2。

这时为奇。

（i ）若2，则无解。

故（2）有解的充要条件是有解。

因对任何整数恒有。

所以（2）有解的充要条件是有解，即2|。

（ii ） 若2|，令。

由知（2）有解的充要条件是有解。

即(5)有解。

作代换＝＋，则（2）有解的充要条件是有解。

由上面讨论，可将（2）的问题化为二次同余式或一般情况即(6)平方剩余和非平方剩余定义 若同余式（6）有解，则叫模的平方剩余，若同余式（6）无解，则叫模的平方非剩余。

精品课件-信息安全数学基础(张金全)-第4章 二次同余方程

精品课件-信息安全数学基础(张金全)-第4章 二次同余方程
《信息安全数学基础》 第4章
《信息安全数学基础》 第4章
《信息安全数学基础》 第4章
《信息安全数学基础》 第4章
《信息安全数学基础》 第4章
《信息安全数学基础》 第4章
作业
《信息安全数学基础》 第4章
每一种知识都需要努力， 都需要付出，感谢支持！
知识就是力量，感谢支持！
《信息安全数学基础》 第4章
《信息安全数学基础》 第4章
勒让得符号-例题
《信息安全数学基础》 第4章
勒让得符号-例题
《信息安全数学基础》 第4章
勒让得符号-例题
《信息安全数学基础》 第4章
勒让得符号-例题
《信息安全数学基础》 第4章
4.3 扩展阅读
《信息安全数学基础》 第4章
《信息安全数学基础》 第4章
《信息安全数学基础》 第4章
二次互反律-性质
《信息安全数学基础》 第4章
二次互反律的发现和证明是一段有趣的掌故. 欧拉和勒让得发 现了二次互反律, 高斯花费了许多精力来寻求证明. 自从1796年得 到第一个证明后, 高斯继续寻求证明此定理的不同方法, 至少给出 了六种证明方法. 他寻求更多证明的目的是找到一种可以推广到更 高次幂的方法, 特别地, 他对素数的三次或四次剩余很感兴趣. 他 的第六个证明可以推广到高次幂的情形.
《信息安全数学基础》 第4章
平方剩余-性质
《信息安全数学基础》 第4章
《信息安全数学基础》 第4章
平方剩余-性质
《信息安全数学基础》 第4章
《信息安全数学基础》 第4章
4.2 Legendre（勒让得）符号
《信息安全数学基础》 第4章
欧拉判别法
《信息安全数学基础》 第4章
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第 4 章 二次同余方程与平方剩余 内容 1. 二次同余方程，平方剩余 2. 模为奇素数的平方剩余3. 勒让德符号、雅可比符号4. 二次同余方程的求解要点二次同余方程有解的判断与求解 4.1 一般二次同余方程(一) 二次同余方程2ax ＋bx ＋c ≡0（mod m ），（a0（mod m ）） （1）(二) 化简 设m ＝k k p p p αααΛ2121，则方程（1）等价于同余方程 ⎪⎪⎩⎪⎪⎨⎧≡++≡++≡++）（）（）（k k p c bx ax p c bx ax p c bx ax αααmod 0mod 0mod 02221221ΛΛ 问题归结为讨论同余方程 2ax ＋bx ＋c ≡0（mod αp ）， （p a ） （2）(三) 化为标准形式p ≠2，方程（2）两边同乘以4a ，422x a ＋4abx ＋4ac ≡0（mod αp ）()22b ax +≡2b －4ac （mod αp ）变量代换，y ＝2ax ＋b （3）有2y ≡2b －4ac （mod αp ） （4）当p 为奇素数时，方程（4）与（2）等价。

即● 两者同时有解或无解；有解时，对（4）的每个解()p y y mod 0≡，通过式（3）（x 的一次同余方程，且（p , 2a ）＝1，所以解数为1）给出（2）的一个解()p x x mod 0≡，由（4）的不同的解给出（2）的不同的解；反之亦然。

● 两者解数相同。

结论：只须讨论以下同余方程2x ≡a （mod αp ） （5）【例】化简方程7x 2＋5x －2≡0（mod 9）为标准形式。

（解）方程两边同乘以4a ＝4×7＝28，得196x 2＋140x －56≡0（mod 9）配方 (14x ＋5) 2－25－56≡0（mod 9）移项 (14x ＋5) 2≡81（mod 9）变量代换 y ＝14x ＋5 得 y 2≡0（mod 9）（解之得y ＝0, ±3，从而原方程的解为x ≡114-(y －5)≡15- (y －5)≡2(y －5)≡2y －10≡2y －1≡－7, －1, 5≡－4, －1, 2（mod 9））(四) 二次剩余【定义4.1.1】设m是正整数，a是整数，m a。

若同余方程2x≡a（mod m）（6）有解，则称a是模m的平方剩余（或二次剩余）；若无解，则称a是模m的平方非剩余（或二次非剩余）。

问题：（1）设正整数a是模p的平方剩余，若记方程（6）中的解为x≡a（mod m），那么此处的平方根a（modm）与通常的代数方程2x＝a的解a有何区别？（2）如何判断方程（6）有解？（3）如何求方程（6）的解？(五) 例【例1】1是模4平方剩余，－1是模4平方非剩余。

【例2】1、2、4是模7平方剩余，3、5、6是模7平方非剩余。

【例3】直接计算12，22，...，142得模15的平方剩余（实际上只要计算（12，22， (72)1，4，9，10，6平方非剩余：2，3，5，7，8，11，12，13，14【例4】求满足方程E：2y≡3x＋x＋1（mod 7）的所有点。

（解）对x＝0，1，2，3，4，5，6分别解出y：x＝0，2y≡1（mod 7），y≡1，6（mod 7）x＝1，2y≡3（mod 7），无解x ＝2，2y ≡4（mod 7），y ≡2，5（mod 7） x ＝3，2y ≡3（mod 7），无解 x ＝4，2y ≡6（mod 7），无解 x ＝5，2y ≡5（mod 7），无解 x ＝6，2y ≡6（mod 7），无解 所以，满足方程的点为（0, 1），（0, 6），（2, 2），（2, 5）。

说明：方程E ：2y ≡3x ＋x ＋1的图形称为椭圆曲线。

4.2 模为奇素数的平方剩余与平方非剩余 模为素数的二次方程2x ≡a （mod p ）, (a, p)＝1 （1）因为()2x -＝2x ，故方程（1）要么无解，要么有两个解。

(一) 平方剩余的判断条件【定理4.2.1】（欧拉判别条件）设p 是奇素数，(a, p)＝1，则（i ）a 是模p 的平方剩余的充要条件是()21-p a ≡1（mod p ） （2）（ii ）a 是模p 的平方非剩余的充要条件是()21-p a ≡－1（mod p ） （3）并且当a 是模p 的平方剩余时，同余方程（1）恰有两个解。

（证）先证p a 时，式（2）或（3）有且仅有一个成立。

由费马定理 1-p a ≡1（mod p ）()()221-p a －1≡0（mod p ）()()()()112121+---p p a a ≡0（mod p ） （4） 即 11--p a p ＝()()()()112121+---p p a a 但 ()()()1,12121+---p p a a ＝1或2且素数p>2。

所以，p 能整除()()()()112121+---p p a a ，但p 不能同时整除()121--p a 和()121+-p a （否则，p 能整除它们的最大公因子1或2）所以，由式（4）立即推出式（2）或式（3）有且仅有一式成立。

（i ）必要性。

若a 是模p 的二次剩余，则必有0x 使得20x ≡a （mod p ）， 因而有 ()()21p 20-x ≡()21-p a （mod p ）。

即 ()2110--≡p p a x （mod p ）。

由于p a ，所以p 0x ，因此由欧拉定理知10-p x ≡1（mod p ）。

即（2）式成立。

充分性。

已知()21-p a≡1（mod p ），这时必有p a 。

故一次同余方程 bx ≡a （mod p ）, (1≤b ≤p －1) （5） 有唯一解，对既约剩余系－(p －1)/2，…，－1，1，…，(p －1)/2 （6） 由式（6）给出的模p 的既约剩余系中的每个j ，当b ＝j 时，必有唯一的j x x =属于既约剩余系（6），使得式（5）成立。

若a 不是模p 的二次剩余，则必有j x j ≠。

这样，既约剩余系（6）中的p －1个数就可按j 、x j 作为一对，两两分完。

（b 1≠b 2，则相应的解x 1≠x 2，且除了±1之外，每个数的逆不是它本身）因此有()().mod )!1(21p a p p -≡-由威尔逊定理知()().mod 121p a p -≡-与式（2）矛盾。

所以必有某一0j ，使00j x j =，由此及式（5）知，a 是模p 的二次剩余。

（ii ）由已经证明的这两部分结论，立即推出第（ii ）条成立。

其次，若0x 0（mod p ）是方程（1）的解，则－0x 也是其解，且必有0x －0x （mod p ）。

故当(a , p )＝1时，方程（1）要么无解，要么同时有两个解。

（说明：本定理只是一个理论结果，当p >>1时，它并不是一个实用的判断方法）小结：对于任何整数a ，方程（1）的解数可能为T (x 2－a ；p )＝0, 1, 2 【例1】设p ＝19，验证定理4.2.1的证明过程。

（解）由费马定理知，对任何a ＝1, 2, …, 18，都有18a ≡1（mod 19）。

方程2x ≡1（mod 19）只有两个解，即x ≡±1（mod 19）。

从而必有9a ≡±1（mod 19）（视()2918a a ≡≡1（mod 19），即9a x ≡）针对必要性：例如a ＝17是模19的二次剩余，即存在0x ≡6使得26≡17（mod 19）。

那么必有 ()21-p a ≡917≡186≡1（mod 19）针对充分性：例如a ＝6，()21-p a ≡96≡1（mod 19），验证6是二次剩余。

解方程bx ≡6（mod 19）, (1≤b ≤18)当b ≡1, 2, 3, 4, 5, …, 17, 18（mod 19）时，方程有唯一解x ≡6, 3, 2, 11, 5, …, 16, 13（mod 19）其中 5•5≡6（mod 19）即当b ≡5时，x ≡5。

所以6是二次剩余。

又选a ＝8，()21-p a ≡98≡－1（mod 19），验证：解方程bx ≡8（mod 19）, (1≤b ≤18)得 1•8≡8， 2•4≡8， 3•9≡8， 4•2≡8， 5•13≡8， 6•14≡8， 7•12≡8， 8•1≡8， 9•3≡8， 10•16≡8， 11•18≡8， 12•7≡8， 13•5≡8， 14•6≡8， 15•17≡8， 16•10≡8， 17•15≡8， 18•11≡81•2• (18)(1•8)( 2•4)( 3•9)( 5•13)( 6•14)( 7•12)( 10•16)( 11•18)( 15•17)≡98≡－1（mod 19）【例2】判断137是否为模227的平方剩余。

（解）首先，227是素数。

其次，计算()1227137-≡－1（mod 227）所以，137是模227的平方非剩余。

【推论】设p 是奇素数，(a 1, p )＝1，(a 2, p )＝1，则 （i ）若a 1，a 2都是模p 的平方剩余，则a 1a 2是模p 的平方剩余；（ii ）若a 1，a 2都是模p 的平方非剩余，则a 1a 2是模p 的平方剩余；（iii ）若a 1是模p 的平方剩余，a 2是模p 的平方非剩余，则a 1a 2是模p 的平方非剩余。

（证）因()()2121-p a a ＝()()212211--p p a a(二) 平方剩余的个数【定理4.2.2】设p 是奇素数，则模p 的既约剩余系中平方剩余与平方非剩余的个数各为(p －1)／2，且(p －1)／2个平方剩余恰与序列12，22，…，221⎪⎭⎫ ⎝⎛-p 中的一个数同余。

（证）由定理4.2.1，模p 的平方剩余个数等于方程 21-p x≡1（mod p ）的解数。

但 1121---p p x x由定理3.4.5知，方程的解数为21-p ，即平方剩余的个数是21-p ，且平方非剩余的个数是(p －1)－21-p ＝21-p 。

其次，可以证明当1≤k 1≤21-p ，1≤k 2≤21-p ，且k 1≠k 2时，有21k 22k mod p 。

故结论成立。

（定理3.4.5：设p 为素数，n 为正整数，n ≤p 。

则同余方程()x f ＝0111a x a x a x n n n ++++--Λ≡0 mod p 有n 个解⇔x x p -被()x f 除所得余式的所有系数都是p 的倍数）4.3 勒让德符号目的：快速判断整数a 是否为素数p 的平方剩余。

(一) 勒让德符号【定义4.3.1】设p 是素数，定义勒让德（Legendre ）符号为：L(a, p)＝⎪⎪⎭⎫ ⎝⎛p a ＝⎪⎩⎪⎨⎧-。