Неправильное умножение / деление в поле Галуа (2 ^ 8)

Я пытаюсь реализовать умножение и деление в 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;
}

/ Оператор реализован с использованием /= переопределите выше, так что ничего особенного там не происходит.

Я проверил, что сгенерированные таблицы log / exp верны.

Что мне здесь не хватает? Спасибо!

1

Решение

Сначала внимательно прочитайте этот вопрос и все его ответы и комментарии:

Сложение и умножение в поле Галуа

Я думаю, что ваш код в порядке, но у вас есть две проблемы.

Во-первых, комментарии неверны; Вы держите показатель в диапазоне 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)); работает. Это не имеет ничего общего с вашим обычным представлением, что пять раз три равно пятнадцати. Точно так же и для других ваших рабочих тестовых случаев, которые вы заметите, в основном включают степени два.

Однако «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)); Вы должны найти это проверить.

4

Другие решения

x % n оценивается как целое число от 0 до (n — 1) включительно.

Это означает, что x % 255 оценивается как целое число от 0 до 254, а не от 0 до 255.

Вы должны заменить 255 на 256 или, альтернативно, выполнить побитовое И с 0xff за тот же результат. Последний работает быстрее, хотя вполне вероятно, что компиляторы достаточно умны, чтобы оптимизировать их под один и тот же байт-код.

0

В коде нет ничего плохого. Умножение / деление конечных полей отличается от обычной арифметики. Пожалуйста, обратитесь к этот вопрос в криптостексе

0
По вопросам рекламы [email protected]