算法分析与设计2004春.课件.第11讲

《算法分析与设计2004春.课件.第11讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Lecture11.NumbertheoreticAlgorithm清华大学宋斌恒清华大学宋斌恒1Fromuselesstouseful¢Numbertheoryisregardedasabeautifulbutlargelyuselessinthepast¢Todaynumber-theoreticalgorithmsareusedwidely清华大学宋斌恒21Contents¢Basicconcepts¢Divisibilityanddivisor¢Primeandcompositenumbers¢Divisiontheorem¢Grea

2、testcommondivisors¢Relativeprimeintegers¢Uniquefactorization¢Euclidalgorithmanditscomplexityanalysis¢Modulararithmetic¢Solvingmodularlinearequation¢孙子定理【中国剩余数定理】¢RSA¢素数测试【primalitytesting】清华大学宋斌恒3BasicConcepts¢Z={…,-2,-1,0,1,2,…}Integers整数¢N={0,1,2,3…}Naturalnumbers自然数¢d

3、a(

4、ddividesa)d整除a，存在整数k使得a=kd¢Divisor:约数¢Trivialdivisor：平凡约数【举例】¢素数【1，2，3，4那个是素数】¢合数【1，2，3，4那个是合数】清华大学宋斌恒42与算法复杂度相关的概念¢整数的大小：二进制【十进制等】的长度作为一个整数的复杂度度量。¢问题：能不能有必二进制更好的表示方法？【使得表示长度更短】。Fibonacci堆的思想：其实就是利用了比堆更加非线性的数据结构。¢Thefunctionof“Log*ofn”¢f(i)(n)=nifi==0¢f(i)(n)=f(f(i)(n))ifi>

5、0¢lg*n=min{i>=0:lg(i)(n)<=1}清华大学宋斌恒5除法定理¢对任意整数a和正整数n，存在唯一整数q和r使得0≤r

6、tegers¢如果gcd(a,b)=1称a和b互素¢唯一分解定理¢a=Π(pei),p是素数单调升【是否可以通过i=1,…nii此方法计算gcd?复杂度？】¢？如何证明有无穷多素数？？【课堂提问】清华大学宋斌恒7gcd¢GCD递推定理：gcd(a,b)=gcd(b,amodb)¢辗转相除法【如何说明其正确性？】¢存在x和y使得gcd(a,b)=xa+yb。¢西方人叫Euclid算法清华大学宋斌恒84Euclid算法1.Euclid(a,b)1.Ifb==0returna2.ReturnEuclid(b,amodb)¢Runningtime:¢

7、Stepsofdivision:O(lga)=O(n)nisthebitlengthofa.¢Lame’stheorem:欧几里德算法迭代步数小于k，其中Fk是第k个Fibonacci数。¢证明提示：数学归纳法证明：如果a>b>=1而且上述Euclid算法进行了k步递归，则a>=Fk+2andb>=Fk+1清华大学宋斌恒9扩展欧几里德算法¢Extended-Euclid(a,b)¢Ifb=0thenreturn(a,1,0)¢(d’,x’,y’)ÅExtended-Euclid(b,amodb)¢Return(d’,y’,x’-[a/b]y’

8、);清华大学宋斌恒105计算最大公约数及其线性表达ab[a/b]dxy14091172-3914917-12x’-[a/b]y’4942171-1x’-[a/b]y’4276701x’-[a/b]y’70-710清华大学宋斌恒11群的概念？¢群(S，⊕)1.封闭性2.么元3.结合率4.逆元交换率：交换群＝Abelian群清华大学宋斌恒126Modulararithmetic¢＋n群，¢×n群¢(Zn,+n)是有限Abel群¢(Z*,×)是有限Abel群nn¢其中Z*＝{[a]:gcd(a,n)=1}nn清华大学宋斌恒13.群15.151247

9、811131412441748111314清华大学宋斌恒147Euler’sphifunctionφ(n)=nΠ(1-1/p)isthesizeofZ*.欧拉φ函数