怀化火车站网站,做的最好自考网站是哪个,安卓软件开发培训,长沙定制网站建设欧几里德算法是计算两个数最大公约数的传统算法#xff0c;他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷#xff0c;这个缺陷只有在大素数时才会显现出来。 考虑现在的硬件平台#xff0c;一般整数最多也就是64位#xff0c;对于这样的整数#xff0c;计…欧几里德算法是计算两个数最大公约数的传统算法他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷这个缺陷只有在大素数时才会显现出来。 考虑现在的硬件平台一般整数最多也就是64位对于这样的整数计算两个数之间的模是很简单的。对于字长为32位的平台计算两个不超过32位的整数的模只需要一个指令周期而计算64位以下的整数模也不过几个周期而已。但是对于更大的素数这样的计算过程就不得不由用户来设计为了计算两个超过64位的整数的模用户也许不得不采用类似于多位数除法手算过程中的试商法这个过程不但复杂而且消耗了很多CPU时间。对于现代密码算法要求计算128位以上的素数的情况比比皆是设计这样的程序迫切希望能够抛弃除法和取模。 Stein算法由J. Stein 1961年提出这个方法也是计算两个数的最大公约数。和欧几里德算法 算法不同的是Stein算法只有整数的移位和加减法这对于程序设计者是一个福音。 为了说明Stein算法的正确性首先必须注意到以下结论 gcd(a,a) a也就是一个数和他自身的公约数是其自身 gcd(ka,kb) k gcd(a,b)也就是最大公约数运算和倍乘运算可以交换特殊的当k2时说明两个偶数的最大公约数必然能被2整除 C/实现 // cstein 算法 int gcd(int a,int b){ if(ab{ int temp a; a b; btemp; } if(0b)//the base case return a; if(a%20 b%2 0)//a and b are even return 2*gcd(a/2,b/2); if ( a%2 0)// only a is even return gcd(a/2,b); if ( b%20 )// only b is even return gcd(a,b/2); return gcd((ab)/2,(a-b)/2);// a and b are odd }
