南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）数论算法（OLD）

计算机问题求解一论题4-2 数论算法 2017年3月27日

计算机问题求解 – 论题4-2 - 数论算法 2017年3月27日

问题1： 讨论数论算法的复杂性有 什么特殊之处？为什么？ 想想两个“很大很大”的整数相乘

想想两个“很大很大”的整数相乘

“长乘” 5678·4321 22712 问题2： 17034 11356 你能解释以下 5678 24534638 下面的论断吗？ thismodipy -bit rs by theordnary method uses)bit operations

“长乘

可能是世界上最古老的算法 EUCLID(a,b) 1 ifb==0 2 return a 3 else return EUCLID(b.a mod b) Theorem 31.9(GCD recursion theorem) For any nonnegative integer a and any positive integer b, gcd(a,b)=gcd(b,a mod b). 证明的关键：a mod b可以表示为和的线性组合：a-qb; 所以gcd(a,b)可以整除(a mod b),所以可以整除gcd(b,a odb)；类似地可以证明后者也可以整除前者，两者均为 正，所以相等

可能是世界上最古老的算法 证明的关键：a mod b 可以表示为a和b的线性组合：a-qb； 所以gcd(a,b)可以整除(a mod b), 所以可以整除gcd(b, a mod b)；类似地可以证明后者也可以整除前者，两者均为 正，所以相等

间题4：如何观察这个算法的复杂度？ 4.1：uclid算法的复杂度如何评估？ 4.2:它与Fibonaci/序列有巧合吗？这种 巧合是偶然还是必然？

Le1ma31.10 If a >b 1 and the call EUCLID(a,b)performs k 1 recursive calls,then a≥Fk+2andb≥F+i 这个定理的直观含义是什么？

这个定理的直观含义是什么？

定理的证明 shall then prove that the lemma holds for k recursive calls.Since k >0,we have b>0,and EUCLID(a,b)calls EUCLID(b,a mod b)recursively,which in turn makes k-1 recursive calls.The inductive hypothesis then implies that bF+ (thus proving part of the lemma),and a mod b>F.We have b+(a mod b)b+(a-bla/b]) ≤a, since a >b>0implies a/b]>1.Thus, a ≥b+(a mod b) Fk+1+Fk Fk+2·

定理的证明

Lemma 31.10 If a >b 1 and the call EUCLID(a,b)performs k 1 recursive calls,then a≥Fk+2andb≥Fk+l 定理11可以由引理10直接得到。Why? Theorem 31.11 (Lame's theorem) For any integer k 1,if a >b 1 and b Fk+1,then the call EUCLID(a,b) makes fewer than k recursive calls

定理11可以由引理10直接得到。Why？

How to understand the following sentences? We can show that the upper bound of Theorem 31.11 is the best possible by showing that the call EUCLID(F+1,F)makes exactly k-1 recursive calls when k≥2. gcd(Fk+1.Fk)=gcd(Fk,Fk+1 mod Fk) gcd(Fk,f-i）

How to understand the following sentences?

EXTENDED-EUCLID(a,b) 1 if b==0 2 return (a,1,0) 3 else (d',x',y')=EXTENDED-EUCLID(b,a mod b) 4 (d,x,y)=(d',y',x'-a/by) 5 return (d,x,y) 问题5： “扩充”的Euclid算法，扩充了什么？怎么实现 的？这个扩充的结果用处是什么？