2

我正在尝试使用对数和指数表在 GF(2^8) 中实现乘法和除法。我使用 3 的指数作为生成器，使用来自此处的说明。

但是我失败了一些琐碎的测试用例。

例子：

//passes  
assert((GF256elm(4) / GF256elm(1)) == GF256elm(4));  
assert((GF256elm(32) / GF256elm(16)) == GF256elm(2));  
assert((GF256elm(15) / GF256elm(5)) == GF256elm(3));  
assert((GF256elm(88) / GF256elm(8)) == GF256elm(11));  
//fails, but should pass
assert((GF256elm(77) / GF256elm(11)) == GF256elm(7));
assert((GF256elm(77) / GF256elm(7)) == GF256elm(11));

前四行通过，但在第 5 行和第 6 行均失败。
经过进一步调查，我发现这些错误发生在“换行”时，即log3(a) + log3(b) > 255（乘法情况）或log3(a) - log3(b) < 0. 然而，该值是“修改”的，因此它们使用真实模数保持在 0~255 之间。

GF256elm& GF256elm::operator/=(const GF256elm& other) { //C++ operator override for division
    int t = _logTable[val] - _logTable[other.val]; //log3(a) - log3(b)
    int temp =  ((t % 255) + 255) % 255; //this wraps the value to between 0~254 inclusive.
    val = _expTable[temp];
    return *this;
}

运算符/是使用/=上面的覆盖实现的，所以那里没有什么特别的事情发生。

我检查了生成的日志/exp 表是否正确。

我在这里想念什么？谢谢！

4

3 回答 3

4

首先，仔细阅读这个问题及其所有答案和评论：

伽罗瓦域中的加法和乘法

我认为您的代码还可以，但是您有两个问题。

一是评论错误；您将指数保持在 0-254 范围内，而不是 0-255 范围内。

其次，您的“琐碎”测试用例是错误的。

在这个领域，将数字视为多项式，其系数可以从数字的二进制表示中获得。例如，由于 5 = 2^2 + 1，因此在此字段中，“5”表示 x^2 + 1。

所以“5” * “3” = (x^2 + 1) * (x + 1) = x^3 + x^2 + x + 1，或“15”。这就是您的测试用例assert((GF256elm(15) / GF256elm(5)) == GF256elm(3));有效的原因。这与你通常认为的五乘三等于十五无关。同样，对于您的其他工作测试用例，您会注意到它们主要涉及 2 的幂。

然而，“7” * “11” = (x^2 + x + 1) * (x^3 + x + 1) = x^5 + x^4 + 2x^3 + 2x^2 +2x + 1

但是系数都是模 2，所以这实际上是 x^5 + x^4 + 1 = "49"。这就是你最后两个测试用例失败的原因。

如果你尝试assert(GF256elm(49) / GF256elm(7) == GF256elm(11));，你应该会发现它检查出来。

于 2013-08-26T00:30:46.770 回答
0

代码没有问题。有限域乘法/除法不同于普通算术。请参考 cryptostackxchange 中的这个问题。

于 2013-08-26T00:14:08.423 回答
0

x % n计算结果为 0 和 (n - 1) 之间的整数，包括 0 和 (n - 1)。

这意味着x % 255计算结果为 0 到 254 之间的整数，而不是 0 到 255。

您应该将 255 替换为 256，或者执行按位与 with0xff以获得相同的结果。后者更快，尽管编译器很可能足够聪明，可以将它们优化为相同的字节码。

于 2013-08-25T11:19:26.187 回答