Math 版 (精华区)

发信人: flytigger (Ostrich), 信区: Math
标  题: 计算机密码学之五
发信站: 哈工大紫丁香 (Sun Sep 26 16:57:09 1999), 转信

    (a,b)=(b,r)=(r,r[1])
依此类推，直到出现余数为零为止。这样，存在某一整数k,使
得
        r[k-2]=r[k-1]*q[k]+r[k],r[k]<>0
        r[k-1=r[k]*q[k+1]
对于这个序列有
        r[1]>r[2]>...>r[k]>0
且      (a,b)=(b,r)=(r,r[1])=...=(r[k-1],r[k])=r[k]
所以r[k]是gcd{a,b}
        定理的证明过程提供了一个求gcd{a,b}的具体步骤。
        例１：求gcd{726,393}。
                726=1x393+333
                393=1x333+60
                333=5x60+33
                 60=1x33+27
                 33=1x27+6
                 27=4x6+3
                  6=2x3+0
所以，d=gcd{726,393}=3。
        定理３　若d=gcd{a,b}，则存在整数p和q，使得d=p*a
+q*b。
        证明：由定理２的证明可得                               
                r[k]=-q[k]*r[k-1]+r[k-2]
                r[k-1]-q[k-1]*r[k-2]+r[k-3]
                ......
                r[1]=-q[1]*r+b
                r=-q*b+a
-----Page 5        Typed by Chan       
--
        ★来棋牌乐揍揍热闹吧……
        ★http://www.nease.net/~chan (一个住的小屋）
        ★只有天马行空的想象，世界才会变得更理想……
※ 修改:．himen 于 Sep 26 17:00:51 修改本文．[FROM: 159.226.41.166]
--
※ 转寄:．华南网木棉站 bbs.gznet.edu.cn．[FROM: 159.226.41.166]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: himen.bbs@melon.gzne]