《现代密码学原理与应用 教学课件 ppt 作者 宋秀丽 第11章 》由会员分享，可在线阅读，更多相关《现代密码学原理与应用 教学课件 ppt 作者 宋秀丽 第11章 （24页珍藏版）》请在金锄头文库上搜索。
1、第11章 密码学相关数学知识,11.1 素数和合数 11.1.1 素数和合数的定义 定义11.1 对于整数a和b，如果存在整数q，使得a=bq，则称b整除a，记为b|a，a叫做b的倍数，b叫做a的一个因子。 【例11-1】有3|27，则27是3的倍数，3是27的一个因子； 再有 5|100，则100是5的倍数，5是100的一个因子。,定义11.2 对于整数p1，如果因子仅为1和p，则称p为素数（或质数）；否则称为合数。 1既不是素数也不是合数。在只考虑非负整数的情况下，素数是只能被1和其自身整除的正整数。 【例11-2】17, 19是素数，存在 ， 323=17*19 则323是合数。,11.
2、1.2 素数检测,素数有无限多个，但目前还没有一个规律能确定所有的素数。有一些检测不太大的整数为素数的方法和对于大的整数的近似检测算法。 定理11.1 如果整数a1，则a的大于1的最小因子一定是素数。 推论11.1 合数a的大于1的最小因子不超过 。 定理11.2 设n是一个大于1的正整数，如果对所有小于或等于 的素数p，都有pn， 则n一定是素数。,1Eratosthenes筛选法 【例11-3】求出所有不超过100的素数。 输出的结果为 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 7
3、3, 79, 83, 89, 97,2费尔玛（Fermat）定理检测法 根据费尔玛定理可以对大的正整数近似检测其素性。费尔玛定理给出了整数n为素数的必要条件： 对任意的整数a，如果满足gcd(a,n) 则an-11(mod n)。 也就是说如果存在与n互素的整数a，不满足an-11(mod n)，则说明n肯定不是素数。 反之，如果有整数a，满足条件 且an-11(mod n)，则n不一定为素数，此时称n是关于基数a的伪素数。 【例11-4】341, 561, 645, 1105等都满足 2n-11(mod n) 但它们都是合数，是基数为2的伪素数。,3Miller-Rabin概率测试法 素数还
4、具有更强的性质：设n是一个大于4的奇素数，n-1=2sr，s和t是正整数， r为奇数，则对所有满足 的整数a，下面两个条件中至少有一个被满足： 1) ar1(mod n)； 2) 对于某个 ，有 则称n通过以a为基的Miller-Rabin概率测试。,定理11.4（算术基本定理）任何大于1的整数n都可以分解为素数的乘积，且在不记顺序的情况下，分解式是唯一的。 将分解式中相同的素数写出幂的形式，则得到如下的标准分解式： 其中，p1p2pt是素数，n1, n2, , nt是正整数。 【例11-5】900的标准分解式为：,11.2 整数的因子分解,11.3.1 同余的性质 定理11.5 （带余除法定
5、理）设n为不等于0的整数，则任意整数a可唯一表示为如下形式： a=nq+r，q和r为整数且0r|n| q和r分别称为a除以n的商和余数。将r定义为a mod n，即a mod n=r。注意0a mod nn。 【例11-8】 由于 5=13+2 所以 5 mod 3=2 又由于 -5=(-2) 3+1 所以 -5 mod 3=1。,11.3 同余运算,定义11.3对于整数a、b和正整数n，如果 a mod n=b mod n 则称a和b模n同余，记为ab(mod n)， n称为模数。 【例11-9】由于 9 mod 5=4，-1 mod 5=4 故 9 -1(mod 5)；,定理11.6 ab
6、(mod n)与以下条件等价： 1) 2) 定理11.7 模n的同余关系是整数集合上的等价关系，即具有 自反性：aa(mod n) 对称性：如果ab(mod n)，则ba (mod n) 传递性：如果ab(mod n)，bc(mod n)，则ac(mod n),同余具有以下性质：,【例11-10】判断5874192是否能被3整除。 【例11-11】2005年7月26日是星期二，问此天后第 21000 天是星期几？,11.4 欧几里德算法,若a除尽b,且a 除尽c,则a是b和c的公因子。即 a = gcdb,c 或 a=(b,c) 若c是a的倍数，又c是b的倍数，则c是a和b的公倍数。即 c =
7、 lcma,b 或 c=a,b 定理11.8 如果 且a,b,q,r都为整数，则,欧几里德（Euclid）算法。其具体思想描述如下： 设a与b是两个非零的整数，且b不整除a，则根据带余除法定理可以写出一串等式,如何求gcda,b呢？,求gcd224,34=? gcd224,34 = gcd34,20 = gcd20,14 = gcd14,6 = gcd6,2 = 2,11.4.2 乘法逆元,定义11.6 对于整数a和正整数n，当 gcd(a,n)=1时存在整数c ，使得 称 c为a关于模n的乘法逆元，记为a-1。,11.5 费尔玛定理和欧拉定理,定理11.10（费尔玛定理）如果p是素数，并且a
8、是不能被p整除的正整数，则 另一等价形式：如果p是素数，a是任意的正整数且gcd(a,p)=1，则有 【例11-18】已知 a=5，p=7 则 561(mod 7)或575(mod 7)。,11.5.1 费尔玛定理,【例11-19】求 的值,定义11.7 欧拉函数(n)(n1)表示比n小且与n互素的正整数的个数。 【例11-20】求(15) 由于n=15，比15小且与15互素的正整数有 1, 2, 4, 7, 8, 11, 13,14 共8个，故(15)=8。 欧拉函数具有如下性质： 1) 当n是素数时，有 (n)=n-1 因为比n小且与n互素的正整数有1,2,n-1。 2) 当n=pq，且p和q是互异的素数时，则有,11.5.2 欧拉函数,
