百度空间 | 百度首页 
               
 
查看文章
  
扩展欧几里德算法
2006-08-17 11:01

给定两个正整数m，n；计算它们的最大公因子d和两个整数a和b，使得am+bn=d;

1) a'=b=1; a=b'=0; c=m;d=n

2)q=c/d; r=c%d;

3) if r==0 then print am+bn=d;

4)else c=d; d=r; t=a'; a'=a; a=t-qa; t=b'; b'=b; b=t-qb;

5) goto 2)


类别：算法(algorithm) | 添加到搜藏 | 浏览() | 评论 (2)
 
最近读者：
 
网友评论：
1
2006-08-17 11:48 | 回复
为了证明上面的结论，我们把上述计算中xi、yi看成ti的迭代初始值，考察一组数(t1,t2,t3)，用归纳法证明：当通过扩展欧几里德算法计算后，每一行都满足a×t1 + b×t2 = t3 第一行：1 × a + 0 × b = a成立 第二行：0 × a + 1 × b = b成立 假设前k行都成立，考察第k+1行 对于k-1行和k行有 t1(k-1) t2(k-1) t3(k-1) t1(k) t2(k) t3(k) 分别满足： t1(k-1) × a + t2(k-1) × b = t3(k-1) t1(k) × a + t2(k) × b = t3(k) 根据扩展欧几里德算法，假设t3(k-1) = j t3(k) + r 则： t3(k+1) = r t2(k+1) = t2(k-1) - j × t2(k) t1(k+1) = t1(k-1) - j × t1(k) 则 t1(k+1) × a + t2(k+1) × b =t1(k-1) × a - j × t1(k) × a + t2(k-1) × b - j × t2(k) × b = t3(k-1) - j t3(k) = r = t3(k+1) 得证 因此，当最终t3迭代计算到1时，有t1× a + t2 × b = 1，显然，t1是a模b的乘法逆元，t2是b模a的乘法逆元
 
2
2007-02-01 18:27 | 回复
《具体数学》第四章，嘿嘿。
 
发表评论：
姓　名：
网址或邮箱： (选填)
内　容：
验证码： 请点击后输入四位验证码，字母不区分大小写
      

     

©2009 Baidu