资源描述
第四章整除与同余,1,2,是关于模m的同余方程，或同余式.,则称为n次同余方程.,注：若则剩余类里的元素都满足该方程.,定义4.41,4.4同余方程求解-同余式概念,3,即与a同余的一切整数作为（1）式的一个解。,注：同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数.显然，同余方程(1)的解数不超过m.,4.4同余方程求解-同余式概念,4,定理4.43设a，b是整数，a0(modm).则同余方程,axb(modm)(2),有解的充要条件是(a,m)b。,证明axb(modm),同余方程(2)等价于不定方程axmy=b.(3),因此，定理得证。,4.4同余方程求解-一次同余式,5,若同余方程(2)有解x0，则存在y0，使得x0与y0是方程(3)的解，,由式(4)所确定的x都满足方程(2).,此时，方程(3)的解是,4.4同余方程求解-一次同余式,6,所以，当r=0,1,2,d1时，相应的解,对模m是两两不同余的，即同余方程(2)恰有d个解.,4.4同余方程求解-一次同余式,记d=(a,m),以及t=dqr,qZ,r=0,1,d1.,0rd1.,7,例：解同余式,4.4同余方程求解-一次同余式,8,定理4.44设(a,m)=1,有整数0使得a1(modm)，,则同余方程axb(modm)的解是xba1(modm).,注：由上述定理及Euler定理可知，若(a,m)=1，则,xba(m)1(modm)是同余方程axb(modm)的解。,例解同余方程,解：xba(21)1,4.4同余方程求解-一次同余式,9,4.4同余方程求解-背包密码,给定一组n个重量W0,W1,.,Wn-1和一个总重量S,能否找到一组系数ai0,1满足S=a0W0+a1W1+.+an-1Wn-1(也称其为“子集-和”问题)实例重量(62,93,26,52,166,48,91,141)问题：找到系数满足S=302答案:62+26+166+48=302此处系数为（10101100）已证明一般背包问题是NP完全问题(非常难解),10,4.4同余方程求解-背包密码,一般背包问题很难解决，但超递增背包问题很容易解决;超递增背包要求重量递增排列且每个重量比前面所有重量和还大;实例重量(2,3,7,14,30,57,120,251)问题:找出子集满足和=186从大到小逐步推算答案:120+57+7+2=186系数为(1,0,1,0,0,1,1,0),11,4.4同余方程求解-背包密码,假设(2,3,7,14,30,57,120,251)是超级递增背包选择m=41,n=491.这里m,n互素并且n大于背包各元素之和则普通背包产生方式：241mod491=82341mod491=123741mod491=2871441mod491=833041mod491=2485741mod491=37312041mod491=1025141mod491=471普通背包:(82,123,287,83,248,373,10,471),12,4.4同余方程求解-背包密码,私钥:(2,3,7,14,30,57,120,251)及12（m1modn称为m的模逆）公钥:(82,123,287,83,248,373,10,471),n=491实例:加密明文1001011082+83+373+10=548（密文）解密,(54812)mod491=6576mod491=193用私钥(2,3,7,14,30,57,120,251)解193得到明文10010110(2+14+57+120=193),13,4.4同余方程求解-背包密码,如果没有私钥(2,3,7,14,30,57,120,251),12攻击者须找到公钥(82,123,287,83,248,373,10,471)里的某个子集满足元素之和为491变成了普通背包问题，非常难解将超递增背包通过模运算转换为普通背包就是陷门，没有私钥的情况下将很难解密,14,4.4同余方程求解-背包密码,陷门:通过模运算将超级超递增背包转换为一般递增背包单向:一般背包容易用来加密，难解密;超递增则容易解密这种背包密码系统是不安全的在1983被苹果II电脑破解攻击采用的是格约简(latticereduction)技术现在很多背包密码的变形,15,4.4同余方程求解-孙子定理,16,瑛姑待她写出最后一项答数，叹道：“这中间果然机妙无穷。”顿了顿，说道：“这第三道题呢，说易是十分容易，说难却又难到了极处。今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？我知道这是二十三，不过那是硬凑出来的，要列一个每数皆可通用的算式，却是想破了脑袋也想不出。”黄蓉笑道：“这容易得紧。以三三数之，余数乘以七十；五五数之，余数乘以二十一；七七数之，余数乘十五。三者相加，如不大于一百零五，即为答数，否则须减去一百零五或其倍数。”瑛姑在心中盘算了一遍，果然丝毫不错，低声记诵道：“三三数之，余数乘以七十；五五数之”黄蓉道：“也不用这般硬记，我念一首诗给你听，那就容易记了：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，余百零五便得知。”,4.4同余方程求解-孙子定理,17,分析设所求物数为x，则有,称之为同余式组。,即要求这些同余式的公共解。,4.4同余方程求解-孙子定理,18,定理4.46孙子定理,m1,m2,mk是两两互质的正整数，,记m=m1m2mk，,则(5)的解为,其中,整数Mi（1ik）,满足MiMi1(modmi).,设有同余式组,4.4同余方程求解-孙子定理,19,例1解同余式组,4.4同余方程求解-孙子定理,20,例2韩信点兵有兵一队，若列成五行纵队，则末行1人；成六行纵队，则末行5人；成七行纵队，则末行4人；成十一行纵队，则末行10人。求兵数。,4.4同余方程求解-孙子定理,21,列表如下：,14623,53851,43301,102101,6731,3,1,1,1,4.4同余方程求解-孙子定理,22,4.4同余方程求解-同余方程组,例：求解同余方程组,23,定理4.47：设a1，a2是整数，m1，m2是正整数，则同余方程组,有解的充要条件是a1a2(mod(m1,m2),若有解，则对模m1,m2是唯一的，即若x1与x2都是同余方程组(7)的解，则x1x2(modm1,m2)。,4.4同余方程求解-同余方程组,24,4.4同余方程求解-同余方程组,例：求解同余方程组,25,注：由上述定理，解一般模的同余方程可以转化为解模为素数幂的同余方程。,定理4.48设m=m1m2mk,其中m1,m2,mk是两两,互素的正整数，,同余方程f(x)0(modm)有解充要,f(x)0(modmi)，1ik有解，且利用孙,以T与Ti的表示解的个数，,则T=T1T2Tk。,条件是,子定理得到模m的解一致.,4.4同余方程求解-高次同余方程,26,因为ab(modmi)，1ik,ab(modm)，,即同余方程(8)等价于同余方程组(9),且解个数相同,对于每个i（1ik），设同余方程组的全部解是,由孙子定理，对于选定的每一组,如下同余方程组对模m有唯一解。,4.4同余方程求解-高次同余方程,27,例解同余方程5x26x490(mod60).(10),解：60=345，同余方程(10)等价于同余方程组,5x26x490(mod3)即-x210(mod3)(11)5x26x490(mod4)即x22x10(mod4)(12)5x26x490(mod5)即x-10(mod5)(13),由(11)得：,x1(1)1，x2(1)1(mod3)，,由(12)得：,x1(2)1，x2(2)1(mod4)，,由(13)得：,x1(3)1(mod5),4.4同余方程求解-高次同余方程,28,这样，同余方程(10)的解x可由下面的方程组决定：,xa1(mod3)，xa2(mod4)，xa3(mod5)，其中a1=1或1，a2=1或1，a3=1。,利用孙子定理，其中m1=3,m2=4,m3=5,m=60.,M1=20,M2=15,M3=12,M1=2,M2=1,M3=3，,则x40a115a236a3(mod60)。,将a1，a2，a3所有可能的取值代入上式，得到方程(10)的全部解是,x11(mod60)，x219(mod60)，x331(mod60)，x411(mod60)。,4.4同余方程求解-高次同余方程,29,定理4.49若x0是同余方程f(x)0(modp)的解，,则必是方程f(x)0(modp-1)(14)的解.,因此，必有与x0相应的方程(14)的某个解x1，使,x0=x1p-1y，,即可以从方程(14)的解中去求原方程的解。,4.4同余方程求解-高次同余方程,30,欲求同余方程f(x)0(modp)的解,先求方程f(x)0(modp)的解.,再求方程f(x)0(modp2)的解.,再求方程f(x)0(modp3)的解.,最后求方程f(x)0(modpa)的解.,4.4同余方程求解-高次同余方程,31,1.先求出方程f(x)0(modp)的解x=x1(modp),2.将x=x1+py代入f(x)0(modp2)得解y=y2(modp)得到f(x)0(modp2)解为x=x1+py2=x2(modp2),3.将x=x2+p2y代入f(x)0(modp3)得解y=y3(modp)得到f(x)0(modp3)解为x=x2+p2y3=x3(modp3),4.将x=x3+p3y代入f(x)0(modp4)得解y=y4(modp)得到f(x)0(modp4)解为x=x3+p3y4=x4(modp3),一直下去，直到最后求出f(x)0(modpa)的解.,求同余方程f(x)0(modp)的解步骤,4.4同余方程求解-高次同余方程,32,1.这时有p个解,为方便求解，现给出如下准则：,2.这时无解,3.这时有一个解,求出这个唯一解yk,则,从而，对于求解的过程第k步，有如下准则：,4.4同余方程求解-高次同余方程,33,例解同余方程,解：考虑方程,4.4同余方程求解-高次同余方程,则(2)的解可表示为：,34,代入(2)，得,将,4.4同余方程求解-高次同余方程,则(2)的解可表示为：,即(2)的解可表示为：,35,从而(1)的解可表示为：,4.4同余方程求解-高次同余方程,36,例解同余方程x33x140(mod45),解：原同余方程等价于同余方程组,x33x140(mod9)，(1)x33x140(mod5).(2),先求(1)的解：,x33x140(mod3)的解为,x2(mod3)。,令x=23t并代入方程(1)，得到,(23t)33(23t)140(mod9)，,恒成立.,于是方程(1)的解是x2，5，8(mod9).,4.4同余方程求解-高次同余方程,37,类似得到方程(2)的解为：x1，2(mod5).,xa1(mod9)，a1=2，5，8，xa2(mod5)，a2=1，2.,因此，原同余方程的解是下面六个同余方程组的解：,利用孙子定理解这六个方程组.,4.4同余方程求解-高次同余方程,记m1=9，m2=5，m=45，M1=5，M2=9，,38,将a1和a2的不同取值代入，得到所求的解是,x11029111(mod45),x2102922(mod45)，x31059141(mod45),x41059232(mod45)，x51089126(mod45),x61089217(mod45),4.4同余方程求解-高次同余方程,39,习题1：解同余式组,习题2：解同余式组,4.4同余方程求解-高次同余方程,
展开阅读全文