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

Question

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

我需要这样做：

(uint256) % (uint256)

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

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

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

附言我需要它进行公钥加密。

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

Answer 1

这是一个简单(且相当有效(的算法，它仅使用减法、乘以 2、除以 2 和比较来计算a % b(所有这些都很容易为您的 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;
}

提出的解决方案使用相同的想法，但方式更有效。我们知道，我们最终会从a确切的k时间中减去b。通过我们不知道k的价值.k可以用二进制表示为2^0 * k_0 + 2^1 * k_1 + 2^2 * k_2 + ...。该算法从 2^i 的最大值开始，并尝试减去2^i * b。多亏了这一点，我们实现了对数时间复杂度而不是线性。

免责声明：我不会使用此实现是真正的加密实现，因为它容易受到侧信道攻击(根据输入的不同执行时间(。