扩展欧几里得算法是一种算法:给定两个整数 a 和 b,计算它们的非负最大公约数 d,并求出整数 x,y,使得
ax+by=d=gcd(a,b).
它在欧几里得算法的基础上,进一步记录每一步的余数如何用原始输入表示。求得的系数称为裴蜀系数,为裴蜀等式提供了构造性的求解方法。该方法是计算数论中的基础工具,尤其适用于求模逆元和解整数方程。
数学基础
对于满足 b>0 的非负整数 a,b,带余除法给出
a=qb+r,0≤r<b.
其中的关键恒等式是
gcd(a,b)=gcd(b,r).
这是因为,一个整数同时整除 a 和 b,当且仅当它同时整除 b 和 a−qb。
因此,反复进行带余除法会得到一个递减的非负余数序列。最后一个非零余数就是最大公约数。
扩展算法还利用了以下事实:每个新余数都是前两个余数的整数线性组合。由于初始值本身已经是 a 和 b 的线性组合,
a=1a+0b,b=0a+1b,
此后的每个余数也都能表示为 sa+tb。持续记录这些系数,最终就能将最大公约数表示成这种形式。
这一方法所依据的除法过程见于几何原本第七卷和第十卷,分别用于整数和量。扩展算法保留了相同的除法步骤,只是增加了系数的记录与更新。
递推与实现
对于正整数输入,初始化为
(r0,s0,t0)=(a,1,0),(r1,s1,t1)=(b,0,1).
每一步先计算
qi=⌊riri−1⌋
再更新
ri+1si+1ti+1=ri−1−qiri,=si−1−qisi,=ti−1−qiti.
这些递推关系始终保持
ri=sia+tib.
当下一个余数为零时,当前的非零余数及其系数就是所求结果。
下面的迭代版本通过对输入的绝对值进行除法运算来处理负数输入:
extended_gcd(a, b):
old_r, r = abs(a), abs(b)
old_s, s = 1, 0
old_t, t = 0, 1
while r != 0:
q = old_r // r
old_r, r = r, old_r - q*r
old_s, s = s, old_s - q*s
old_t, t = t, old_t - q*t
if a < 0:
old_s = -old_s
if b < 0:
old_t = -old_t
return old_r, old_s, old_t
每组成对赋值都是同时进行的:右侧的两个表达式都使用赋值前的变量值。
如果只有一个输入为零,该过程会返回另一个输入的绝对值及相应的系数。按照常见约定 gcd(0,0)=0,对于 (0,0),它也能返回一个成立的等式;不过,有些文献并不定义这两个数的最大公约数。
计算示例
对于 a=240 和 b=46,欧几里得算法中的除法步骤为
240461064=5⋅46+10,=4⋅10+6,=1⋅6+4,=1⋅4+2,=2⋅2+0.
因此,gcd(240,46)=2。
记录各步系数可得:
| 余数 r |
240 的系数 s |
46 的系数 t |
| 240 |
1 |
0 |
| 46 |
0 |
1 |
| 10 |
1 |
−5 |
| 6 |
−4 |
21 |
| 4 |
5 |
−26 |
| 2 |
−9 |
47 |
所以输出为
(d,x,y)=(2,−9,47),
且有
240(−9)+46(47)=2.
也可以从最后一个非零余数开始,通过回代求出相同的系数:
2=6−4=6−(10−6)=2(46−4⋅10)−10=2⋅46−9(240−5⋅46)=−9⋅240+47⋅46.
回代与正向记录系数,是同一代数过程的两种实现方式。
正确性
算法的正确性由以下三个性质保证。
最大公约数保持不变。 每一次替换
(u,v)⟼(v,u−qv)
都不会改变两数的公约数集合。
系数恒等式保持成立。 如果
u=sa+tb,v=s′a+t′b,
那么
u−qv=(s−qs′)a+(t−qt′)b.
因此,存储的每个余数都具有所述的表示形式。
终止性。 非零余数构成一个严格递减的正整数序列,因此最终必然出现零余数。
算法终止时,最后一个非零余数与原始输入具有相同的最大公约数,并且它本身就是这个公约数。与它一同存储的系数给出了所需的恒等式。
矩阵解释
一次更新也可以用矩阵表示:
(riri+1)=(011−qi)(ri−1ri).
更新矩阵的行列式为 −1,因此其逆矩阵的元素也都是整数。将同一个矩阵作用于系数行,就能解释为什么余数计算与系数记录始终同步。
应用
模逆元
在模算术中,整数 a 存在模 m>1 的模乘法逆元,当且仅当
gcd(a,m)=1.
如果算法求得
那么两边对 m 取模可得
ax≡1(modm).
因此,xmodm 就是 a 的一个逆元。
例如,
17(−5)+43(2)=1,
所以 17 模 43 的逆元是
−5mod43=38.
如果算出的最大公约数大于 1,则逆元不存在。
模逆运算用于计算代数和密码学,其中也包括公钥系统所依赖的算术运算。
线性丢番图方程
对于 a,b 不全为零的线性丢番图方程
它有整数解,当且仅当
d=gcd(a,b)
整除 c。
如果算法给出
ax0+by0=d,
则一个解为
xp=x0dc,yp=y0dc.
所有整数解为
x=xp+dbk,y=yp−dak,k∈Z.
特别地,裴蜀系数通常并不唯一。当 c=d 时,这个公式给出了将最大公约数表示为线性组合的所有系数对。
同余式与中国剩余定理
同余式
ax≡c(modm)
等价于整数方程
因此,扩展算法可以判断该同余式是否有解,并构造出解。
它还能求出中国剩余定理的构造性证明及其实现中所需的模逆元。对于模数不互素的情况,可以通过计算最大公约数来判断这些同余式是否相容。
效率与实现限制
令
n=⌈log2(max(∣a∣,∣b∣)+1)⌉
表示以比特数衡量的输入规模。采用大O记号表示,标准算法需要 O(n) 次欧几里得除法。对于给定的输入数值范围,斐波那契数列中的相邻项会使除法次数达到最坏情况。
除法次数并不等同于位运算成本。使用经典整数算术时,标准实现的位复杂度为 O(n2)。更快的分治变体可以达到如下形式的复杂度界:
O(M(n)logn),
其中,M(n) 表示两个 n 比特整数相乘的成本。
迭代实现只需存储固定数量的整数,但这些整数的位数会随输入规模增长;因此,以比特数衡量时,其存储空间并不是常数。
实际实现中的限制包括:
- 溢出: 即使最终结果在固定宽度整数类型的表示范围内,中间计算中的系数乘积也可能超出范围。
- 有符号除法的约定: 使用非负余数,可以避免不同编程语言对负数除法规则的差异。
- 计时信息泄漏: 普通算法的迭代次数和分支取决于输入。在涉及秘密数据的密码学应用中,可能需要专门的常数时间实现。
推广
该方法不仅适用于整数,也可以推广到欧几里得整环,其中存在带余除法,且余数的某种度量会适当地递减。
一个重要例子是域(数学)上的多项式环。给定多项式 f 和 g,扩展算法可以计算出多项式 u,v,d,使其满足
其中 d 是一个最大公约式。由于多项式的最大公约式只在相差一个非零域元素因子的意义下唯一,通常将其规范化为首一多项式。
如果 p 不可约且 f 不被 p 整除,将恒等式规范化为
便可使 u 成为 f 模 p 的逆元。这为用多项式表示的有限域提供了一种有效的求逆方法。
在任意环中,仅仅存在最大公约元并不能保证可以使用这一扩展过程:欧几里得算法还要求存在合适的带余除法运算。