欧几里得算法

定义

欧几里得算法(Euclidean Algorithm),即辗转相除法,用于计算两个整数的最大公约数(GCD),记载于公元前约 300 年欧几里得的《几何原本》,被认为是最古老的仍在使用的算法之一。

原理

基于恒等式 gcd(a, b) = gcd(b, a mod b):反复用较小数去除较大数并取余,直到余数为 0,此时的除数即为最大公约数。最坏情况出现在相邻斐波那契数上,复杂度为 O(log min(a,b))。二进制 GCD(Stein 算法)用移位和减法替代取模,适合某些硬件环境。

扩展欧几里得算法

在求 GCD 的同时求出系数 x、y 使 ax + by = gcd(a, b),用于求模逆元、解线性同余方程与中国剩余定理,是 RSA 等公钥密码算法中密钥计算的基础步骤。

应用

分数化简、最小公倍数计算、密码学、同余方程求解与计算机代数系统。