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

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

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

下载文档原格式

  / 49

合集下载

《平方剩余》课件

《平方剩余》课件
详细描述
选取一个较大的模数，并计算出满足模数的平方根。在这个过程中，可以深入探讨平方剩余的性质， 如模数的周期性、模数的奇偶性等。同时，也可以介绍平方剩余在密码学、数论等领域的应用。
实例三：实际应用中的平方剩余
总结词
通过实际应用案例，展示平方剩余在解决实际问题中的价值。
详细描述
介绍一些实际应用案例，如利用平方剩余解决几何问题、利用平方剩余进行数据加密等。通过这些案例，可以说 明平方剩余在实际问题中的应用价值，并激发学习者对数学的兴趣和热情。
详细描述
费马小定理是数论中的一个重要 定理，它说明了模n的同余方程 x^2≡a(mod n)有解的充分必要 条件是a^(n-1)≡1(mod n)。利用 费马小定理，我们可以证明平方 剩余。
证明方法二：欧拉定理
总结词
欧拉定理是数论中的另一个重要定理，它揭示了模n的指数和 与模n的乘法逆元之间的关系。通过欧拉定理，我们可以证明 平方剩余。
平方剩余与离散对数问题之间存在一 定的联系。离散对数问题是一个著名 的数学难题，而平方剩余在解决某些 离散对数问题时具有一定的帮助。
通过利用平方剩余的性质，可以设计 出一些算法来求解离散对数问题，这 对于密码学和网络安全等领域具有重 要意义。
在密码学中的应用
平方剩余在密码学中有广泛的应用，因为它们具有一些特 殊的数学性质，这些性质使得它们在加密和解密过程中具 有重要的作用。
详细描述
中国剩余定理说明了对于任意给定的正整数m1,m2,...,ms，且两两互质，存在 唯一的一组解x1,x2,...,xs，满足xi≡b[i] (mod mi)(i=1,2,...,s)，并且mi|(b[i+1]b[i])。利用中国剩余定理，我们可以证明平方剩余。

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

第4讲二次同余与平方剩余
227 2 −1 ⋅ 8
227
227
5−1 227 −1 ⋅ 227 2 ( )(−1) 2 5
2 = ( ) = (−1) = −1 。 东北大学数学系 5
52 −1 8
朱和贵
4.4二次互反律的证明
定理4 (二次互反律) 设p与q是不相同的两个素数，则
⎛ p⎞ ⎛ q⎞ ( p −1) / 2⋅( q −1) / 2 ⎜ ⎟ = ⎜ ⎟ ( −1) ⎝ q ⎠ ⎝ p⎠
东北大学数学系
朱和贵
4.1 一般二次同余式
定义１ 给定整数m，对于任意的整数a，(a，m) = 1，若方程x2 ≡ a (mod m)有解，则称a是模m的二 次剩余；否则，称a是模m的二次非剩余. 例1验证1是模4的平方剩余,-1是是模4的非平方剩余 例 2 1,2,4 是模7的平方剩余,-1,3,5是模7的非平方 剩余 解 因为,12≡1, 22≡4, 32≡2, 42≡2， 52≡4 ， 62≡1 （mod7），
证明: 定理4也是要证明
⎛ p ⎞⎛ q ⎞ ( p −1) / 2⋅( q −1) / 2 ⎜ ⎟ ⎜ ⎟ = ( −1) ⎝ q ⎠⎝ p ⎠
东北大学数学系
朱和贵
4.4二次互反律的证明
因为
∑[ ] q ( ) = (−1) i=1 p
qi p
p −1) / 2
( q −1) / 2
( p ) = (−1)
⎜ ⎟ = (− 1) ⎜ p⎟ ⎝ ⎠
证明: r1, r2, …, rk表示a,2a,…,,(p-1)/2a的模p最小剩余 小于或等于(p-1)/2的数, 而s1, s2, …, sm表示它们中 大于(p-1)/2的数, 显然k+m=(p-1)/2, 且:

《平方剩余》课件

《平方剩余》课件
《平方剩余》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

名师推荐数论01二次同余式与平方剩余32页PPT

名师推荐数论01二次同余式与平方剩余32页PPT
名师推荐数论01二次同余式与平方剩 余
46、法律有权打破平静。——马·格林 47、在一千磅法律里，没有一盎司仁 爱。— —英国
48、法律一多，公正就少。——托·富 勒 49、犯罪总是以惩罚相补偿；只有处 罚才能 使犯罪 得到偿 还。— —达雷厄尔
谢谢
11、越是没有本领的就越加自命不凡。——邓拓 12、越是无能的人，越喜欢挑剔别人的错儿。——爱尔兰 13、知人者智，自知者明。胜人者有力，自胜者强。——老子 14、意志坚强的人能把世界放在手中像泥块一样任意揉捏。——歌德 15、最具挑战性的挑战莫过于提升自我。——迈克尔·F·斯特利

第四章 二次剩余

第四章 二次剩余
第四章 二次同余式与平方剩余
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公钥密码算法中就使用了平方剩余的性质 。
在数论中的应用
平方剩余是数论中的一个重要概念，它在证明费马大定理、哥德巴赫猜想等数学问题中 发挥了重要作用。

二次同余式和平方剩余

二次同余式和平方剩余

