北交大-密码学课件-第8章-数论入门.pptVIP

* * Fermat大定理 x^n+y^n=z^n 1993 A. Wiles证明 Fermat 行为怪癖的法学家 业余数学家 * * 20，8 * * 产生一个n位随机数，然后判断是否素数 试除法：复杂度为sqrt(n)，不行 筛法：依次去除2、3、5、7等的倍数 其他算法：概率判定算法 * 产生一个n位随机数，然后判断是否素数 试除法：复杂度为sqrt(n)，不行 筛法：依次去除2、3、5、7等的倍数 其他算法：概率判定算法 素数的分布是无限的 * * * * 韩信点兵 有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人；成十一行纵队，则末行十人，求兵数。 * * * * * * * * * * * * * * * * 单击此处编辑母版标题样式 单击此处编辑母版副标题样式 第8章 数论入门 本章内容 素数 模运算 Euclid算法 费马定理和欧拉定理 素性测试 中国剩余定理 离散对数 费尔马定理和欧拉定理 费尔马（Fermat）定理： 若p是素数，a是正整数且gcd(a, p)=1，则ap-1≡1 mod p。 证明：考虑集合{1,2,…,p-1},对每个数乘以a,得到集合 {a mod p,2a mod p,…,(p-1)a mod p}, 两两不同且都在 1与p-1之间,因此两个集合相同: {a mod p, 2a mod p,…, (p-1)a mod p}={1,2,…,p-1} 所以 ：(p-1)! mod p = 1×2×…×(p-1) ≡a×2a×…×(p-1)a ≡[(a mod p)×(2a mod p)×…×((p-1)a mod p)] mod p ≡[(p-1)!ap-1 ] mod p 由于(p-1)!与p互素，因此(p-1)!有乘法逆元，由乘法可约律得ap-1≡1 mod 推论：设p是素数，a是任一正整数，则ap ≡ a mod p 欧拉函数 设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n)。? 例如： φ(6)=2 ，φ(7)=6 ，φ(8)=4。 若n是素数，则显然有φ(n)=n-1。 定理：若n是两个素数p和q的乘积，则 φ(n)=φ(p)×φ(q)=(p-1)×(q-1) ? 例如： 由21=3×7，得φ(21)=φ(3)×φ(7)=2×6=12 回顾欧拉函数的求值公式 费尔马定理和欧拉定理 欧拉（Euler）定理：若a和n互素，则a φ(n) ≡1 (mod n)； 证明: R={x1,x2,…,xφ(n)}为所有小于n且与n互素的正整数,考虑集合: S={(ax1 mod n), (ax2 mod n),…, (axφ(n) mod n)} ① (axi mod n)与n互素 ② (axi mod n)两两不等: (axi mod n) = (axj mod n) ? xi mod n = xj mod n ③ S有φ(n)个元素 故S也是所有小于n且与n互素的正整数,因此S=R,从而： Πxi=Π(axi mod n)≡(Π(axi)) mod n ≡ (aφ(n) Πxi) mod n 注意到xi 与n互素,从而得到结论. 欧拉（Euler）定理推论： a φ(n)+1 ≡a (mod n) 若n=pq, p≠q都是素数, k是任意整数,则： mk(p-1)(q-1)+1 ≡ m mod n, 对任意0≤m≤n 素性检验 素性检验是指对给定的数检验其是否为素数 直接判断一个整数是否为素数是困难的； 对于大数的素性检验来说没有简单直接的方法，目前常用的是概率检验法，如Miller-Rabin算法 素数分布密度：在n范围内:平均每(ln n)个整数中有一个素数。所以平均而言，在找到一个素数之前，需要测试的整数的个数为0.5ln n。 素性检验 引理 : 如果p为大于2的素数，则方程 x2 ≡1(mod p)的解只有x≡1和x≡-1。 证明：由x2≡1 mod p，有x2-1≡0 mod p，(x+1)(x-1)≡0 mod p，因此p|(x+1)或p|(x-1)或 p|(x+1)且p|(x-1)。 若p|(x+1)且p|(x-1)，则存在两个整数k和j，使得x+1=kp，x-1=jp,两式相减得2=(k-j)p，为不可能结果。所以有p|(x+1)或p|(x-1)。 设p|(x+1)，则x+1=kp