arongnet 阅读(1391) 评论(26)

欧几里德算法

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理:

定理:gcd(a,b) = gcd(b,a mod b)

 证明:a可以表示成a = kb + r,则r = a mod b
 假设d是a,b的一个公约数,则有
 d|a, d|b,而r = a - kb,因此d|r
 因此d是(b,a mod b)的公约数
 
 假设d 是(b,a mod b)的公约数,则
 d | b , d |r ,但是a = kb +r 
 因此d也是(a,b)的公约数
 
 因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证

欧几里德算法就是根据这个原理来做的,其算法用C++语言描述为:

    void swap(int & a, int & b)
    {
        int c = a;
        a = b;
        b = c;
    }
    int gcd(int a,int b)
    {
        if(0 == a )
        {
            return b;
        }
        if( 0 == b)
        {
            return a;
        }
        if(a > b)
        {
            swap(a,b);
        }
        int c;
        for(c = a % b ; c > 0  ; c = a % b)
        {
            a = b;
            b = c;
        }
        return b;
    }

模P乘法逆元

对于整数a、p,如果存在整数b,满足ab mod p =1,则说,b是a的模p乘法逆元。

定理:a存在模p的乘法逆元的充要条件是gcd(a,p) = 1

 证明:
 首先证明充分性
 如果gcd(a,p) = 1,根据欧拉定理,aφ(p) ≡ 1 mod p,因此
 显然aφ(p)-1 mod p是a的模p乘法逆元。
 
 再证明必要性
 假设存在a模p的乘法逆元为b
 ab ≡ 1 mod p
 则ab = kp +1    ,所以1 = ab - kp
 因为gcd(a,p) = d 
 所以d | 1
 所以d只能为1

扩展欧几里德算法

扩展欧几里德算法不但能计算(a,b)的最大公约数,而且能计算a模b及b模a的乘法逆元,用C语言描述如下:

 int    gcd(int    a,    int    b    ,    int&    ar,int    &    br)
 {
  int    x1,x2,x3;
  int    y1,y2,y3;
  int    t1,t2,t3;
  if(0    ==    a)
  {//有一个数为0,就不存在乘法逆元
               ar    =    0;
               br    =    0    ;
               return    b;
  }
  if(0    ==    b)
  {
               ar    =    0;
               br    =    0    ;
               return    a;
  }
  x1    =    1;
  x2    =    0;
  x3    =    a;
  y1    =    0;
  y2    =    1;
  y3    =    b;
  int    k;
  for(    t3    =    x3    %    y3    ;    t3    !=    0    ;        t3    =    x3    %    y3)
  {
   k    =    x3    /    y3;
   t2    =    x2    -    k    *    y2;
   t1    =    x1    -    k    *    y1;
   x1    =    y1;
   x1    =    y2;
   x3    =    y3;
   y1    =    t1;
   y2    =    t2;
   y3    =    t3;
  }
  if(    y3    ==    1)
  {
   //有乘法逆元
   ar    =    y2;
   br    =    x1;
   return    1;
  }else{
          //公约数不为1,无乘法逆元
           ar    =    0;
           br    =    0;
           return    y3;
  }
 }

扩展欧几里德算法对于最大公约数的计算和普通欧几里德算法是一致的。计算乘法逆元则显得很难明白。我想了半个小时才想出证明他的方法。

首先重复拙作整除中的一个论断:

如果gcd(a,b)=d,则存在m,n,使得d = ma + nb,称呼这种关系为a、b组合整数d,m,n称为组合系数。当d=1时,有 ma + nb = 1 ,此时可以看出m是a模b的乘法逆元,n是b模a的乘法逆元。

为了证明上面的结论,我们把上述计算中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的乘法逆元。


