[工学]加密算法.ppt

现代密码学理论与实践-08 Cryptography and Network Security Chapter 8 Introduction to Number Theory Fourth Edition by William Stallings Lecture Slides by 杨寿保 syang@ 1/~syang September 2009 Chapter 8 – Introduction to Number Theory The Devil said to Daniel Webster: Set me a task I cant carry out, and Ill give you anything in the world you ask for. Daniel Webster: Fair enough. Prove that for n greater than 2, the equation an + bn = cn has no non-trivial solution in the integers. They agreed on a three-day period for the labor, and the Devil disappeared. At the end of three days, the Devil presented himself, haggard, jumpy, biting his lip. Daniel Webster said to him, Well, how did you do at my task? Did you prove the theorem? Eh? No . . . no, I havent proved it. Then I can have whatever I ask for? Money? The Presidency? What? Oh, that—of course. But listen! If we could just prove the following two lemmas— —The Mathematical Magpie, Clifton Fadiman 本章要点 素数是一种整数，在整除意义下，它只能被自身(正负)和1整除。素数在数论和密码学里扮演重要角色。 在公钥密码里起重要作用的两个定理是费马定理和欧拉定理。 许多密码算法的一个重要前提是能够选择一个大的素数。开发有效算法判定一个随机整数是否为素数是密码研究重要课题。 离散对数是许多公钥算法的基础。离散对数和普通对数类似，但是在模算术上进行运算。 8.1 素数Prime Numbers 素数的因子是1和其自身 不能写作其他数的乘积形式 1是素数，但是通常没有什么作用 如，2,3,5,7是素数, 4,6,8,9,10不是 素数是数论的核心 小于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 小于2000的素数 合数的素因子分解 分解一个数n就是把它写成其他数的乘积形式，如 n=a × b × c 比起用乘的方法把几个因子乘起来生成合数，分解合数通常要困难得多。 任何整数a1，可以分解为a= p1a1p2a2…ptat , 其中， p1p2…pt 是素数，每一个ai是正整数，如 91=7x13; 11011=7x112x13 素因子分解就是把一个合数写成若干素数的乘积形式，如3600=24x32x52 合数的素因子分解 任一给定的正整数，可通过简单列出所有后面公式中非零指数分量来说明 Ex：12可以表示为{a2=2, a3=1}，18可以表示为{a2=1, a3=2}， 91可以表示为{a7=1, a13=1} 两个数的乘法等同于对应指数分量的加法： k=mn →kp=mp + np 对所有p Ex：k=12x18=(22x3)x(2x32)=216, k2=2+1=3, k3=1+2=3 216=23x33 如果任何以pk形式表示的整数仅能被对应素数分量小于或等于它的另一个整数pj整除，其中j≤k， 因此有a|b →ap≤bp 对所有p Ex：a=12, b=36, 12|36, 12=22x31, 36=22x32 a2=2=b2, a3=1≤2=b3 互素和最大公约数GCD gcd(a, b)=c, 即c是a和b