1、第二讲 数论与代数知识初步(上)现代密码系统中，消息都是事先转换成数值进行加密传输。密码过程是一些输入输出都是数值的数学操作，建立，分析，攻击这些算法需要数学工具。其中在实践中应用最为成功的数学理论当然是数论和代数，特别是同余理论。本讲提要q 基本概念q 同余1 基本概念基本概念。，记不整除不存在，我们如果这。的倍数，记做 的因数，做，我们使得，如果存在一个整数整除。我们，0对于整数 b|abaka|babbab=kakbaba为说个为叫叫把说 定义1定义11.1 整除性。即，所以，由定义可写出。，所以有，满足由定义存在显而易见。是任意整数。和，这里，则，如果。，则，如果。，对于任意，对于任意
2、tca|sbatksktcsbakcakbklaclbckablktstcsbaa|ca|bcacba|b|bba|aa|a )(3)(和(2)1()(|(3)|)2(10 0)1(2121证明.证明.性质1性质11.1 整除性(续)。0 0，成立，使得及个唯一的整数，则存在两是两个整数，其中设brrbq arqbba定理1定理11.2 素数的素数。存在无穷多个形如矛盾。数的个数是有限的假设其它素数，因此，与素然存在之中任意一个整除，必，不可为而，知其必为合数，是全体素数。再令，的可令如果素数的个数是有限素数的个数是无穷的。否则就叫做合数。它本身，就叫做素数，和因数只有的正整数，如果它的正一个
3、大于14 1 3211 212121npppppppppppkkk 定定理理3 3证证明明.定定理理2 22 2 定定义义1.2 素数(续)200以内的素数：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 都表示素数。的整数时，取所有使得，式，不存在整系数多项对于任意给定整数)()0,0()(001110 xfxxnaaxaxaxaxf
4、xnnnnn 定定理理4 4。时，比率，也就是说当的所有素数，则有表示小于如果素数数量定理1)ln()(ln)()()(xx/xxxxxxx 定理5定理5因此，足够使用。，我们可以估计通过位左右的十进制素数要求使用在各种密码应用中经常97999910010099100109.310ln1010ln10)10()10(,100定理5定理51.2 素数(续)1.3 最大公约数。，是整数，则其中，整数，且是任意三个不全为零的，设互素。，就说，若，公因数，记作叫最大的公因数中最大的一个，公因数。整数的一个，就叫，那么它们之中每一个的因数是整数个不全为零的整数。若是，设)()(1)()(21212121
5、2121cbbaqcbqacbaaaaaaaaaaaaaaaaddnaaannnnnn 定理6定理6定义3定义3。，即一个不等于零的余数，就是上述过程中最后，则，任意。，有，不失一般性假定任意算法的表述nnnnnnnnnnnnnnnnnnrbababarrqrrrrrqrrrrrqrrrrrqrrrrrqrbbrrbqaba)()(00 0 0 0 0 0 0 00Euclidean111111221112323332112221111定定理理7 71.3 最大公约数(续)1.3 最大公约数(续)忽略的过程。被除数除数：剩余可以看到余数都经历了。，因此，。，计算21180)(482028162
6、1635016504216051622482216482211801180)(482 例例子子1 1。，使得，则存在两个整数，若任给整数nbmabanmba)(00 定理8定理81.3 最大公约数(续)算法。这一过程被称为扩展。，所以同样有。，因此，。，则，我们可以得到递推公式的证明根据Euclidean)1180 482(2)29(118071482297132245221)(11:,534523412321212121121221yxxxxxxxxxxxbabyaxyyqyqqyqyxxqxqxxnnjjjjjjjj定定理理7 71.3 最大公约数(续)。，使得，个正整数，则存在整数是，若
7、。，个正整数，则是，若，那么有下面的定理。，设。，则，若)()2()()2()()()(0002|1)(|21221121212121133222121nnnnnnnnnnnnaaaxaxaxaxxxnnaaadaaannaaadaddaddaaaaancababca 定理11定理11定理10定理10定理9定理91.4 最小公倍数。，的所有倍数。，的所有公倍数就是，是任意的两个整数，则，设。，记作整数叫做最小公倍数，的一切公倍数中最小的，个数的一个公倍数。在就叫这每一个的倍数，那么个数中是这个整数。若是，设)()2(1)2(212121baabbabababaaaaaaanmnmnaaannn
8、 定理12定理12 定义4定义41.4 最小公倍数(续)。，个正整数，则是，若，那么有下面的定理。，设nnnnnnnmaaannaaamammammaaaaan )2(00022121133222121定理13定理131.4 整数唯一分解定理。或，则是素数，若。，或是任一整数，则有是一素数，若。是合数时，是素数，并且当正因数以外的最小的除的整数，则是任一大于设bpapp|abpapapapaqaqaa|1)(|11 引理3引理3引理2引理2引理1引理1。，以此类推，最后可得，可以得。进一步，由，因此，和。同时有，为素数，所以，由于，可知，由引理知和证明唯一性。由其次成立。故也能表示为素数乘积，
9、因此都能表示为素数乘积，和可知则必有分解如果为合数如果为素数显然成立，的正整数都成立，考虑且小于显然成立，假定一时成立，数学归纳法，当首先证明证明：。，都是素数，则，其中，并且若都是素数，其中，有即对于整数的乘积数的正整数都能分解成素任何大于整数唯一分解定理mnmnkjkjkjmniimmmnnnqpnmqpqqppqppqqppqqppqpqqpqqqpppacbacbbcaaaanipqnmqqqqqqqqqapppppppppaa222211111111112121212121212121|3)2()1(,)1(,1,)1(2(1)21(2),(1)1,1)(定定理理1 14 41.4
10、整数唯一分解定理(续)1.4 整数唯一分解定理(续)。，即，所以，由于。，且和因此，对于是素数。，其中，的整数能够唯一写成意大于算术基本定理说明，任)()()min()max()()1(0)1(000)()1(01),max(),max(2),max(1),min(),min(2),min(121212122112211212121baabbababaabyxyxyxpppbapppbakipppbkipppabajippkipppakkkkkkkkkikikjiik1.5 一次不定方程为任意整数。的一组解，为，其中，的全部解可表示为，则，设。，件是有整数解的充分必要条方程。是给定的整数，其中
11、，二元一次不定方程是指tyxtayytaxxaanaaaanaanyaxa)3(3)|)()3(03)(0010202121212121 1 1)(定理16定理16定理15定理152 同余同余式。为任意给定整系数多项，；为任意整数；，其中则有，如果。同余的充分必要条件是对模，整数。，传递性；，则对称性；自反性。就不同余，记为对，如果余数不同，同余，记为对，余数相同，我们就说所得的和去除两个整数，如果用给定正整数)()(mod()()4()(mod)3()(mod)2()(mod)1(),(mod)(mod|)(mod)(mod)(mod(3)(mod)(mod )2()(mod)(mod)(m
12、od xfmbfafmbambayxmybxyaxmmbabammbamcamcbmbamabmbamaambambambambabammnn (1 1)定定理理1 18 8定定理理1 17 7性性质质2 2定定义义5 52.1 同余定义与概念2.1 同余定义与概念(续)。，则，若。，则，且若如果)(mod21)(mod mod )()(mod 21nimmmbanimbadmbadcmmbcac 定定理理2 20 0定定理理1 19 92.2 剩余类和完全剩余类的非负最小完全剩余。，称为模，常用的完全剩余系不同余。两对模的完系的充要条件为两个整数成为模由定义立即得到：的一组完全剩余系。称为模
13、，个数，此，中各取一个数，的剩余类在模。条件是属于同一类的充分必要，两个整数；中，这里个剩余类每个整数都包含在某一剩余类，则有是模，设的剩余类。做模叫，则，中的整数组成的集合，其表示所有形如，是一个给定整数，设mmmmmmaaammjCaCCCmmyxyxmjCmCCCmmCCCqrqmmrCmmjjmjmmr110#110)(mod )2(10)1(0 10)110(110110110110定理22定理22定义7定义7定义6定义6 定理21定理212.2 剩余类和完全剩余类(续）的完系。通过模的完系，则，分别通过模，而，设的一组完系。也是模，则的一组完系是模，而，设2121122121212
14、11101101)(00 1)(mmxmxmmmxxmmmmmkakakamaaamkmm定定理理2 24 4定定理理2 23 32.3 缩系的缩系。也是模的缩系则是通过模，若不同余。两模系的充要条件为它们两为缩，互素的整数，则个与是，若个数。的一组缩系含有模。是素数时互素的数的个数。显然中与，的值为序列函数，是一个定义在整数上的欧拉函数的一组缩系。组成的集叫模各取一个数互素的剩余类，在其中，就把它叫做一个与模互素显然一个互素全部互素的剩余类里的数与如果一个模maxmxmamaammaammpppnnnnmmmmmm1)()()(1)(110)()()()(1)(1 定定义义8 8定定理理2
15、27 7定定理理2 26 6定定理理2 25 5定定义义9 92.3 缩系(续)mod()mod1(1)(1 )(。是素数，则若费马小定理立刻可得：由。，则，设欧拉定理paapmamampm )()(定定理理2 29 9定定理理2 28 8定定理理2 28 82.3 缩系(续)。，则的标准分解设。，则，若立得由的缩系。通过模的缩系，则，分别通过模，而，设kkpppnnpppnnmmmmmmmmxmxmmmxxmmmmk111111)()()()(1)(1)(0021212121212121122121212121 定定理理3 30 0 定定理理3 31 1推推论论1 1定定理理3 30 02.
16、4 一次同余式。的逆元，记为称为的解。特别地，我们将是恰有一个解，这个解就，则同余式，设互不同余的解。解是指叫同余式的解。不同的，则满足叫次数。如果，则的同余式。若叫模，则是整数，又设，其中设11)(1)(0000111)(mod1)(mod)(mod 0)(mod)(mod0)()(mod0)(mod0)(0)10(0)(aaamaxmbaxmbaxmmamxxmxfxnmammxfmnianaxaxaxaxfmmninnnn1 1)(定定理理3 32 2定定义义1 10 02.4 一次同余式(续)个解。有，则同余式，设。有解的充分必要条件是，则同余式，设dmbaxbdmdmabdmbaxm
17、dma)(mod|0|)(mod 0)()(定定理理3 34 4定定理理3 33 32.5 模是素数的同余式个解。最多有则同余式，是一个整系数多项式，是素数，设定理npxfpanaxaxaxaxfpnnnnn)(mod0)()(mod00)(0111 )(L La ag gr ra an ng ge e定定理理3 35 52.6 中国剩余定理(CRT)。，其中，有唯一解，则同余式组，个两两互素的正整数，是，设过程是可逆的。中国剩余定理揭示这一)1)(mod1 )(mod )(mod)(mod)(mod)1()7(mod2)5(mod3)3(mod2)105(mod2322211122112121kimMMmbMMbMMbMMxmbxmbxmbxkiMmmmmmmkmmmxxxxiiikkkkkiikk定理36定理362.6 中国剩余定理(CRT)(续)。为所以解由于。解有唯一解。，对模可解时，且当，可解的充分必要条件是，一次同余式组)105(mod80),15(mod5)15(mod80),7(mod3)7(mod80)15(mod5),7(mod3)4(|)(4)(mod)(mod 2121212211xxxmmbbmmmbxmbx 例子2例子2 定理37定理37谢谢！
