/*
*我把这个大整数的系列写成了Code中的项目，见https://code.csdn.net/XUE_HAIyang/bignumber
*/
之前已经完成了大整数的表示、绝对值的比较大小、取负值、加减法运算、乘法运算以及除法和余数运算。具体见我的主页前三篇博客（自己动手写Java系列
）。
这篇博客添加求大整数GCD、扩展欧几里得算法和求Mod逆的算法。
扩展欧几里得算法
说道扩展的欧几里得算法，首先我们看下简单的欧几里得算法。经典的欧几里得算法就是
计算两个整数的最大公因子的算法，所基于的原理就是GCD（a， b）=GCD（b, a%b). 不断地迭代
下去就行了。代码见
/*
* mod 运算，模数是一个正数,被模数可以是负数，返回mod数
*/
public DecimalBig Mod(DecimalBig modnumber)
{
DecimalBig tempthis =Zero;
if (this.sign==-1)
tempthis=this.DivideReminder(modnumber).Add(modnumber);
else
tempthis=this;
return tempthis.DivideReminder(modnumber);
}
/**
* Returns a DecimalBig whose value is the greatest common divisor of
* {@code abs(this)} and {@code abs(val)}. Returns 0 if
* {@code this == 0 && val == 0}.
*
* @param val value with which the GCD is to be computed.
* @return {@code GCD(abs(this), abs(val))}
*/
public DecimalBig gcd(DecimalBig val)
{
if(val==Zero)
return this;
return val.gcd(this.Mod(val));
}
扩展的欧几里得算法不仅要计算a和b的做大公因子而且还要将其用a和b线性表出，
也就是计算出x和y使得GCD（a， b）=xa+yb；
算法我就引用<introduction to modern Computer Algebra>上的算描述了。
实现见代码
/**
* Returns a DecimalBig whose value is the linear representation of
* {@code abs(this)} modulus {@code abs(val)}.
*
* 这里边我们返回的是x使得x*this+yval=GCD(this,val);
* 如果return为t0则返回的是y使得x*this+yval=GCD(this,val)。
*/
private DecimalBig ExtGCD(DecimalBig val)
{
DecimalBig r0=this, r1=val;
DecimalBig s0=One, s1=Zero;
DecimalBig t0=Zero, t1=One;
DecimalBig temp_r, temp_s, temp_t;
while(r1.Compare(Zero)!=0)
{
DecimalBig q=r0.Divide(r1);
<span style="white-space:pre"> </span>temp_r=r0.Substract(q.Multiply(r1));
<span style="white-space:pre"> </span>temp_s=s0.Substract(q.Multiply(s1));
<span style="white-space:pre"> </span>temp_t=t0.Substract(q.Multiply(t1));
<span style="white-space:pre"> </span>
r0=r1;r1=temp_r;
s0=s1;r1=temp_s;
t0=t1;r1=temp_t;
}
return s0;
}
求Mod逆的算法。
扩展的欧几里得算法已经实现了，求mod 逆就是公因子是1的特例
/**
* Returns a DecimalBig whose value is the greatest common divisor of
* {@code abs(this)} and {@code abs(val)}. Returns 0 if
* {@code this == 0 && val == 0}.
*
* @param val value with which the GCD is to be computed.
* @return {@code GCD(abs(this), abs(val))}
*/
public DecimalBig Inv_Mod(DecimalBig val)
{
if (val.sign != 1)
throw new ArithmeticException("DecimalBig: modulus not positive");
if (this.gcd(val).Compare(One)==1)
throw new ArithmeticException("DecimalBig: modulus and this have commen dividor >1 ");
return this.ExtGCD(val);
}