§2 勒让德符号
定义：p是一个给定的奇素数，对于整数a定 义勒让德符号
1, a是平方剩余
( 例：
a) p
(1)
1, a是平方剩余
0, p | a
1, (2) 1, (3) 1, (4)
1
55
5
5
为了更方便地计算勒让德符号，我们给出其 相关的性质，即有下面的定理。
定理1：（1）
(a)
p 1
有解。例
(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
a )
pi
m)
=-1,
无解.
下面给出雅可比符号的类似于勒让德符号性质，
定理：在模P的简化系中，平方剩余和平方非
剩余余各为 p 1个
p 1
2
且 余，2而个且平仅方与乘一余数分一别同与余。1,22 ,
(
p 1)2 2
之一同
证明如下:
证：由欧拉判别定理知平方剩余的个数是
p 1
p 1
x 2 1(mod p) 的解数。但 x p x (x 2 1)q(x)
其余式为0，由定理知
(143) 563
时，可以不
要管143是否为素数而直接用二次互反律，为
计算提供了方便。
例2：若 ( d ) 1, 则p 不能写成x2 dy2 的形式
p
证：若p= x2 dy2 ,则有若P|x, 则有 p|y
于是可设 x px1, y py1

数论基础

数论基础

第二节 孙 子 定 理
• 术曰： • 三三数之剩二, 置一百四十； • 五五数之剩三, 置六十三； • 七七数之剩二，置三十， • 并之，得二百三十三； • 以二百一十减之即得。
第二节 孙 子 定 理
• 凡三三数之剩一, 置七十； • 五五数之剩一, 置二十一； • 七七数之剩一，置十五， • 一百以上，以二百一十减之， • 即得。 （求一术）
(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 。

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

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

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 章 同余方程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）的解。

（解）取模15的绝对最小完全剩余系：－7，－6，…，－1，0，1，2，…，7直接代入方程得解：x ≡－6，3（mod 15）， ()15;f T ＝2。

浅谈二次剩余——求解二次同余方程

浅谈二次剩余——求解二次同余方程

浅谈⼆次剩余——求解⼆次同余⽅程1.⼆次同余式⼆次同余式是关于未知数的⼆次多项式的同余⽅程。

即：是⼀个⼆次同余⽅程。

此外，称为最简⼆次同余式，或称最简⼆次同余⽅程。

⼀般的，通过配⽅，可以把⼀个⼀般的⼆次同余⽅程转化为⼀个最简⼆次同余式接下来只需要讨论最简⼆次同余式。

2⼆次剩余2.1 前置概念、定理即证明：若⽆特殊说明，下⾯的模运算都是在模p的意义下1.有正整数n，奇质数p，且p∤n，若存在⼀个正整数x，使得x2≡n(mod则称n为p的⼆次剩余。

2.勒让德符号\begin{pmatrix}\dfrac{n}{p}\end{pmatrix}，若n为p的⼆次剩余，则该值为1，若不是则该值为-1，若p\mid n，则该值为0定理1：\begin{pmatrix}\dfrac{n}{p}\end{pmatrix}\equiv n^{\frac{p-1}{2}}证明：1.若p能整除n，那右边明显模p与0同余，故成⽴。

2.若n是p的⼆次剩余，则根据费马⼩定理(n^{p-1}\equiv1(\bmod p)其中，p为质数)，有n^{\frac{p-1}{2}} = {\sqrt{n}^{p-1}}\equiv 1，故成⽴3.若n不是p的⼆次剩余，则根据扩展欧⼏⾥得算法，对于i\in[1,p-1]都有唯⼀的j\in[1,p-1],i\neq j且ij\equiv n这样的数⼀共有\frac{p-1}{2}个，因此\frac{p-1} {2}\equiv (p-1)!根据威尔逊定理)(：当且仅当p为素数时有：( p -1 )! \equiv -1 ( \bmod p ))，就有\frac{p-1}{2}\equiv -1证毕威尔逊定理证明：我们知道1\times1\equiv 1(mod p),( − 1 ) \times ( − 1 )\equiv (mod p)，且仅有这两组的逆元与本⾝相等。

如果x^2\equiv 1(\bmod p)那么通过移项再因式分解可以得到x=-1或x=1，除了1，-1这两个数之外，2⾄p-2中的每⼀个数都⼀定有⼀个对应的逆元（注明：-1\equiv p-1(\bmod p)）且⼀定与⾃⼰不相等，且每⼀个数与他的逆元⼀⼀对应。

数论 03二次同余式与平方剩余共25页文档

数论 03二次同余式与平方剩余共25页文档

66、节制使快乐增加并使享受加强。 ——德 谟克利 特 67、今天应做的事没有做，明天再早也 是耽误 了。——裴斯 泰洛齐 68、决定一个人的一生，以及整个命运 的，只 是一瞬 之间。 ——歌 德 69、懒人无法享受休息之乐。——拉布 克 70、浪费时间是一桩大罪过。——卢梭
数论 03二次同余式与平方剩 余
31、别人笑我太疯癫，我笑他人看不 穿。(名 言网) 32、我不想听失意者的哭泣，抱怨者 的牢骚 ，这是 羊群中 的瘟疫 ，我不 能被它 传染。 我要尽 量避免 绝望， 辛勤耕 耘，忍 受苦楚 。我一 试再试 ，争取 每天的 成功， 避免以 失败收 常在别 人停滞 不前时 ，我继 续拼搏 。
33、如果惧怕前面跌宕的山岩，生命 就永远 只能是 死水一 潭。 34、当你眼泪忍不住要流出来的时候 ，睁大 眼睛， 千万别 眨眼!你会看到 世界由 清晰变 清澈明 晰。盐 。注定 要融化 的，也 许是用 眼泪的 方式。
35、不要以为自己成功一次就可以了 ，也不 要以为 过去的 光荣可 以被永 远肯定 。

《数论算法》教案 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. 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 ＝⎪⎩⎪⎨⎧-。