信息安全数学基础4章4讲.pptxVIP

第四章整除与同余整数整除一不定方程二同余方程求解四二次剩下五整数同余三1第1页

2普通二次同余式普通形式为ax2?bx?c?0(modm)。该同余式能够化简为4.5二次剩下-平方剩下第2页

3若有解，则a称为模m平方剩下；不然，称a为模m平方非剩下。∴模3平方剩下为1；平方非剩下为2(或-1).4.5二次剩下-平方剩下第3页

4∴模5平方剩下为1,4；平方非剩下为2,3.4.5二次剩下-平方剩下第4页

5∴模7平方剩下为1，2，4；平方非剩下为6，5，3.∴模11平方剩下为1，-2，3，4，5；平方非剩下为-1，2，-3，-4，-5.4.5二次剩下-平方剩下第5页

6本节先讨论形如同余式解。定理4.50设p是奇素数,在模p意义下,就是模p简化剩下类中全部二次剩下。4.5二次剩下-平方剩下判别第6页

7定理4.51模p简化系中，二次剩下与二次非剩下个数都是且模p每个二次剩下与且仅与数列中一个数同余。模7平方剩下为1，2，-3；平方非剩下为-1，-2，3.4.5二次剩下-平方剩下判别第7页

8定理4.52(欧拉判别条件)若(a,p)=1，则（1）a是模p二次剩下充要条件是（2）a是模p二次非剩下充要条件是4.5二次剩下-平方剩下判别第8页

9能够验证：∴模11平方剩下为1，-2，3，4，5；平方非剩下为-1，2，-3，-4，-5.4.5二次剩下-平方剩下判别第9页

10利用欧拉判别条件即使能够判定x2?a(modp)解存在性，但对较大质数模，实际利用很困难。经过引入勒让德符号，本节给出了较方便判别方法。阿德昂·利·埃·勒让德（公元1752─公元1833）,法国数学家4.5二次剩下-勒让德符号第10页

11定理4.53给定奇素数p,对于整数n,定义Legendre符号为如,1与4是模5平方剩下，2与3是模5平方非剩下，4.5二次剩下-勒让德符号第11页

124.5二次剩下-勒让德符号第12页

13例：4.5二次剩下-勒让德符号第13页

14定理4.54下面结论成立：4.5二次剩下-勒让德符号第14页

154.5二次剩下-勒让德符号第15页

16例：令。欧拉判别：上述定理：4.5二次剩下-勒让德符号第16页

17定理4.55(二次互反律)设p与q是不一样两奇素数，则欧拉猜测下面定理成立，但未能证实：例：德国数学家高斯17岁时证实了二次互反律！4.5二次剩下-勒让德符号第17页

18例4.5二次剩下-勒让德符号第18页

19普通地，若p是素数，计算可按以下步骤进行：(1)求出n0?n(modp)，1?n0?p；(2)将n0写成n0=Q2q1q2?qk形式，其中Q?Z，q1,q2,?,qk是互不相同素数；(3)若有某个qi=2，直接判定之值；(4)若qi?2，将计算转化为计算(5)重复以上步骤，直至求出每个4.5二次剩下-勒让德符号第19页

20对于奇素数p,利用计算Legendre符号能够判定方程x2?a(modp)(1)是否有解。对于普通正整数m，，怎样判定方程是否有解呢？x2?a(modm)(2)4.5二次剩下-雅克比符号第20页

21对于普通正整数m，假如它标准分解式是那么判定方程x2?a(modm)(2)是否有解，可归结为对形如方程x2?a(modp)(1)可解性判定。所以，在理论上，利用Legendre符号能够判定方程(2)是否有解。不过，写出正整数标准分解式常会碰到实际困难，所以利用Legendre符号判定方程(2)可解性并不容易实现。4.5二次剩下-雅克比符号第21页

22定理4.56给定正奇数m1，m=p1p2?pk，其中pi（1?i?k）是奇素数，对于任意整数a，（1?i?k）是Legendre符号，称是Jacobi符号。例:取m=45=3?3?5，则4.5二次剩下-雅克比符号第22页

23注1:当m是奇素数时，Jacobi符号就是Legendre符号。前者是后者推广。注2:假如m是奇素数，当=1时，方程x2?a(modm)有解。当m不是奇素数时，这个结论不一定成立。比如，方程x2?5(mod9)无解，显然，若