第2周_密码学中的数学基础知识.pptVIP

密码学中的数学知识 因子 若b|a,则称b为a的因数 若a=kb,而b既非a又非1,则称b是a的真因数. 例如 12的因子：1，2，3，4，6，12 12的真因子：2，3，4，6 整除实例 Q: 下面哪个是对的? 77 | 7 7 | 77 24 | 24 0 | 24 24 | 0 实例 Q: 1. 找出60的所有因子 2. 列出80的所有真因子 模运算 设n是正整数，a是整数，如果用n去除a，得商为q，余数为r，则可以表示为： a=qn+r,0≤rn, 用a mod n表示余数r，则r≡a mod n. 例如：令a=17, n=5,则17=3×5 +2, r =2≡17mod5 模运算典型实例 时钟模12的运算 同余 设n是正整数，a, b是整数，如果a mod n≡b mod n，则称整数a和b模n同余，记为a≡b mod n。 显然，a≡b mod n，则n|(a-b). 例如：a=17, b=-8, n=5, 因为17=3×5 +2, -8 =-2×5 +2, 则17 mod 5≡-8 mod 5，通常记为：17≡-8 mod 5. 同余式实例 Q: 下面哪个是真的? 3 ? 3 (mod 17) 3 ? -3 (mod 17) 172 ? 177 (mod 5) -13 ? 13 (mod 26) 同余式实例 A: 3 ? 3 (mod 17) True. (3-3 = 0, divisible by all) 3 ? -3 (mod 17) False. (3-(-3)) = 6 不能整除 17. 172 ? 177 (mod 5) True. 172-177 = -5 能整除 5 -13 ? 13 (mod 26) True: -13-13 = -26 能整除by 26. 同余的基本性质 ① [(a mod n)+(b mod n)]mod n=(a+b)mod n ② [(a mod n)-(b mod n)]mod n=(a-b)mod n ③ [(a mod n)×(b mod n)]mod n=(a×b)mod n 同余的基本性质 例 11 mod 8=3; 15 mod 8=7 ① [(11mod 8)+(15 mod 8)]mod 8=(3+7)mod 8 =2 =(11+15) mod 8=26 mod 8=2 ② [(11 mod 8)×(15 mod 8)]mod 8 =(3×7)mod 8 =21 mod 8=5 (11×15）mod 8＝165 mod 8＝5 同余性质 1. 若a?b(mod m), c?d(mod m), 则: ① ax+cy ? bx+dy(mod m), 其中x和y为任给整数. ② ac ? bd(mod m). ③ an ? bn(mod m), 其中 n＞0. 上面的性质容易证明，以②为例： 设a=b+q1m,c=d+q2m ac=( b+q1m)( d+q2m)=bd+(bq2+dq1+q1q2)m, 等式两边同时模m可证。 同余性质 2. 设m是一个正整数， ① ad≡bd(mod m), 如果(d, m)=1, 则a≡b(mod m) ② a≡b(mod m), k0, 则ak≡bk(mod mk) ③ a≡b(mod m), 如果d是m的因子，则a≡ b(mod d) 下面对①③进行证明。 同余性质 ① 证明：若ad≡bd(mod m), 则m|(ad-bd), 即m|d(a-b). 因(d, m)=1，故m|(a-b), 即a=b(mod m) ③ 证明：d是m的因子，故存在m’, 使得m=dm’. 因为a≡b(mod m), 存在k, 使得a=b+mk= b+ dm’k. 等式两边模d, 可得a≡b(mod d). 最大公因数 设a, b是整数，则a, b的所有公因数中最大的一个公因数叫做最大公因数，通常记为gcd(a,b)。 例如12和-18的最大公因数为6，记为gcd(12,-18) =6 gcd(513,614)=？ gcd(1024,888)=？ 如果两个整数的绝对值都比较小，求它们的最大公因数是比较容易的。如果两个数都比较大，可以用广义欧几里德除法，也称辗转相除法。 一个关于同余的性质 对任何非负整数a和非负整数b，设a≥b, a=bq+r, 0≤r|b|, 则gcd（a, b ）=gcd(b, r). 证明：设gcd（a, b）=d, 则d|a, d|b, 则d|a-bq即d|r. 同理，设gcd(b, r)=k, 则k|b, k|r, 则k|bq+r, 即k|a. 所以，结论成立。 例如，96=28×3+12，故gcd(96,28)=gcd(28,12)=4