Как сохранить значение умножения в пределах конечного диапазона полей? Я реализую умножение GF(8)
Я реализую умножение GF(8). Примитивный полином - это x^3 + x + 1. Я знаю основы: если умножение переполняется, я могу переписать его с помощью своего примитивного полинома и вывести его в область конечного поля.
Однако проблема возникает, когда переполнение происходит более чем на один бит. Например: правильный результат: альфа ^3(011) * альфа ^2(100) в двоичных результатах 12(1001). Продукт переполнен и, следовательно, выполнение XOR с примитивным полиномом дает правильное значение, то есть альфа ^5(111).Неверный результат: alpha ^ 5 (111) * alpha ^ 3 (011) в двоичных результатах 21(10101). Здесь результат переполняется на два бита, и выполнение XOR с примитивным полиномом не дает правильного результата.
Что мне не хватает?
1 ответ
Умножение GF - это полиномиальное умножение, поэтому нет переносов. Таким образом, 111 * 011 = 1001 и 1001 по модулю 1011 равно 010. Однако рассмотрим случай 100 * 100 = 10000. В этом случае вам необходимо выполнить два шага "деления" (аналогично вычислению CRC с использованием двоичной математики низкого уровня, вместо которой используется XOR вычитать).
10
-------
1011 | 10000
1011
----
110
000
---
110
Итак, 100 * 100 мод 1011 = 110.
Вы можете создать таблицу antilog и таблицу журнала. Для этого поля GF(8) = GF(2^3), основанного на x^3 + x + 1, все 7 ненулевых чисел имеют степень 1x + 0 (hex 2):
0 1 2 3 4 5 6 antilog table
001 010 100 011 110 111 101
001 010 011 100 101 110 111 log table
0 1 3 2 6 4 5
Используя таблицы, a*b = alog((log(a) + log(b))%7). 100*100 = alog((log(100)+log(100))%7) = alog((2+2)&7 = alog(4) = 110. 110*111 = alog((log(110)+log) (111))%7) = alog((4+5)%7) = alog(2) = 100.
Вы можете устранить необходимость в% 7, удвоив таблицу antilog, таблица журнала останется прежней:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 antilog table
001 010 100 011 110 111 101 001 010 100 011 110 111 101
a * b = alog (log (a) + log (b)). Также для деления: a/b = alog(7+log(a)-log(b)).