Как сохранить значение умножения в пределах конечного диапазона полей?Я реализую умножение GF (8) - PullRequest
Новая
       63

Как сохранить значение умножения в пределах конечного диапазона полей?Я реализую умножение GF (8)

0 голосов
/ 28 января 2019

Я использую умножение 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 Ответ

0 голосов
/ 28 января 2019

Умножение GF - это полиномиальное умножение, поэтому нет переносов.Таким образом, 111 * 011 = 1001 и 1001 по модулю 1011 равно 010. Однако рассмотрим случай 100 * 100 = 10000. В этом случае вам необходимо выполнить два шага «деления» (аналогично вычислению CRC с использованием двоичной математики низкого уровня, вместо которой используется XORвычитать). 

          10
     -------
1011 | 10000
       1011
       ----
         110
         000
         ---
         110

Итак, 100 * 100, мод 1011 = 110.

Вы можете создать таблицу антилогов и таблицу журналов.Для этого поля 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 (б)).

...