Алгоритм получения элементов поля GF(2n) в стандартном базисе

 

Для построения элементов поля GF(2n) в стандартном базисе существует следующий алгоритм, использующий сдвиговыерегистры.

На входе: поле GF(2n), заданное полиномом-модулем ψ(x).

 

На выходе: множество найденных элементов поля (получаемых на шаге 2 алгоритма).

Пусть заданы 2 регистра Рг1 и Рг2 длины n+1 - в них запишем:

 

- в Рг1 - коэффициенты полинома-модуля ψ(x);

 

- в Рг2 - константу-единицу 000…001.

 

Предполагается, что нулевой элемент поля равен 000…000. Шаги алгоритма.

1. Пусть текущий номер элемента поля равен j = 1.

 

2. Регистр Рг2 задает элемент поля под номером j.

 

3. Регистр Рг2 сдвигается влево на одну позицию.

 

4. Если старший, n-ый разряд регистра Рг2 равен единице, то выполнить поразрядное сложение Рг2 = Рг1 + Рг2.

5. Выполнить сложение j = j + 1. Если j = 2n, то выход, иначе переход к

 

шагу 2.


 

Дополнительные примеры для решения.

 

Аналогично примеру 3.3 постройте элементы поля GF(24), заданного полиномом-модулем ψ(x) = x4 + x3 + 1.

 

Вопросы для самопроверки.

 

1. Поясните, как можно представлять элементы поля в стандартном базисе.

 

2. В чем достоинства и недостатки представления элементов поля в стандартном базисе?

3. Каким образом выполняется операция получения коэффициента элемента, представленного в стандартном базисе?

4. Каким образом выполняется операция установки значения коэффициента элемента, представленного в стандартном базисе?

5. Поясните, как можно представлять элементы поля при помощи сопровождающей матрицы.

6. Какой объём памяти требуется для хранения степеней сопровождающей матрицы?

7. Для чего используется представление элементов поля с помощью сопровождающей матрицы?

8. Поясните, как можно представлять элементы поля при помощи параллельных массивов.

9. Поясните, как можно представлять элементы поля в виде значения примитивного элемента.

10. Поясните, как можно представлять элементы поля в виде степени примитивного элемента.


 

Арифметические операции над элементами поля GF(2n),