文档介绍：1 1密码学中的数学知识 2 2 因子若 b|a, 则称 b为a的因数若 a=kb, 而b既非 a又非 1,则称 b是a的真因数. 例如 12的因子: 1,2,3,4,6,12 12的真因子: 2,3,4,6 3 3 整除实例 Q: 下面哪个是对的? 77 | 7 7 | 77 24 | 24 0 | 24 24 | 0 4 4 实例 Q: 1. 找出 60 的所有因子 2. 列出 80 的所有真因子 5 5 模运算设n是正整数, a是整数,如果用 n去除 a,得商为q,余数为 r,则可以表示为: a=qn+r,0 ≤ r<n, 用 a mod n 表示余数 r,则 r≡ a mod n. 例如:令 a=17, n=5, 则 17=3 × 5 +2, r =2 ≡ 17mod5 6 6 模运算典型实例时钟模 12的运算 7 7 同余设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. 8 8 同余式实例 Q: 下面哪个是真的? 3 ? 3 (mod 17) 3 ? -3 (mod 17) 172 ? 177 (mod 5) -13 ? 13 (mod 26) 9 9 同余式实例 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. 10 10 同余的基本性质① [(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