伽罗瓦域 GF(4) 中乘法的恒定时间

Question

Tl; dr：有没有办法以任何方式（包括多线程）改进下面的代码，因为代码将运行数千亿次？

目标是找到一个恒定时间算法（没有for 循环）以在 Galois Field GF(4) 中执行乘法。我不确定这是否可行，但值得一试。

一些背景：乘法在GF（2）或基体2是等效的安定被相乘的两个值。这是因为：

一种	乙	a × b = a ? 乙
0	0	0
0	1	0
1	0	0
1	1	1

例如：

10101011010100 × 10011000101101 = 

10101011010100 
10011000101101 ?
--------------
10001000000100

当涉及到GF（4）中，有可以使用的四个不同的符号：0，1，2和3这是不一样基座4执行乘法，因为一些数字不给时相乘的一个预期的结果按其他数字。它们在下表中以粗体显示：

一种	乙	一 × 乙
0	0	0
0	1	0
0	2	0
0	3	0
1	0	0
1	1	1
1	2	2
1	3	3
2	0	0
2	1	2
2	2	3
2	3	1
3	0	0
3	1	3
3	2	1
3	3	2

可以使用以下乘法表总结上表的更紧凑形式：

×	0	1	2	3
0	0	0	0	0
1	0	1	2	3
2	0	2	3	1
3	0	3	1	2

我们可以用二进制写出四位数字中的每一个，因为乘法将对值的二进制表示进行：

数字	二进制表示
0	00
1	01
2	10
3	11

在 GF(4) 中，乘法是通过逐位相乘而不带进位来完成的。例如：

21302032 × 31012233 = 

21302032
31012233 ×
--------
11003021

我们可以使用值的二进制表示并执行乘法：

21302032 = 1001110010001110 in binary
31012233 = 1101000110101111 in binary
11003021 = 0101000011001001 in binary

1001110010001110
1101000110101111 ×
----------------
0101000011001001

最后，这是一个执行乘法的工作 java 代码的实现。但是，它使用 for 循环，目标是提出恒定时间算法：

10101011010100 × 10011000101101 = 

10101011010100 
10011000101101 ?
--------------
10001000000100

有算法吗？如果没有，是否有一些改进可以帮助我的逻辑（也许是一种有效的多线程方法）？

Answer 1

问题的答案“可以使用公式（没有 for 循环）来实现结果吗？” 是是的。

这是一些代码。它在 Python 中，但它应该直接转换为 Java，无需进行重大修改。示例和解释遵循代码。它的编写假设 64 位整数编码 GF(4) 的 32 个元素 - 如果您想要 32 位整数，请使用MASKof0x5555_5555代替。

#: Mask to extract the low-order bit of each GF(4) element.
MASK = 0x5555_5555_5555_5555


def gf4_vector_multiply(i, j):
    """
    Vector multiply in GF(4).

    i and j are 64-bit integers, each of which encodes 32 elements
    of GF(4) in pairs of consecutive bits.

    The returned value represents the 32 products of the GF(4) elements,
    encoded as a 64-bit integer in the same way.
    """
    ii = i >> 1
    jj = j >> 1
    r0 = (ii & jj) ^ (i & j)
    r1 = (ii & j) ^ (jj & i) ^ (ii & jj)
    return ((r1 & MASK) << 1) ^ (r0 & MASK)

例子

这是应用于您给出的示例的上述函数，将 21302032 和 31012233 相乘得到 11003021：

>>> i = int("21302032", base=4)
>>> j = int("31012233", base=4)
>>> product = gf4_vector_multiply(i, j)
>>> product == int("11003021", base=4)
True

解释

我们分别计算每个乘积的低位（r0在上面的代码中）和高位（r1），然后将它们组合起来。

对于产品的低位，我们有下表（从问题中的表中复制，但将2s和3s替换为0s和1s）：

×	0	1	2	3
0	0	0	0	0
1	0	1	0	1
2	0	0	1	1
3	0	1	1	0

此表中的值是以下两个表中相应值的按位异或：

×	0	1	2	3
0	0	0	0	0
1	0	1	0	1
2	0	0	0	0
3	0	1	0	1

和

×	0	1	2	3
0	0	0	0	0
1	0	0	0	0
2	0	0	1	1
3	0	0	1	1

这两个表中的第一个只是输入（i & j在代码中）的低位的按位与，而第二个是输入（在代码中）的高位的按位与ii & jj。所以(ii & jj) ^ (i & j)给了我们结果的低位。高阶位r1的构造类似。

注意的有趣的部分r0和r1在每对，即，在低序位r0 & 0x55555555和r1 & 0x55555555。每对 ( r0 & 0xaaaaaaaaand r1 & 0xaaaaaaaa)的高阶位没有用：它们的值包含混合连续 GF(4) 位的结果，这不是我们想要的，所以我们必须小心地将这些位屏蔽掉重新组装结果。

优化

我没有做太多努力来最小化这里的按位运算；可能有一些空间可以减少位操作的总数。上面的代码使用了 14 个操作。这是一个不太清楚的变体，但使用了 12 个操作。需要注意的是正常的运算符优先级规则（包括使用Java和Python）的，则对圆括号所有，但一个是多余的：我发现代码的可读性与括号，但如果你认为它看起来更好的是随意带他们出去道路。

def gf4_vector_multiply(i, j):
    """
    Vector multiply in GF(4).

    i and j are 64-bit integers, each of which encodes 32 elements
    of GF(4) in pairs of bits.

    The returned value represents the 32 products of the GF(4) elements,
    encoded in the same way.
    """
    ii = (i >> 1) & MASK
    jj = (j >> 1) & MASK
    return (((ii & j) ^ (jj & i)) << 1) ^ (ii & jj) ^ (i & j)

另外，正如您所建议的，如果您有一个令人尴尬的并行问题，那么使用多线程可能会有所帮助，但我认为这确实是对单独的 Stack Overflow 问题的调查。在现代 CPU 上，上面的代码很可能足够简单，瓶颈在于将数据传入和传出 RAM 而不是计算。

特例 n = 1

在评论中，作者询问了有关个位数乘法的问题。对于一位数乘法，还有其他技巧可用。这是一种可能性（再次在 Python 中，但它应该再次直接转换为 Java）：

def gf4_scalar_multiply(i, j):
    return (0x813e4 >> 2*i*j) & 3

在这里，我们简单地将乘积值以位对的形式编码在魔术常数 中0x813e4，以 4 为基数是2001033210。现在我们使用移位来查找给定整数乘积的合适的基数为 4 的乘积。

让我们检查一下这是否给出了预期的乘法表：

>>> for i in range(4):
...     for j in range(4):
...          print(gf4_scalar_multiply(i, j), end=" ")
...     print()
... 
0 0 0 0 
0 1 2 3 
0 2 3 1 
0 3 1 2