第31章-数论算法.pptxVIP

第31章 数论算法预备知识1数论基础数论是一门古老的数学分支。以前人们都认为它是完全纯粹数学，在现实生活中很难找到它的实际应用。自从1976年公开密钥密码体制诞生以来，现代密码学就和数论有着千丝万缕的联系。自然数与整数一、引言约定：字母N表示全体自然数集合，Z表示整数集合，即N={0，1，2，…}Z={…，-2，-1，0，1，2，…}整除定义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）算法（辗转相除法）7=63-4 ?14 =63-4 ?(77-63) =-4 ?77+5 ?63 = -4 ?77+ 5 ?(140-77) =5 ?140-9 ?77 = 5 ?140 -9 ?(777- 5 ?140) =-9 ?777+50 ?140 =-9 ?777+50 ?(917-777) =50 ?917-59 ?777 = 50 ?917-59?(1694-917) = -59?1694+109 ?9171694=1?917+777917=1?777+140777=5?140+77140=1?77+6377=1?63+1463=4?14+714=2?7+0gcd(1694,917)=7 同余两个整数同余：设a,b是两个整数，m是一个正整数。如果 m|(b-a), 则称a与b对模m同余。记作a? b(mod m).例如，3? 1（mod 2）4? 1 (mod 3)a? a (mod m)a? b (mod m)b? a (mod m),b? c (mod m)a? b (mod m)a? bc(mod m)模运算定义模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=6, {1,2,3,4,5}中与m互素的数为{1，5}，共两个，因此=2欧拉函数设正整数m的标准分解形式为则例如6=2? 3欧拉定理与费尔马定理欧拉定理：如果a和m互素，则费尔马定理 若p是素数，则中国剩余定理中国剩余定理：设m1, m2,…, mk 是k个两两互素的整数，m= m1·m2,…·mk , Mi=m/mi，I=1,2,…,k。则同余方程组x? b1 (mod m1)x? b2 (mod m2)………x? bk (mod mk)有解可由欧几里德算法求出。离散对数离散对数问题设x, r, n是正整数。已知x, r和n, 可以很快地求出反过来，如果已知y, x和n, 求r使得：成立，这就是离散对数问题。离散对数当y, x和n都比较小时，可以用穷举有哪些信誉好的足球投注网站求得r, 如果这些数都比较大，这是非常困难的。如果给定一个整数r, 那么可以很容易验证它是否为的解。因此，离散对数问题是NP问题。计算机理论科学已经证明，离散对数问题是NP－完全问题。加密机制一个密码体制被定义为一对数据变换，其中一个变换应用于称之为明文的数据项，变换后产生的相应数据项称为密文；而另一个变换应用于密文，变换后的结果为明文。ＣＭ