● 计算机密码学之五(转寄) - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: hbo (H.B.), 信区: Hacker
标  题: 计算机密码学之五(转寄)
发信站: 深大荔园晨风站 (Mon Mar 30 11:00:01 1998), 转信

发信人: chan (Hacking...), 信区: Hacker
标  题: 计算机密码学之五
发信站: 华南网木棉站 (Mon Mar 30 09:38:33 1998), 转信

    (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{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

--
※ 来源:．深大荔园晨风站 bbs.szu.edu.cn．[FROM: 202.192.140.143]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店