7、欧几里得算法及其扩展应用详解

欧几里得算法及其扩展应用详解

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} :=