Соотношения между элементами двойственных базисов

Обе полученные схемы реализации ЛРП над GF(q) основаны на формировании элементов ЛРП над GF(qm) путем последовательного умножения начального элемента поля GF(qm) на примитивный элемент поля. При этом одинаковые последовательности коэффициентов вектора начального состояния соответствуют разным элементам поля расширения в разных базисах. Последовательности на выходах обеих схем соответствуют последовательности значений функции след исходных элементов поля расширения.

Очевидно, что значения функции след одного и того же элемента GF(qm), записанного в полиномиальном и двойственном базисах, совпадают. Поэтому при соответствии векторов начального состояния обеих схем одному и тому же элементу поля расширения на выходе обеих схем будут получены одинаковые ЛРП над полем GF(q).

Запишем разложение элемента р в обоих двойственных базисах:

Для получения связи между коэффициентами разложения элемента р обоих базисов нам необходимо знать связь между базисными векторами.

Так как векторы у™ -1, ym - 2.....уо образуют базис, то любой элемент GF(qm)

как вектор векторного пространства GFm(q) можно представить линейной комбинацией векторов ym_i, у т-2,.... уо. В том числе вектор полиномиального базиса:

Для любого ак, к = 0,1,2.....т -1 системы (3.21), а также любого п = 0,1,2,

..., т - 1 в соответствии с определением двойственного базиса можно записать:

Тг{ак‘ап) = 7У(а/со7о-ал + akvyv ап + ... + акп-уп-ап + ... + akm-rym-van) = a*n.

Тогда:

Или в матричном виде:

Применив обозначения:

получим компактную матричную форму записи представления векторов полиномиального базиса в виде линейных комбинаций векторов двойственного базиса:

Матрица А определяется следующим образом:

Так как А~'-А = у, А~' - обратная матрица матрицы А (см. приложение 1), то матричное уравнение (3.22) может быть разрешено относительно у следующим образом:

где D = /А-1 - обратная матрица матрицы А.

По правилам умножения матриц, любой элемент матрицы-столбца у может быть определен как:

где dkj - элемент к-й строки и /-го столбца матрицы D = A~

Подобным образом из уравнения (3.22) векторы полиномиального базиса могут быть выражены через векторы двойственного базиса:

где akj - элемент /с-й строки и j-го столбца матрицы А.

Из формул (3.24) и (3.25) следует, что каждый вектор двойственного базиса соответствует некоторой линейной комбинации векторов полиномиального базиса, и наоборот.

Пример 3.3.2. Пусть поле GF(24) построено по модулю примитивного многочлена р(х) = х4 + х + 1. Выразим векторы двойственного базиса поля через векторы полиномиального базиса.

Найдем матрицу А:

Матрица D = /-1 в этом случае имеет вид:

Тогда, согласно уравнению (3.23) и формуле (3.24):

На основе полученных соотношений определим, например, соответствие вектора начального состояния 1111 элементу поля GF(24) в полиномиальном базисе для схемы реализации ЛРП над GF(24) из примера 3.3.1:

Полученная линейная комбинация степеней примитивного элемента соответствует элементу а11 поля GF(24) в полиномиальном базисе.

Ь;3

Ь 2

Ь'1

Ь'о

п

ft.

1

1

1

1

0

а"

0

1

1

1

1

а12

0

0

1

1

2

а13

0

0

0

1

3

а14

1

0

0

0

4

а15 = 1

0

1

0

0

5

а1

0

0

1

0

6

а2

1

0

0

1

7

а3

1

1

0

0

8

а4

0

1

1

0

9

а5

1

0

1

1

10

а6

0

1

0

1

11

а7

1

0

1

0

12

а8

1

1

0

1

13

а9

1

1

1

0

14

а10

Таблица 3.4 позволяет наглядно убедиться в том, что каждый элемент ЛРП над GF(qm), формируемый схемой на основе двойственного базиса, так же, как и в случае схемы на основе полиномиального базиса, соответствует результату умножения предыдущего элемента GF(qm), полученного схемой, на примитивный элемент поля GF(qm).

Пример 3.3.3. Рассмотрим теперь обратное выражение векторов полиномиального базиса через векторы двойственного базиса для поля из примера 3.3.2.

Запишем уравнение (3.22) для матрицы А, найденной в примере 3.3.2:

откуда:

В качестве проверки запишем элемент а11 из предыдущего примера в двойственном базисе:

Полученный набор коэффициентов соответствует исходному представлению рассматриваемого элемента в двойственном базисе.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >