扩展欧几里德算法

一种确定两个单变量多项式的贝祖等式系数和多项式最大公因数的方法，称为“扩展欧几里得算法”。

当a和b互质时，扩展欧几里得方法非常有用。因此，两种扩展欧几里得算法都被广泛应用于密码学中。

描述

普通的欧几里得算法由一系列欧几里得除法组成，其商不被使用。只保留余数。后续的商在扩展过程中被使用。更具体地说，使用a和b作为输入，普通的欧几里得算法计算一系列商（q1,.., qk）和余数（r0,.., rk+1），使得。

欧几里得除法的基本特征是，右侧的不等式以唯一的方式从ri-1和ri确定qi和ri+1。

当计算结束，得到零余数时，最后的非零余数rk就是最大公约数。

扩展欧几里得方法遵循类似的路径，但增加了两个额外的序列。

当rk+1 = 0时，计算也停止并给出

• 输入变量a = r0和b = r1的rk是它们的最大公约数。
• Sk和tk，或者gcd(a,b) = rk = ask + btk，是贝祖系数。
• 由给出，它们是a和b被它们的最大公因子除得到的商。

此外，如果gcd(a,b) /= min(a,b)，并且a和b都为正，

则小于等于x的最大整数，其中|x|表示x的整数部分。对于0 = i = k。

作为满足上述两个条件的唯一一对，扩展欧几里得方法提供的贝祖系数对是最小的贝祖系数对。

此外，它表明该技术可以通过计算机程序实现，使用大于a和b的预定大小的数字，而不会发生整数溢出。

示例

下表展示了使用输入240和46时扩展欧几里得算法的进展。“余数”列中的最后一个非零值2是最大公约数。第6行的余数为零。因此，计算在此处结束。倒数第二行的最后两项是贝祖系数。很容易验证9 * 240 + 47 * 46 = 2。

使用多项式的扩展欧几里得算法

第一个区别是，在欧几里得除法和算法中，必须使用次数不等式deg ri+1 < deg ri，而不是不等式0 <= ri+1 < |ri|。否则，前面段落中的任何内容都没有改变；改变的只是用多项式代替了整数。

另一个区别是，扩展欧几里得算法对贝祖系数的大小有限制，这在多项式情况下更为精确，并得到以下结果。

如果a和b是两个非零多项式，扩展欧几里得方法生成一对特定的多项式(s, t)，使得as + bt = gcd(a,b)。

有几种方法可以确定最大公因数。

在数学中，通常要求最大公约数是单项式。将每个输出元素除以rk的首项系数即可得到。如果a和b互质，这使得贝祖等式的右侧为1。否则，可以得到任何非零常数。由于计算机代数中的多项式经常包含整数系数，因此通过这种方法将最大公约数归一化会引入过多的分数，以至于不实用。

将每个输出元素除以rk的首项系数即可得到。如果a和b互质，这使得贝祖等式的右侧为1。否则，可以得到任何非零常数。由于计算机代数中的多项式经常包含整数系数，因此通过这种方法将最大公约数归一化会引入过多的分数，以至于不实用。

归一化还产生了输入多项式互质的最大公约数为一。

第三，我们通过类似于扩展欧几里得算法从原始子结果伪余数序列算法中扩展子结果伪余数序列方法。从整数系数开始，使得所有计算出的多项式都具有整数系数。此外，每个计算出的余数ri都是一个多项式的子结果。对于这种贝祖恒等式的解释，方程没有分母。通过将所有内容除以结果，可以得到常规的贝祖恒等式，其是有理数的一个不同公分母。

从整数系数开始，使得所有计算出的多项式都具有整数系数。此外，每个计算出的余数ri都是一个多项式的子结果。对于这种贝祖恒等式的解释，方程没有分母。通过将所有内容除以结果，可以得到常规的贝祖恒等式，其是有理数的一个不同公分母。

伪代码

首先，应该注意的是，在实现上述算法时，每一步都需要索引变量的两个最新值。因此，为了节省内存，每个索引变量必须被替换为仅仅两个变量。

以下算法以及本文中的其他算法为了简洁起见，使用了并行赋值。在不支持此功能的编程语言中，必须使用辅助变量来模拟并发赋值。

例如，第一个

等同于

其他并行赋值同理。这导致了以下代码

当除以a和b及其GCD时，结果可能不正确。这在计算完成后很容易修复，但为了代码简洁起见，在此尚未进行。与前面的例子一样，如果a或b为零且另一个为负，则必须改变所有输出符号。在这种情况下，输出的最大公约数也是有害的。

