3

我试图找到一种uint64_t在不支持 128 位整数的系统上使用 C 实现 EEA 的方法。问题在于，似乎总是存在某个变量或另一个变量会溢出的情况，从而产生不正确的结果。

我知道它可以用 /signed/ 机器字来完成，这里和其他地方有很多答案可以为此提供伪代码。可以用无符号且没有溢出来完成吗？还是您需要更大的整数大小？

4

2 回答 2

4

欧几里得算法中的系数在符号上交替出现（在初始零消失后），因此我们可以仅使用幅度来计算它们，并在最后从迭代奇偶校验中重建符号。

扩展欧几里得算法求正互质整数u和v的乘法逆a和b。也就是说，我们发现a和b使得a •<em>u 与 1 模v一致，并且b •<em>v 与 1 模u一致。我们从两个方程开始：

  • u = 1•<em>u + 0•<em>v。
  • v = 0•<em>u + 1•<em>v。

那么算法是：

  • 设x和y是最新的两个方程的左边（y是最新的）。
  • 如果y为 1，我们就完成了。右侧的u和v的系数分别是u和v的倒数。
  • 否则，令q为整数商x除以y。追加一个等于第一个方程减去第二个方程乘以q的新方程。

这在方程的左边实现了欧几里得算法，所以我们知道它以 1 终止于相对素数u和v。那么最后一个方程的形式为：

  • 1 = a •<em>u + b •<em>v。

在此，很明显a是u模v的乘法逆，b是b模u的乘法逆。

观察到在第三个等式中，u的系数将为 1−0•<em>q。因此，它将是积极的。v的系数为0−1•<em>q。因此，它将是负面的。在第四个等式中，u的系数为正。从那时起，我们总是从一个正数中减去一个负数，或者从一个负数中减去一个正数，因此我们交替使用符号。

在第n个等式中，如果n为奇数，则u的系数为非负，如果n为偶数，则为非正，反之亦然。

因此，我们可以通过仅保留系数的大小来使用无符号算术来实现这一点：

  • 给定已知非负系数的大小g和已知非正系数的大小h，计算新的大小为g + h •<em>q。
  • 给定已知非正系数的大小g和已知非负系数的大小h，计算新的大小为g + h •<em>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的系数或u的系数的v ，但无法获得该证明。（它嵌入到前雇主的源代码中。）

于 2021-04-14T19:19:59.590 回答
0

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 来固定幅度的符号。

于 2021-12-27T23:28:15.030 回答