评论列表
毛毛虫
re: 欧几里德算法和扩展欧几里德算法
还要考虑a和b为负数的情况。
根据公约数的2条基本性质(一共5条):
gcd(a,b)=gcd(b,a)
gcd(a,b)=gcd(-a,b)
所以还要在程序中加入2条条件语句:
if(a<0) a=-a;
if(b<0) b=-b;
毛毛虫
re: 欧几里德算法和扩展欧几里德算法
加一个swap()干嘛。没什么用啊!!而且就算要加,这个写法也有问题,无端端多做一次无用计算。
黑鹰
re: 欧几里德算法和扩展欧几里德算法
扩展欧几里德算法是中国的一个研究人员给出的,详细情况请查看有关算法的书籍。
fighter
re: 欧几里德算法和扩展欧几里德算法
会编程吗你!!??
怎么倒着做的!!??
无名小卒
re: 欧几里德算法和扩展欧几里德算法
那个swap是保证b一定是小于a的,为了让后面的程序不必考虑b大于a的情况,但是这个swap其实是可以不必单独制作一个子函数的,那样会减慢程序运行的速度……
无名小卒
re: 欧几里德算法和扩展欧几里德算法
有一个小小的很白的问题,如果我想要计算各个数据的乘法逆元,就是求方程1=s*a+t*b相应的 s 和 t 的值?或者能不能给出一个有效合理的公式?
此先谢过!
arong
re: 欧几里德算法和扩展欧几里德算法
这没有公式,因为值不唯一
如1= 2*3 -5 = 2*5 - 3*3 = 7*3 - 4*5 ...
这样,对于(3,5),其实有无数个解,怎么可能有公式
不过扩展欧几里德算法里应该已经包含一个解,你好好看看

这么多东西不合理?
arong
to fighter
实际上俺在学数学德人中,编程算中等,在学编程德人中,数学算中等
基本不会编程啊
无名小卒
re: 欧几里德算法和扩展欧几里德算法
但是如果对于给定的a, b的值,那末s, t的值应该是唯一的……欧几里得算法是提供了这样的算法,也就是在RSA和Affine Cipher密码系统中普遍应用的算法,即将每一个方程回代,最终写出1 = s*a + t*y的形式,但是我就是不会写程序代码……
jj
re: 欧几里德算法和扩展欧几里德算法
姓名:董存瑞 
性别:男
小名:四虎
死因:炸死
任务:连长说炸药包一面有胶,让我把他粘在桥下
临终遗言:连长**的我 靠,两边都有胶 
victor
re: 欧几里德算法和扩展欧几里德算法
好帖,建议在说明算法的时候,举一些具体数值的例子,更直观
sicheng
re: 欧几里德算法和扩展欧几里德算法
int Gcd(m, b) //assume m>b
{
  if (m%b)
    return b;
  else
    return Gcd(b, m%b);
}
This is extended Euclid Algorithm
sicheng

//求逆元
long double mod_1(long double u,  long double m)
{
  long double n1 = m, n2 = nod(u,m),
    b1 = 0, b2 = 1, r, t, q;
  do{
    r = mod(n1, n2);
    q = floor(n1/n2);
    if(fabs(r)>ee)   //ee=1e-10
    {
       n1 = n2; n2 = r; 
       t = b2; b2 = b1-q*b2; b1 = t;
    }
    else
       break;
   }while(1);
  b2 = mod(b2, m);
  return b2;
}
OVAX预测
re: 欧几里德算法和扩展欧几里德算法
那么,谁知道欧几里得算法的程序设计是什么?请速回
紫悦儿
re: 欧几里德算法和扩展欧几里德算法
请问用Euclid算法求123(mod17)的逆元怎么做?    如果有这方面的行家,可愿意加我QQ277935955,先谢了!
arong
re: 欧几里德算法和扩展欧几里德算法
123 mod 17的逆元计算

123 mod 17 = 4
123*123 mod 17 = 16 = -1
123*123*123*123 mod 17 =1
所以它逆元是123*3 mod 17 = 4 * (-1) = -4 = 13

13 * 123 = 1599 = 94 * 17 +1

C
re: 欧几里德算法和扩展欧几里德算法
也不可老踩人家的脚走路
kewei
re: 欧几里德算法和扩展欧几里德算法
ma+nb=1
-->(ma+nb)mod a=1mod a
-->(ma mod a +nb mod a)mod a=1
-->nb mod a=1
-->n是b模a的乘法逆元
同理
-->
m是a模b的乘法逆元

sunyfun
re: 欧几里德算法和扩展欧几里德算法
错了  还有一个条件没有判断
那就是任何整数x对1求模还是得1
即 1=1 mod x
plp626
re: 欧几里德算法和扩展欧几里德算法
那个兄弟不知在几楼?
int Gcd(m, b) //assume m>b 
{
........
}
其实不用假设m>b:

------------------------------------------------
int Gcd(m, b) //assume m>b 

  if (!b) 
    return m; 
  else 
    return Gcd(b, m%b); 

-------------------------------------------------

两个正整数的最大公约数的递归定义为:
(a,b)=(b,a%b)
(a,0)=a
如果a<b 那么(a,b)=(b,a%b)定会让两个数位置交换。

发表评论
切换编辑模式