我正试图找到一种方法，在不支持128位整数的系统上，使用C中的uint64_t实现EEA。问题是，似乎总有一种情况，某个变量或另一个变量会溢出，产生不正确的结果。
我知道这可以用/签名/机器词来完成，这里和其他地方有很多答案可以给出伪代码。它可以用无符号和无溢出来完成吗？或者您需要一个更大的整数大小吗？
欧几里得算法中的系数符号交替(在初始零消失后(，因此我们可以仅使用幅度来计算它们，并在迭代奇偶性结束时重建符号。
扩展欧几里得算法找到正相对素数u和v相对于彼此的乘法逆a与b。也就是说，我们发现a和b使得a•u与1模v一致，并且b·v则与1模u一致。我们从两个方程开始：
- u=1•u+0•v
- v=0•u+1•v
则算法为：
- 设x和y是最近两个方程的左侧(y在后面(
- 如果y为1，则结束。右侧的u和v的系数分别是u与v
- 否则，设q为x除以y的整数商。附加一个新方程式，该方程式等于前面的方程式减去后面的方程式乘以q
这在方程的左侧实现了欧几里得算法，所以我们知道它在相对素数u和v的情况下终止于1。最后一个方程的形式是：
- 1=a•u+b·v
在这一点上，很明显a是u模v的乘性逆，b则是bu模的乘法逆。
注意，在第三个方程中，u的系数将为1−0•q。因此，这将是积极的。v的系数为0−1•q。因此，它将是负面的。在第四个方程中，u的系数为正。从那时起，我们总是从正数中减去负数，或者从负数中减去正数，因此我们交替符号。
在nth方程中，如果n是奇数，则u的系数是非负的，如果n是偶数，则u的系数不是正的，反之亦然。
因此，我们可以通过只保留系数的大小来使用无符号算术来实现这一点：
- 给定已知非负系数的幅值g和已知非正系数的幅值h，计算新幅值为g+h•q
- 给定已知非正系数的幅值g和已知非负系数的幅值h，计算新幅值为g+h•q
13和10的示例：
- 13=1•13+0•10
- 10=0•13+1•10
- 13/10的商是1。计算13−1•10=3，1+0•1=1，0+1•1=1。这样可以：
- 3=1•13−1•10。(符号是隐式已知的，而不是计算的。(
- 10/3的商是3。计算10−3•3=1，0+1•3=3，1+1•3=4。这样可以：
- 1=−3•13+4•10
在这一点上，我们用来保持u(13(的系数的任何变量都包含3，但我们知道它是负的，因为我们处于偶数迭代(第四次(中。因此u的倒数是−3。如果需要，我们可以添加u(计算为u减去存储的幅度(以获得正结果。
我已经证明，对于u的系数，这些计算永远不会超过v，或者对于v
Eric Postpischil是绝对正确的，但答案很难阅读，尤其是如果你正在寻找有效的代码，那么就来吧：
template<typename T>
typename std::enable_if<std::is_unsigned<T>::value,tuple<T,T>>::type
constexpr extended_euclidean(const T a, const T b)
{
T r0 = a;
T r1 = b;
T s0 = 1;
T s1 = 0;
T t0 = 0;
T t1 = 1;
size_t n = 0;
while (r1) {
T q = r0 / r1;
r0 = r0>q*r1?r0-q*r1:q*r1-r0; swap(r0,r1);
s0 = s0+q*s1; swap(s0,s1);
t0 = t0+q*t1; swap(t0,t1);
++n;
}
// gcd = r0
if (n%2) s0=b-s0;
else t0=a-t0;
return tuple<T,T>({s0,t0});
}
所以基本上我们在做标准的欧氏算法，但在计算余数时，我们只关心幅度，在更新系数时，我们可以添加。幅度的符号最终需要使用奇偶校验，使用计数器n来固定。