Для построения элементов поля 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),