c++ - 从两个4x64位整数数组获取模

我使用OpenCL进行GPGPU编程，但是不幸的是，没有 native 256位整数支持。我决定将256位整数分成四个64位整数。基本操作的很好解决方案，但是如何获得它们的模数呢？

我需要这样做:

(uint256) % (uint256)

但是使用OpenCL，我只能拥有:

[ (uint64), (uint64), (uint64), (uint64) ] % [ (uint64), (uint64), (uint64), (uint64) ]

那么我该如何实现呢？我应该使用哪种算法，最重要的是-最容易实现的算法是什么？

附言对于公钥加密，我需要它。

编辑:我既没有实现加法，也没有实现减法。

最佳答案

这是一个简单(相当有效)的算法，仅使用减法，乘以2，除以2和比较(所有这些对于uint256都很容易实现)来计算a % b。

uint256 modulo(uint256 a, uint256 b) {
  int i = 0;
  while (b <= a) {
    b = b * 2; // watch out for overflow!
    i++;
  }
  while (i--) {
    b = b / 2;
    if (b <= a) {
      a = a - b;
    }
  }
  return a;
}

这是一个例子:

start: a = 40, b = 7
i = 1, a = 40, b = 14
i = 2, a = 40, b = 28
i = 3, a = 40, b = 56

i = 3, b = 28, a = 40 - 28 = 12
i = 2, b = 14, a = 12 (b > a so nothing happens)
i = 1, b = 7, a = 12 - 7 = 5
i = 0, so we stop and return a = 5

编辑:为什么这有效？
如果满足以下条件，则可计算模余数的简单方法:

int modulo(int a, int b) {
  while (a >= b) {
    a -= b;
  }
  return a;
}

提出的解决方案使用相同的想法，但是效率更高。我们知道，最终我们将从b中减去a精确地达到k时间。通过我们我们不知道k的值。 k可以二进制形式表示为2^0 * k_0 + 2^1 * k_1 + 2^2 * k_2 + ...。该算法从2 ^ i的最大值开始，尝试减去2^i * b。因此，我们实现了对数时间复杂度，而不是线性。

免责声明:我不会使用此实现，而是真正的密码实现，因为它容易受到旁道攻击(不同的执行时间取决于输入)。