下载文档原格式
第三章 数学基础近代密码学用到数学之多，遍及许多数学分支，如概率统计、信息论、数论、有限域理论、复杂性理论，甚至于代数、几何等都在近代密码学中扮演重要角色。
所以，数学是近代密码学不可或缺的工具。
3.1 数论3.1.1 数的m 进制表示1. 十进制表示十进制是最方便的一种整数表示法。
例： 7108109101198723+∙+∙+∙=110210710310553721234+∙+∙+∙+∙=2. m 进制表示实际上，使用任何进制表示一个数都是可以的。
定理 设m 是大于的正整数，则每一个正整数n 可唯一地表示为0111c m c m c m c n k k k k ++++=--其中),,2,1,0(k j c j =是整数，且0,0≠<≤k j c m c 。
记作：m k k c c c c n )(011 -=。
3. m 进制表示的具体做法将一个正整数n 表示成m 进制时，主要是要确定k k c c c c ，，，，110- 。
若用⎥⎦⎥⎢⎣⎢m n 表示n 除以m 后，取其整数部分（也就是比m n 小的最大整数），确定k k c c c c ，，，，110- 的方法如下：1. 令01c r =，n n =0，则有1221101c m c m c m c m n n k k k k ++++=⎥⎦⎥⎢⎣⎢=---2. 令12c r =，则有2331212c m c m c m c m n n k k k k ++++=⎥⎦⎥⎢⎣⎢=---3. 令23c r =， ……4. 若m n i >，令 ,2,1,0,1==+i c r i i122111++-----+++++=⎥⎦⎥⎢⎣⎢=i i i k k i k k i i c m c m c m c m n n5. 直到110++==⎥⎦⎥⎢⎣⎢=k k k k r c m n n ， 即m n k <为止。
4. 举例例 5389==m n ， 解 令 3890==n n则有34342323121201013 0 5350 3 55152 15577547753895c r n n c r n n c r n n c r n n ===⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢====⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢====⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢====⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢=，，，，故5123)4203(4525053389=+∙+∙+∙=例 2389==m n ， 解 令 3890==n n⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦1 12121 12320 32620 621220 1222420 42 24821 84 29720 97219421 19423892889778667556445334223112001====================================c n n c n n c n n c n n c n n c n n c n n c n n c n n ，，，，，，，，， 故2278)101000011(1222389=+++=第六次课截止于此3.1.2 数的因数分解素数 只能被1和其自身除尽的正整数称为素数（1,2,3,5,7, 11,13,17,…）。
