Я пытаюсь реализовать умножение и деление в 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 верны.
Что мне здесь не хватает? Спасибо!
Сначала внимательно прочитайте этот вопрос и все его ответы и комментарии:
Сложение и умножение в поле Галуа
Я думаю, что ваш код в порядке, но у вас есть две проблемы.
Во-первых, комментарии неверны; Вы держите показатель в диапазоне 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));
Вы должны найти это проверить.
x % n
оценивается как целое число от 0 до (n — 1) включительно.
Это означает, что x % 255
оценивается как целое число от 0 до 254, а не от 0 до 255.
Вы должны заменить 255 на 256 или, альтернативно, выполнить побитовое И с 0xff
за тот же результат. Последний работает быстрее, хотя вполне вероятно, что компиляторы достаточно умны, чтобы оптимизировать их под один и тот же байт-код.
В коде нет ничего плохого. Умножение / деление конечных полей отличается от обычной арифметики. Пожалуйста, обратитесь к этот вопрос в криптостексе