之前一直只知道欧几里得辗转相除法,今天学习了一下另外一种、在处理大数时更优秀的算法——Stein
特此记载
1.欧几里得(Euclid)算法
又称辗转相除法,依据定理gcd(a,b)=gcd(b,a%b)
实现过程演示: sample:gcd(15,10)=gcd(10,5)=gcd(5,0)=5
C语言实现:
int Euclid_GCD(int a, int b)
{
return b?Euclid_GCD(b, a%b):a;
}
2.Stein 算法
一般实际应用中的整数很少会超过64位(当然现在已经允许128位了),对于这样的整数,计算两个数之间的模是很简单的。对于字长为32位的平台,计算两个不超过32位的整数的模,只需要一个指令周期,而计算64位以下的整数模,也不过几个周期而已。但是对于更大的素数,这样的计算过程就不得不由用户来设计,为了计算两个超过 64位的整数的模,用户也许不得不采用类似于多位数除法手算过程中的试商法,这个过程不但复杂,而且消耗了很多CPU时间。对于现代密码算法,要求计算 128位以上的素数的情况比比皆是,设计这样的程序迫切希望能够抛弃除法和取模。
依据定理:
gcd(a,a)=a,也就是一个数和其自身的公约数仍是其自身。
C语言实现:
int Stein_GCD(int x, int y)
{
if (x == ) return y;
if (y == ) return x;
if (x % == && y % == )
return * Stein_GCD(x >> , y >> );
else if (x % == )
return Stein_GCD(x >> , y);
else if (y % == )
return Stein_GCD(x, y >> );
else
return Stein_GCD(min(x, y), fabs(x - y));
}