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

Question

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

我需要这样做：

(uint256) % (uint256)

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

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

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

PS我需要公钥密码学。

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

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

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