欧几里得算法及其扩展应用详解
1. 欧几里得算法
欧几里得算法用于计算两个数的最大公约数（gcd），其伪代码如下：
r ← a, r′ ← b, e ← 0 while 2 | r and 2 | r′ do r ← r/2, r′ ← r′/2, e ← e + 1 repeat while 2 | r do r ← r/2 while 2 | r′ do r′ ← r′/2 if r′ < r then (r, r′) ← (r′, r) r′ ← r′ − r until r′ = 0 d ← 2^e · r output d该算法的时间复杂度为 $O(\ell^2)$，其中 $\ell = \max(\text{len}(a), \text{len}(b))$。
2. 扩展欧几里得算法
扩展欧几里得算法不仅能计算两个非负整数 $a$ 和 $b$ 的最大公约数 $d$，还能找到整数 $s$ 和 $t$，使得 $as + bt = d$。
定理 4.3：
- 定义整数序列 $s_i$ 和 $t_i$ 如下：
- $s_0 := 1, t_0 := 0, s_1 := 0, t_1 := 1$
- 对于 $i = 1, \ldots, \ell$，$s_{i + 1} :=
- 定义整数序列 $s_i$ 和 $t_i$ 如下：
