文档介绍：第二章数学基础(3学时)(1)掌握数论的有关基本定义、Euclid算法、同余概念及二次剩余概念;(2)掌握熵和互信息的概念;(3)了解三个NP-完全问题。(1)数论的有关基本定义和定理;(2)信息论的有关定义和定理。数论、信息论和算法复杂性理论是近代密码学的理论基础,本章给出简单介绍。:字母N表示全体自然数集合,Z表示全体整数集合,即N={0,1,2,∙∙∙∙∙∙}Z={∙∙∙∙∙∙,-2,-1,0,1,2,∙∙∙∙∙∙},使得n=kd,则称d整除n,记作d|n,其中d称作n的因数(Divisors),n称作d的倍数。如果不存在这样一个整数kZ使得n=kd,则称d不整除n,记作d+n。(1)若a、b、c均为整数,若c|a且c|b,则称c是a和b的公因数。把a和b的所有公因数中最大的,称为a和b的最大公因数(monDivisors),记作gcd(a,b)。(2)若a、b、c均为整数,若a|c且b|c,则称c是a和b的公倍数。把a和b的所有公倍数中最小的,称为a和b的最小公倍数,记作lcm(a,b)。例如:gcd(12,60)=12,lcm(15,20,30)=(>1)称为素数(PrimeNumber),如果除1和其本身除外,p没有任何其它因数。不是素数的整数称为合数。例如:7=1×7,7没有1和7以外的因数,因此7是素数;6=2×3,6有因数2和3,因此6是合数。从此定义可知,正整数集合可分为三类:素数、合数和1。(算术基本定理)任何一个正整数m,都存在唯一的因数分解形式:m=p1e1p2e2……pnen其中eiN,pi是素数且p1<p2<……<pn,又称为m的标准分解形式。例如:6=21×31×50,20=22×30×51,100=22×30×,任何整数可以分解成标准形式,从而可方便地求出两个整数的最大公因数和最小公倍数。设a、b是两个正整数,且有标准分解形式: a=p1e1p2e2……pneneiN b=p1f1p2f2……pnfnfiN 则 gcd(a,b)=,lcm(a,b)=其中min{x,y}表示x,y中最小者;max{x,y}表示x,y中最大者。 例如: gcd(6,20)=2min{1,2}∙3min{1,0}∙5min{0,1}=21∙30∙50=2, lcm(6,20)=2max{1,2}∙3max{1,0}∙5max{0,1}=22∙31∙51=(欧几里德)算法 利用算术基本定理可以求得两个整数的最大公因数,但当两个整数比较大时,求它们的标准分解形式非常困难,因此求其最大公因数也变得非常困难,Eulid算法成为解决该问题的另一方法。(带余数除法)设a、bN,其中b>0,则存在两个整数q、r使得: a=bq+r0≤r<b 成立,其中q和r唯一确定。、bN,则存在两个整数v、u,使得: ua+bv=gcd(a,b)(Eulid算法)又称辗转除法,,得以下等式: a=bq1+r10<r1<b b=r1q2+r20<r2<r1 r1=r2q3+r30<r3<r2 … rn-2=rn-1qn+rn0<rn<rn-1 rn-1=rnqn+1+rn+1rn+1=0 则有: gcd(a,b)=(即每次的余数为除数去除上一次的除数)。每进行一次带余数除法,余数会递减,而b是有限的,因此经过一定次数的带余数除法,余数变为0。最后一个不为0的余数rn就是a和b的最大公因数。 例:求gcd(1970,1066)=? 【解】用欧几里德算法的计算过程如下: 1970=1×1066+904 1066=1×904+162 904=5×162+94 162=1×94+68 94=1×68+26 68=2×26+16 26=1×16+10 16=1×10+6 10=1×6+4 6=1×4+2 4=2×2+0 因此gcd(1970,1066)=2侗辉亦声布屏窖