第9章-数论算法.pptxVIP

第九章 数论算法;内容提要 ;重点与难点 ;学习目的与要求 ;数论是一门古老的数学分支。以前人们都认为它是完全纯粹数学，在现实生活中很难找到它的实际应用。自从1976年公开密钥密码体制诞生以来，现代密码学就和数论有着千丝万缕的联系。;一、引言;定义1：如果存在一个整数k使得n=kd，则称d整除n,记作d|n，其中d称作n的因子，n称作d的倍数。如果不存在这样一个整数使得n=kd，则称d不整除n，记为d?n。 ;定义2：整数p1称为素数，如果除了1和其本身外，p没有任何其它因数。不是素数的整数称为合数。 ;带余除法：设a,b是两个整数，其中b0。则存在两个整数q,r使得a=q·b+r。其中q和r是唯一确定的。 ;公因数：设a,b是两个整数，既是a的因数又是b的因数的数称为a,b的公因数。 ;最大公因数：a和b的所有公因数中最大者，称为a和b的最大公因数，记作gcd(a,b)。 ;公倍数：设a,b是两个整数，既是a的倍数又是b的倍数的数称为a,b的公倍数。 最小公倍数：a和b的所有公倍数中最小者，称为a和b的最小公倍数，记作lcm(a,b)。 ;lcm(a,b) ·gcd(a,b)=a·b. ;a与b互素：如果对两个整数a,b有gcd(a,b)=1,则称a与b互素。 ;设a,b是自然数，则存在两个整数u和v使得： u·a+v·b=gcd(a,b);算术基本定理：任何一个正整数m都存在唯一的因数分解形式：;;;欧几里德（Euclid）算法（辗转相除法）;1694=1?917+777 917=1?777+140 777=5?140+77 140=1?77+63 77=1?63+14 63=4?14+7 14=2?7+0 gcd(1694,917)=7 ;两个整数同余：设a,b是两个整数，m是一个正整数。如果 m|(b-a), 则称a与b对模m同余。记作a? b(mod m). 例如，3? 1（mod 2） 4? 1 (mod 3);定义模m的算术运算：Zm={0，1，…，m-1},它有两种运算+和? 。在Zm中的加法和乘法，除了将结果被模m约简外，恰好像实数加法和乘法。 例如：在Z2中的加法 0+0? 0 (mod 2) 0+1? 1 (mod 2) 1+0? 1 (mod 2) 1+1? 0 (mod 2) 例如：在Z16中的乘法11 ?13 11 ?13=143 ?15 （mod 16）;定义4 欧拉函数 是定义在正整数上的函数，它在正整数m的值等于1，2，…，m-1中与m互素的数的个数，记为 ;设正整数m的标准分解形式为;欧拉定理：如果a和m互素，则;中国剩余定理：设m1, m2,…, mk 是k个两两互素的整数，m= m1·m2,…·mk , Mi=m/mi，I=1,2,…,k。则同余方程组;;;;公开密钥密码体制;单向函数;RSA公开密钥密码体制;RSA公开密钥密码体制;RSA公开密钥密码体制;2.RSA加密、解密过程;2.RSA加密、解密过程;2.RSA加密、解密实例;Miller 素数测试;;定理 1 如果 n 是素数，则测试算法总是输出“prime”； 如果n是合数， 则测试算法输出“合数”的概率不小于0.5。;小结