Extended Euclidean Algorithm
扩展欧几里得算法在计算 gcd(a,b) 的同时求 Bezout 系数 x,y 使 ax+by=gcd(a,b)。
用途
求模逆元与解线性 Diophantine 方程，是数论与密码学基础工具。
机制
在欧几里得算法回溯过程中维护系数：gcd(a,b)=gcd(b,a mod b)，回代时 x=y_prev, y=x_prev-floor(a/b)*y_prev。时间复杂度 O(log min(a,b))。
用例
- 模逆元计算
- RSA 密钥生成
- 线性 Diophantine 方程