在贝祖恒等式axe + by = gcd(a,b)中，如果a、b、x和gcd(a,b)已知，则y可以求解。通过仅计算sk序列可以获得贝祖系数x，这是对以下算法的改进

这表明“优化”是用一个计算时间比它所替换的操作更长的单一操作替换了一系列小的整数乘法和除法。可以通过替换前面伪代码的三个输出行如下行来创建这个规范化的约简版本。

因为s和t是两个互质数，所以+ bt = 0，依此类推，该过程的证明依赖于这个事实。移动负号以表示正分母是获得简化规范版本所必需的。

如果b整除，则算法执行一次迭代，结果为s = 1。

利用模框架计算乘法逆元。

灵活整数

如果n是正整数，则由n的欧几里得除法得到的余数集称为环Z/nZ。加法和乘法运算涉及将整数相加和相乘的结果除以n。如果Z/nZ中的一个元素an与n互质，则它具有乘法逆元（即它是单位），否则不具有。

因此，a模n的乘法逆元是t，或者更准确地说，是t除以n的余数。

要将扩展欧几里得方法应用于此问题，应注意不需要计算第n个贝祖系数。此外，可以利用过程产生的整数t满足|t| < n这一事实，以获得一个大于零且小于n的结果。换句话说，如果t < 0，则最终必须加上n。这生成了伪代码，其中n是大于1的整数。

扩展欧几里得算法是在计算简单代数域扩张中的乘法逆元的主要方法。非素数阶的有限域在密码学和编码理论中经常使用。

计算模乘法逆元的步骤与之前类似。有两个显著的变体：第一，最后一行不是必需的，因为给出的贝祖系数的次数总是小于d。第二，当输入多项式互质时，K中的任何非零成员都可以作为最大公约数；因此，这个贝祖系数（通常是具有正次数的多项式）必须乘以K中的该元素的逆。多项式p和多项式an是以下伪代码中的多项式。

有两个显著的变体：第一，最后一行不是必需的，因为给出的贝祖系数的次数总是小于d。第二，当输入多项式互质时，K中的任何非零成员都可以作为最大公约数；因此，这个贝祖系数（通常是具有正次数的多项式）必须乘以K中的该元素的逆。多项式p和多项式an是以下伪代码中的多项式。

示例

例如，如果a = x^6 + x^4 + x + 1是需要求逆元的元素，p = x^8 + x^4 + x^3 + x + 1是用于创建有限域GF(2^8)的多项式，那么使用该技术可以得到下表中所示的计算。对于域中的每个元素z，在阶为2n的域中存在z + z = 0。由于GF(2)中的唯一非零元素是1，因此不需要修改伪代码的最后一行。

通过将两个分量相乘，然后将余数乘以p，可以证明其逆为x^7 + x^6 + x^3 + x。

多于两个整数

可以通过迭代处理多个数字的情况。我们首先证明gcd(a, b, c) = gcd(gcd(a, b), c)。令d = gcd(a, b, c)来证明这一点。根据gcd的定义，d是a和b的约数。因此，对于某个k，gcd(a, b) = kd。与d整除c类似，c等于jd，其中j是某个值。假设u = gcd(k, j)。根据我们构造u的方法，ud整除a、b和c，但由于d是u的最大约数，所以u是单位。因为ud = gcd(gcd(a, b), c))，结论得证。

可以通过迭代处理多个数字的情况。我们首先证明gcd(a, b, c) = gcd(gcd(a, b), c)。令d = gcd(a, b, c)来证明这一点。根据gcd的定义，d是a和b的约数。因此，对于某个k，gcd(a, b) = kd。与d整除c类似，c等于jd，其中j是某个值。假设u = gcd(k, j)。根据我们构造u的方法，ud整除a、b和c，但由于d是u的最大约数，所以u是单位。因为ud = gcd(gcd(a, b), c))，结论得证。

多于两个整数

可以通过迭代处理多个数字的情况。我们首先证明gcd(a, b, c) = gcd(gcd(a, b), c)。令d = gcd(a, b, c)来证明这一点。根据gcd的定义，d是a和b的约数。因此，对于某个k，gcd(a, b) = kd。与d整除c类似，c等于jd，其中j是某个值。假设u = gcd(k, j)。根据我们构造u的方法，ud整除a、b和c，但由于d是u的最大约数，所以u是单位。因为ud = gcd(gcd(a, b), c))，结论得证。