扩展欧几里德算法

欧几里德算法找gcd已被我们所熟知,但刚看到扩展欧几里德算法的时候的确让我昏了一下,google,mathworld,wiki,baidu各给出了不同的说明,更是有多种多样的算法实现。

该算法在密码学中有非常重要的地位,因为很多算法都要用到乘法反元素,而它是找反元素最高效率的算法,无论两个数有多大,都可以在接近对数级时间复杂度下完成。

在《Making,Breaking Codes》一书中用了一个矩阵乘法的方式来表示中间过程,非常漂亮!可以理解这个过程,但它并不能很清楚的表示扩展欧几里德算法。靠,无法输入数学符号,将就着看吧:

{xn}   = { 0 1} * {xn-1}

{yn}      { 1 -q}    {yn-1}

q=(xn-1)/(yn-1)

经过一系列运算最后会得到一个2×1矩阵

{gcd(x,y)}

{0}

如果将

{ 0   1}    { 0 1}   。。{ 0 1}

{ 1 -q1}   { 1 -q2}   { 1 -qn}

表示成一系列矩阵,而它们的乘积M等于:

{ a b}

{ c d}

那么我们就得到了

ax+by=gcd(x,y)

a是x模y的乘法反元素,b是y模x的乘法反元素。

如果你没有看过这个算法,可以肯定你还是昏的,其实扩展算法与标准算法最关键的地方在于使用了商,看下这段代码:

int gcd(int u,int v)
{
if(v==0)
{
return u;
}

const int r=u%v;
return gcd(v,r);
}

int extgcd(int u,int v,int &x,int &y)
{
if(v==0)//当u*x+v*y=u时,脑子里不要想v现在的值,x,y各该是多少,显然x==1,y==0,递归算法常需要我们刻意忘记某个变量的值
{
x=1;
y=0;
return u;
}

const int q=u/v;
const int r=u-q*v;//u%v
int g=extgcd(v,r,x,y);

int t=x-q*y;//计算系数,回代的时候要交换x,y值
x=y;
y=t;

printf(“%d=%d*%d+%d
“,u,q,v,r);

return g;
}

int main(void)
{
int u=614,v=513,x=0,y=0,g=0;
g=extgcd(u,v,x,y);
printf(”
%d * %d + %d * %d = %d
“,u,x,v,y,g);

return 0;
}

输出:

2=2*1+0
3=1*2+1
5=1*3+2
8=1*5+3
101=12*8+5
513=5*101+8
614=1*513+101

614 * -193 + 513 * 231 = 1
Press any key to continue

其实可以非常简单的理解它,说的再通俗一点就是看成解一元一次方程组,而有多少方程式取决于什么时候找到最大公约数,这中间会用到每一步的商构造方程式。

每一个方程式回代到上一级,最终得到两个系数a和b!

参考:

Extended Euclidean algorithm

原文地址:http://hi.baidu.com/kruglinski/blog/item/b4ede217d7e98701c83d6d2f.html

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>