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

Question

我使用 OpenCL 进行 GPGPU 编程，但不幸的是没有原生 256 位整数支持。我决定将 256 位整数分成四个 64 位整数。基本操作的很好的解决方案，但我怎样才能得到它们的模数？

我需要这样做:

(uint256) % (uint256)

但是使用 OpenCL，我只能有这个:

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

那么我怎样才能做到这一点呢？我应该使用什么算法，最重要的是 - 什么是最容易实现的？

附言我需要公钥密码学。

编辑 : 我没有实现加法和减法。

Answer 1

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

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 .多亏了这一点，我们实现了对数时间复杂度而不是线性。

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