第二章 同余 信安数学.ppt

总结 还需知道 孙子定理的最大价值不在于直接解同余方程组 而在于大模的一个同余式化为小模的、模互质的同余方程组 然后利用欧拉定理、费马小定理将式子化简 通过解同余方程组来提高解原来同余式的速度 特别是存在大指数的情况更有效 法一：1012=127*8-4 127=4*32-1 所以 （127，1012）=1，有解 1=4*32-127 1=(127*8-1012)*32-127=127*255-1012*32 所以127*255 ≡1(mod 1012) 所以两边同乘以255 255*127x ≡255*833(mod 1012) ≡907(mod 1012) 练习 解 127x≡833(mod 1012) 1012=4*11*23，所以化为方程组 127x≡833(mod 4) 化简为：x≡-1(mod 4) 127x≡833(mod 11) 化简为：6x≡-3(mod 11)= x≡5(mod 11) 127x≡833(mod 23) 化简为：12x≡5(mod 23)= x≡10(mod 23) 对于第一个：M1=11*23=253 因为253≡1(mod 4),M1’=1 对于第二个：M2=4*23=92 因为92≡4(mod 11),M2’=3 对于第三个：M3=4*11=44 因为44≡-2(mod 23)，M3’=11 求和：x≡1*(-1)*1+4*5*3+(-2)*10*11 错误！！ 应该：x≡253*(-1)*1+92*5*3+44*10*11 ≡-253+1380+4840≡5967≡907 (mod 1012) 练习 解 127x≡833(mod 1012) 最后的模应大于47*87，也就是大概为50*90=4500 首先要找到各方程式的模，考虑47是个素数，87=3*29 所以可以采用一个模为29，这样，一个同余式中会出现0方便计算，而不采用3是因为它与4500相差太远 还需要150才能实现4500,150=15*10，所以考虑11和17 建立方程组： xy≡47*87≡0 (mod 29) xy≡47*87≡-3 (mod 11) xy≡47*87≡-4*2≡9 (mod 17) 练习 X=47,y=87,利用孙子定理计算x*y 对于方程组： xy≡0 (mod 29) xy≡-3 (mod 11) xy≡9 (mod 17) 最后的模：5423 对于第一个：0 对于第二个：M2=29*17=493,因为493≡-2(mod 11),所以M2’=5 对于第三个：M3=29*11=319,因为319≡-4(mod 17),所以M2’=4 求和：xy≡0+493*(-3)*5+319*9*4(mod 5423)≡4089 所以xy=4089 练习 X=47,y=87,利用孙子定理计算x*y 检验：你会吗？ 熟练的写出： 给出模写出同余的两个数 缩系和完系 欧拉函数 熟练的计算 同余与整除的转换 同余式的可行的加、减、乘、除计算 同余式的化简：系数、底数、指数 同余式与同余方程组的转化 解方程 * ? 2003-2004 Microsoft Corporation. All rights reserved. This presentation is for informational purposes only. Microsoft makes no warranties, express or implied, in this summary. * * ? 2003-2004 Microsoft Corporation. All rights reserved. This presentation is for informational purposes only. Microsoft makes no warranties, express or implied, in this summary. * m|a-b的证明 证明 设a?b(mod m), 则a=mq1+r, b=mq2+r, 0≤rm. 故(a-b)=m(q1-q2), m|(a-b). 反之, 设a=mq1+r1, b=mq2+r2, 0r1≤m, 0r2≤m, m|(a-b).于是, m|(a-b)=m(ql-q2)+(rl-r2), 故: m|(r1-r2). 又因|r1-r2|m, 得r1=r2. * ? 2003-2004 Microsoft Corporation. All rights reserved. This presentation is for inform