第2章 信息安全数学基础new(数论)(精品·公开课件).ppt

第2章 信息安全数学基础 2010、07 第2章 信息安全数学基础 第2章 信息安全数学基础 整除定义及性质 带余数除法 带余数除法 素数定义及素数个数定理 素数补充定理 素数补充定理（续） 素数补充定理（续） 素数个数定理及证明 素数定义及素数个数定理 整数的唯一分解定理 最大公约数定义及求法 最大公约数的欧几里得算法 最大公约数的欧几里得算法（续） 欧几里得算法（例1） 最大公约数的欧几里得算法（续） 欧几里得算法（例2）：求gcd(12345，1111) 最大公约数的欧几里得算法（续） 欧几里得算法抽象 最大公约数的欧几里得算法（续） 欧几里得算法实现 扩展的欧几里得算法（续） 计算出了gcd(a,b); 但是并没有计算出两个数m，n来，使得： ma+nb=gcd(a,b) 扩展的欧几里得算法（续） 第2章 信息安全数学基础 同余 同余及模运算性质 模运算的除法运算及其性质 模运算的除法运算及其性质（续） 乘法逆元 扩展欧几里德算法与乘法逆元 欧几里德算法与乘法逆元 如果算法gcd（a，b）输出rm＝1，则b有乘法逆元 如果求出了ma+nb=1中的整数m，n，则可以求出b（mod a）的乘法逆元。 欧几里得算法没有给出b的乘法逆元b－1 如何求b－1 ？ 扩展的欧几里德算法 扩展欧几里德算法与乘法逆元（续） 扩展欧几里德算法与乘法逆元（续） 例：求 11 mod 26的乘法逆元(a=26,b=11) 扩展欧几里德算法 第2章 信息安全数学基础 中国剩余定理 中国剩余定理（续） 中国剩余定理（续） 中国剩余定理（续） 中国剩余定理（续） 中国剩余定理解同余方程组 中国剩余定理（续） 中国剩余定理（续） 练习1 解同余方程：6x=7 mod 23 练习2： 解同余方程：81x3+24x2+5x+23=0 mod 7 中国剩余定理（续） 中国剩余定理（续） 中国剩余定理（续） 第2章 信息安全数学基础 模的幂运算 模的幂运算（续） 模的幂运算（续） 请用平方-乘算法计算： （1） 3460 mod 51 （2） 34589 mod 101 第2章 信息安全数学基础 本原根有关定理（续） 离散对数困难问题（续） 课外阅读资料 Mao Wenbo， Modern Cryptography: Theory and Practice?， 电子工业出版社，2004 Any Question? QA 1、 利用扩展的欧几里德算法求28mod75的乘 法逆元(a=75,b=28)。 2、 求 253(mod 11) = ? 3、解同余方程 5x2+6x+49 = 0 (mod 60)。 4、求43的所有原根。 5、利用欧几里德算法求（50，35）的最大公约数。 6．计算20的欧拉函数。 5x2+6x+49 = 0 (mod 60) 第四章 同余方程 §1 同余方程的基本概念 一元同余方程： 设f(x)是整系数多项式 f(x)≡0(mod m) (等价于不定方程f(x)＋my=0) 解： c是解 f(c)≡0(mod m)，c mod m 是一个解 解数t：c1，c2，…，ct(或c1 mod m，c2 mod m，…，ct mod m)都是解，两两不同余，且任一解c(或c mod m)必和其中一个模m同余(或和其中一个相同) 一元同余方程组 整系数多项式fj(x)≡0(mod mj)，1≤j≤k。 解： c是解 fj(c)≡0(mod mj)，1≤j≤k。c mod m 是一个解，m=[m1，m2，…，mk] 解数：c1，c2，…，ct(或c1 mod m，c2 mod m，…，ct mod m)都是解，两两不同余，且任一解c(或c mod m)必和其中一个模m同余(或和其中一个相同) 具体求解方法：解同余方程和同余方程组只要在x=0，1，…，m－1中，或在任一取定的模m的完全剩余系中求解，其中满足同余方程和同余方程组的个数就是解数。 类似可讨论多元情形 §2 一次同余方程 ax≡b(mod m) 它等价于二元一次不定方程ax＋my=b 可利用第二章关于二元一次不定方程的结果来讨论一元一次同余方程，但这里用第三章的同余理论来讨论。 定理4.2.1 (a，m)=1 (a) 利用定理3.2.10(i)：x1 , x2 , …, xm 是模m的完全剩余系━ax1 , ax2 , …, axm 是模m的完全剩余系，推出有且仅有一个xj使得axj≡b(mod m)，所以有唯一解xj mod m。 (b) 利用性质3.1.VIII：整数a对模m有逆元素a－1 (mod m)，aa－1≡1(mod m)，所以 a