信息安全数学基础4章节4讲

《信息安全数学基础4章节4讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章整除与同余整数的整除一不定方程二同余方程求解四二次剩余五整数的同余三12一般二次同余式的一般形式为ax2bxc0(modm)。该同余式可以化简为4.5二次剩余-平方剩余3若有解，则a称为模m的平方剩余；否则，称a为模m的平方非剩余。∴模3的平方剩余为1；平方非剩余为2(或-1).4.5二次剩余-平方剩余4∴模5的平方剩余为1,4；平方非剩余为2,3.4.5二次剩余-平方剩余5∴模7的平方剩余为1，2，4；平方非剩余为6，5，3.∴模11的平方剩余为1，-2，3，4，5；平方非剩余为-1，2，-3，-4，-5.4.5二次剩余-平方剩余

2、6本节先讨论形如的同余式的解。定理4.50设p是奇素数,在模p的意义下,就是模p的简化剩余类中的全部二次剩余。4.5二次剩余-平方剩余判别7定理4.51模p的简化系中，二次剩余与二次非剩余的个数都是且模p的每个二次剩余与且仅与数列中的一个数同余。模7的平方剩余为1，2，-3；平方非剩余为-1，-2，3.4.5二次剩余-平方剩余判别8定理4.52(欧拉判别条件)若(a,p)=1，则（1）a是模p的二次剩余的充要条件是（2）a是模p的二次非剩余的充要条件是4.5二次剩余-平方剩余判别9可以验证：∴模11的平方剩余为1，-2，3，4，5；平方非剩余为

3、-1，2，-3，-4，-5.4.5二次剩余-平方剩余判别10利用欧拉判别条件虽然可以判定x2a(modp)的解的存在性，但对较大的质数模，实际运用很困难。通过引入勒让德符号，本节给出了较方便的判别方法。阿德昂·利·埃·勒让德（公元1752─公元1833）,法国数学家4.5二次剩余-勒让德符号11定理4.53给定奇素数p,对于整数n,定义Legendre符号为如,1与4是模5的平方剩余，2与3是模5的平方非剩余，4.5二次剩余-勒让德符号124.5二次剩余-勒让德符号13例：4.5二次剩余-勒让德符号14定理4.54下面的结论成立：4.5二次剩

4、余-勒让德符号154.5二次剩余-勒让德符号16例：令。欧拉判别：上述定理：4.5二次剩余-勒让德符号17定理4.55(二次互反律)设p与q是不同的两奇素数，则欧拉猜测下面定理成立，但未能证明：例：德国数学家高斯17岁时证明了二次互反律！4.5二次剩余-勒让德符号18例4.5二次剩余-勒让德符号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、转化为计算(5)重复以上步骤，直至求出每个4.5二次剩余-勒让德符号20对于奇素数p,利用计算Legendre符号可以判定方程x2a(modp)(1)是否有解。对于一般的正整数m，，如何判定方程是否有解呢？x2a(modm)(2)4.5二次剩余-雅克比符号21对于一般的正整数m，如果它的标准分解式是那么判定方程x2a(modm)(2)是否有解，可归结为对形如方程x2a(modp)(1)的可解性判定。因此，在理论上，利用Legendre符号可以判定方程(2)是否有解。但是，写出正整数的标准分解式常会遇到实际困难，所以利用Legendre符

6、号判定方程(2)的可解性并不容易实现。4.5二次剩余-雅克比符号22定理4.56给定正奇数m>1，m=p1p2pk，其中pi（1ik）是奇素数，对于任意的整数a，（1ik）是Legendre符号，称是Jacobi符号。例:取m=45=335，则4.5二次剩余-雅克比符号23注1:当m是奇素数时，Jacobi符号就是Legendre符号。前者是后者的推广。注2:如果m是奇素数，当=1时，方程x2a(modm)有解。当m不是奇素数时，这个结论不一定成立。例如，方程x25(mod9)无解，显然，若则方程x2a(modm)必无解。4

7、.5二次剩余-雅克比符号24定理4.57使用前面定义中的符号，下面的结论成立：(1)若aa1(modm)，则(3)对于任意的整数a1,a2,,at，有(4)对于任意的整数a，b，(a,m)=1，有4.5二次剩余-雅克比符号25定理4.58设m=p1p2pk是奇数,其中p1,p2,pk是素数,例4.5二次剩余-雅克比符号26定理4.59设m，n是大于1的奇整数，则注：利用以上定理，我们可以很容易地计算Jacobi符号的数值。但是，在判断方程(2)的可解性时，Legendre符号和Jacobi的作用是不一样的。4.5二次剩余-雅克比符号例:

8、已知3371是素数，判断方程x212345(mod3371)是否有解。解:利用Jacobi符号的性质，有因此，方程无解。4.5二次剩余-雅克比符号例