第四章 同余式-基本概念、一次同余式、 孙子定理,0,1,2, -1.),(,mmaaammam 定定义义是是定定义义在在正正整整数数上上的的函函数数 它它在在正正整整数数 上上值值等等于于序序列列 中中与与 互互质质的的数数的的个个数数定定义义 如如果果一一个个模模的的剩剩余余类类里里面面的的数数与与互互质质 就就把把它它叫叫做做在在与与模模互互质质的的全全部部剩剩余余类类中中 从从每每一一类类各各任任取取一一数数所所作作成成的的数数的的集集合合 叫叫做做一一个个模模互互质质的的剩剩余余类类模模的的一一个个简简拉拉函函数数化化剩剩余余系系欧欧复习复习1( ),( ).mmmmmmmmm定定理理模模的的剩剩余余类类与与模模互互质质的的充充分分必必要要条条件件是是此此类类中中有有一一数数与与互互质质. .因因此此与与模模互互质质的的剩剩余余类类的的个个数数是是模模的的每每一一简简化化剩剩余余系系是是由由与与互互质质的的个个模模不不同同余余的的整整数数组组成成的的12()12()2 ,( ),mma aammma aam定定理理若若是是与与互互质质的的整整数数, ,并并且且两两两两对对模模不不同同余余, ,则则是是模模的的一一个个简简化化剩剩余余系系. . 1212122 112123 ( ,)1,.4 ,a mxmaxmm mx xm mm xm xmm定定理理若若通通过过模模的的简简化化剩剩余余系系, ,则则通通过过模模的的简简化化剩剩余余系系定定理理若若是是两两个个互互质质的的正正整整数数, ,分分别别通通过过模模的的简简化化剩剩余余系系则则+ +通通过过模模的的简简化化剩剩余余系系. .121212121212()()().5 111( )(1)(1)(1).k kkm mmmmmap ppaappp推推论论若若, ,是是两两个个互互质质的的正正整整数数, ,则则定定理理设设, ,则则(12()12()1()1 2()() 1)2)(1(, ,33,)(,1( uler()1,)1,mmmmmm mmEma mar rrmar ararmararrrrmarrrrmrm 证证 设设是是模模的的简简化化剩剩余余系系, ,则则由由定定理理也也是是模模的的简简化化剩剩余余系系, ,故故() (mod ) () (mod )即即) ) 定定理理设设是是大大于于 的的整整数数,( ,(则则1(mo1(mo(mo (mod )d )d d . .) )12()1 2()(),)( ,)(,)1,)1.1mmmr mr mrmrrrmam但但( (因因此此( (由由性性质质己己, ,即即得得 1(mod ). 1(mod ).4 4 欧拉定理欧拉定理. .费马定理及应用费马定理及应用1, )1,135(Fe,(mormad).t, )1,)ppppa papaappa pp aaapaap. .证证 若若( (由由定定理理 及及定定理理推推论论定定理理 若若 是是素素数数 则则即即得得1 (mod 1 (mod ) )因因而而 若若( (则则故故(m(m(mo (moododd)d). .) )1212+1+1+20.,(0,1,9,0)0,0,1,2, ;0,1,2,.,0.,.,nns is kt isss tssa aaastaait ka aa aastaa定定义义 如如果果对对于于一一个个有有限限小小数数是是之之中中的的一一个个数数码码 并并且且从从任任何何一一位位以以后后不不全全为为是是能能找找到到两两个个整整数数使使得得我我们们就就称称它它为为循循环环小小数数 并并简简单单把把它它记记作作对对于于循循环环小小数数而而言言 具具有有上上述述性性质质的的 及及 是是不不只只一一个个的的 如如果果找找到到的的是是最最小小的的 我我们们就就称称+,;0,.s tats 为为循循环环节节称称为为循循环环节节的的长长度度 若若最最小小的的, ,那那小小数数就就叫叫做做纯纯循循环环小小数数 否否则则叫叫混混循循环环小小数数公钥密码体制公钥密码体制9算法描述密钥产生算法描述密钥产生独立地选取两大素数独立地选取两大素数p p和和q q( (各各100100200200位十进制数字位十进制数字) )计算计算n n=p pq q，其欧拉函数值其欧拉函数值 ( (n n)=()=(p p1 1)( )(q q1 1) )随机选一整数随机选一整数e e，1 1 e e ( (n n) )，gcd(gcd( ( (n n), ),e e)=)=1 1在模在模 ( (n n) )下下，计算计算e e的有逆元的有逆元d=ed=e- -1 1modmod ( (n n) )以以n n，e e为公钥为公钥。秘密钥为秘密钥为d d。( (p p, ,q q不再需要不再需要，可以销毁可以销毁。) )加密加密将明文分组将明文分组，各组对应的十进制数小于各组对应的十进制数小于n nc=memod n解密解密m=cdmod n10解密正确性证明解密正确性证明 cdmod n medmod n m1 mod(n) mod n mk(n)+1 mod ngcd(m,n) =1 m(n)1 mod n欧拉定理欧拉定理 mk(n)1 mod n mk(n)+1m mod ngcd(m,n) 1 m是是p的倍数或的倍数或q的倍数的倍数， 设设m=cp，gcd(m,q)=1, m(q)1 mod q， mk(q)1 mod q， mk(q) (p)1 mod q mk(n)1 mod q，存在一整数存在一整数r，使mk(n)1rq 两边同乘两边同乘m=cp, mk(n)+1m+rcpq=m+rcn, 即即mk(n)+1m mod n11RSA算法实现算法实现如何判定一个给定的大整数是素数？如何判定一个给定的大整数是素数？已知已知d d如何计算如何计算e e，使，使e * d1 mod(n)e * d1 mod(n)？如何计算如何计算C MC Me emod nmod n或或MCMCd dmod nmod n？12第四章基本内容第四章基本内容同余式的概念一次同余式概念及求解孙子定理：求解同余方程组高次同余式的解数及解法质数模的同余式1 基本概念及一次同余式基本概念及一次同余式10( )( ),;,( )0(mod)(1)0(mod),.12,( )0(mod),( )0(mod).n ninaf xf xa xa xaamf xmamnf amKaf amm定定义义 若若表表示示多多项项式式 + +其其中中是是整整数数 又又设设是是一一正正整整数数 则则. .若若则则 叫叫做做(1)(1)的的次次数数由由第第三三章章定定理理若若 则则剩剩余余类类中中任任何何叫叫做做模模的的同同余余式式整整数数都都能能使使 成成立立( )0(mod),(mod)( )0(mod).( )0(mod)( )0(mod).af amxamf xmf xmmf xm定定义义 若若 是是使使 成成立立的的一一个个整整数数则则叫叫做做的的一一这这就就是是说说我我们们把把适适合合而而对对模模互互相相同同余余的的一一切切数数算算作作的的一一个个解解解解1212mod11(mod).mod,mod,mod11cmxcmcmc cmcm cmm同同余余式式解解的的定定义义同同余余类类 中中的的任任一一整整数数也也是是( )( )的的解解, ,这这些些解解都都应应看看作作是是相相同同的的, ,把把它它们们的的全全体体算算作作是是( )( )式式的的一一个个解解, ,并并把把这这个个解解记记为为这这实实际际上上是是把把同同余余类类 看看作作是是满满足足(1)(1)的的一一个个解解. .当当均均为为同同余余式式的的解解, ,且且对对模模不不同同余余( (即即是是不不同同的的同同余余类类) )时时才才看看成成是是( )( )的的不不同同的的解解. .我我们们把把所所有有对对模模两两两两不不同同余余的的( )( )的的解解的的个个数数( (即即满满足足( (11.mmmmm( )( )的的解解数数我我们们只只要要在在模模的的一一) )的的模模的的组组完完全全剩剩余余系系中中来来解解模模的的同同同同余余类类的的个个数数) )称称为为是是. .因因此此. .显显然然, ,余余式式模模的的同同余余式式的的解解数数至至多多为为2427 -120(mod 15)6,36,3(mod15),2.xxxx 例例1 1 求求同同余余方方程程 的的解解. .解解 取取模模1515的的绝绝对对最最小小完完全全剩剩余余系系:-7,-6,:-7,-6,-1,0,1,2,7,-1,0,1,2,7,直直接接计计算算知知 是是解解. .所所以以, ,这这个个同同余余方方程程的的解解是是解解数数为为 2257427 -70(mod 15)7, 2, 1,4(mod15),.427 -90(mod 15)0(mod 5)5;0(mod 7)xxxxxxxxxx 例例2 2 求求同同余余式式 的的解解. .解解 同同样样直直接接计计算算知知 -7,-2,-1,4 -7,-2,-1,4 是是解解. .所所以以, ,它它的的解解是是解解数数为为 4 4例例3 3 求求同同余余式式 的的解解. .直直接接计计算算, ,这这个个方方程程无无解解. .例例4 4 由由Fermat-EulerFermat-Euler定定理理知知, ,同同余余式式的的解解数数为为同同余余式式的的解解数数0(mod7).ppxxpp一一般般地地, ,对对素素数数 , ,同同余余方方程程的的解解数数为为为为(mod),0(mod)(2),)(2)(2)()( ,).axbmama mbmda m定定理理 一一次次同同余余式式 有有解解的的充充要要条条件件是是(.(.若若有有解解, ,则则的的解解数数 对对模模来来说说 是是|1010101-.2(2)( ,) .( ,).(2)12 ,0, 1, 2,.(mod),0,1,1.,ax myba m bda mmxmtx mtdmxxkmm kdxkm证证 (2) (2)有有解解的的充充要要条条件件是是 有有解解 从从而而由由第第二二章章 1 1定定理理 即即知知有有解解充充要要条条件件是是设设若若有有解解, ,则则由由第第二二章章 1 1定定理理 知知适适合合( )( )式式的的一一切切整整数数可可以以表表成成此此式式对对模模来来说说, ,可可以以写写成成但但0,1,1 .(2)kdmd是是对对模模两两两两不不同同余余的的故故有有个个解解. .- (4)(2)ax mybx由由定定理理的的证证明明可可以以看看出出, ,适适合合(2)(2)式式的的整整数数也也就就是是适适合合不不定定方方程程 的的解解答答中中 的的值值, ,故故同同余余式式可可以以用用解解不不定定方方程程(4)(4)的的方方法法去去解解它它. .1111111111-/ 2/ 2;-/ 2/ 2;(mod)55 ). (6)5aammambbmmbmaxbma xbmmybaa xmyb (i)