欧几里德算法

欧几里德算法如下：

欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。这是数论和代数学中的重要方法。从整数的除法可知：对任给二整数a，b0，必有二整数q及r存在，使得a=qb+r，0≤rb，并且q及r是唯一存在的，这是数论的一条基本定理。

整数的一系列重要性质都可以由此得到，如果反复利用这一基本定理，就可以得到因为每进行一次除法，余数就至少减一，而b是有限的正整数，所以最多进行b次，总可以得到一个余数是零的等式，即rn+1=0。上面的方法叫做欧几里德算法。

定理：gcd（a，b）=gcd（b，amodb），证明：a可以表示成a=kb+r，则r=amodb，假设d是a，b的一个公约数，则有da，db，而r=a-kb，因此dr，因此d是（缺帆b，amodb）的公约数，假设d是（b，amodb）的公约数，则db，dr，但是a=kb+r，因此d也是（a，b）的公约数。胡扮孝

欧几里德算法的Stein版：

欧几里德算法是计算两个数最大公约数的传统算法，他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。考虑现在的硬件平台，一般整数最多也就是64位，对于这样的整数，计算两个数之间的模是很简单的。

对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模。

用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数裤稿的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两巧茄个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

辗转相除法的算法步骤为，两个数中用较大数除以较小数，再用出现的余数除除数。

再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。

辗转相除法是利用以下性质来确定两个正整数a和b的最大公因子的：

1、若r是a ÷ b的余数，且r不为0，则gcd(a,b) = gcd(b,r)。

⒉、a和其倍数之最大公因子为a。

另一种写法是：

⒈、令r为a/b所得余数（0≤r），孝斗察销空若r= 0，算法结束；b即为答案。

⒉、互换：置a←b，b←r，并返回第一步。

---