ЛЕКЦИЧ 16

 

Способы представления элементов поля GF(2n)

 

Для представления элементов в полях Галуа вида GF(2n) существуют различные способы, образующие изоморфные поля:

- полиномиальное;

 

- стандартный базис;

 

- при помощи сопровождающей матрицы;

 

- параллельные массивы;

 

- нормальный базис - в виде:

 

- значения степеней примитивного элемента ξ,

 

- степеней примитивного элемента ξ.

 

I. Полиномиальное представление.

Каждый элемент GF(2n) можно представить в виде некоторого многочлена

 

f(x) = a0 + a1x + … + an−1xn-1, (3.1)

 

- степени deg(f(x)) ≤ n-1

 

- с коэффициентами ai ÎGF(2).

 

II. Стандартный базис(векторное представление):

 

- элементы поля задаются полиномами вида (3.1);

 

- хранятся коэффициенты полинома f(x) в виде двоичного вектора. Используются 2 метода расположения старших степеней полинома f(x):

- математическая форма записи (запись слева направо):

 

- слева располагается старшая степень полинома,

 

- оптимально для операций деления и увеличения степени полиномов;

- обратный порядок (запись справа налево):

 

- оптимально для операций умножения и сложения полиномов. Достоинствами векторного представления является следующее:

- рационально используется память,

 

- простота выполнения операций сложения и вычитания полиномов

 

(например, на регистровых структурах).

 

Недостатком векторного представления является то, что требуется дополнительное время ЭВМ для выборки коэффициентов, так как обработка данных в ЭВМ выполняется байтами, а не битами.

Операция получения бинарного коэффициента полинома реализуется следующим образом:

1) находится байт, содержащий требуемый коэффициент в виде бита;

 

2) байт сдвигается вправо, чтобы бит оказался на младшей позиции байта;

3) байт логически умножается на двоичную единицу:

 

- для обнуления остальных бит,

 

 

как:

- и выделения нужного бита.

 

На языке программирования Сиоперацияполучения бита выполняется

 

(x >> i) & 1,

 

где x - значение машинного слова,

 

i - позиция искомого бита,

 

>> - сдвиг значения переменной x на i позиций вправо (слева добавляются нули),

& - операция логического умножения.

Для установки значения y (y Î{0, 1}) для i-го бита используется операция:

 

(x & ~(1 << i)) | (y << i),

 

где << - операция сдвига значения переменной y на i позиций влево (справа добавляются нули),

~(…) - двоичная инверсия значения в скобках,

 

| - операция логического сложения,

(x & ~(1 << i)) - обнуление i-го бита в переменной x (демаскирование i-го бита).

 

Левая часть выражения обнуляет i-ый бит в числе x, а правая часть -

 

устанавливает новое значение y в i-ю позицию.

 

Стандартный базис применяется:

 

- для перевода между собой двух типов представления элементов нормального базиса:

- из степени примитивного элемента в его значение,

 

- и обратно.

 

III. Представление элементов конечного поля GF(2n) при помощи

 

сопровождающей матрицы A, заданной примитивным многочленом

 

ψ(x) = a0 + a1x + … + an−1xn-1 + xn, где ai Î{0, 1}.

 

Сопровождающая матрица A строится на базе полинома-модуля ψ(x)

 

следующим образом.

 

 

1. Матрица A = (aij), aij Î{0, 1}, i, j = 0, n - 1, заполняется нулями.

 

2. Единицами заполняется главная нижняя поддиагональ:

 

- для "i = 1, n - 2 выполняется аi+1,I = 1.

 

3. В верхнюю строку матрицы записываются коэффициенты при неизвестных ψ(x) в порядке убывания степеней неизвестных:

- для i = 0, n - 1: a0,i = an-i-1.

 

n

Тогда получим матрицу следующего вида (рис.3.1).

 

Степени этой матрицы A, A2, …,

 

определяют элементы поля GF(2n):

A2 -1

 

вместе с нулевой матрицей

 

- нижняя строка матрицы А i в виде вектора (a(n-1)0, a(n-1)1, …, a(n-1)(n-1))

 

задает

 

- соответствующий i-ый элемент поля GF(2n) - степень примитивного элемента ξ i, "i = 0,2 n - 2 .

an-1 an-2 an-3 … a2 a1 a0

1 0 0 0 0 0

An?n = 0 1 0 …0 0 0

0 0 1 0 0 0

… … …

0 0 0 0 1 0

Рис.3.1. Структура сопровождающей матрицы

 

 

Пример 3.1. Представим элементы поля GF(23) в виде степеней сопровождающей матрицы.

Для многочлена ψ(x) = x3 + x + 1 сопровождающая матрица имеет вид

 

(рис. 3.2):

 

A3?3 =

Рис.3.2. Сопровождающая матрица для полинома ψ(x) = x3 + x + 1

 

Получим следующее множество элементов поля: (0, E, А, А2, А3, А4, А5,

 

А6) (рис. 3.3), где E - единичная матрица размера n? n и А7 совпадает с E:

 

0 =

;

E=

;

A=

 

A2=

;

A3=

;

A4=

A5=

;

A6=

;

A7=

Рис. 3.3. Степени матрицы A

 

Для хранения элементов поля требуется объем памяти:

 

- равный 2n? n? n = 2n? n2 бит,

 

- где n? n - объем памяти под одну матрицу. Для операций:

- редко использующих все значения степеней матрицы A,

 

- можно хранить только матрицу A.

 

При вычислении матрицы A i, "i = 2, 2n - 2 :

 

- потребуется выполнить (n-1)? n2? (i-1) операций сложения и

 

- n? n2? (i-1) операций умножения,

 

- где (i-1) - количество последовательных возведений в степень,

 

- (n - 1) - количество операций для получения одного элемента результирующей матрицы при умножении матриц Ai-1 и A.

Данный способ представления элементов поля применяется:

 

- при умножении двух полиномов методом Paar [16]:

 

- замена комплексной операции умножения

 

- на множество умножений и сложений полиномов меньших степеней;

- для получения значений степеней примитивного элемента при использовании нормального базиса.

 

IV. Представление полиномов в виде параллельных массивов, где элементы:

- первого массива хранят степени неизвестных полинома (степень при неизвестной с ненулевым коэффициентом),

- а элементы второго - коэффициенты при неизвестных.

 

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

- хранятся коэффициенты и степени при неизвестных полиномов только для степеней,

- при которых находятся коэффициенты,

 

- общее количество которых меньше числа коэффициентов, противоположных по значению.

V. Нормальный базис. Элементы поля представляются в виде:

 

- степеней примитивного элемента,

 

- которым сопоставлены бинарные значения элементов поля (элементы в стандартном базисе).

Для поля GF(2n) требуется вычислить и хранить:

 

- (2n - 1) степеней примитивного элемента,

 

- каждая из которых имеет длину n-1 бит.

 

Все элементы поля GF(2n) можно записать в виде множества:

 

n

GF(2n) = {0, 1, ξ, ξ2, …, x2 -2 },

 

где ξ - примитивный элемент.

 

Для получения элементов поля GF(2n) в этом базисе можно использовать:

- способ последовательного умножения ξ i на ξ (то есть ξ используется

 

как образующий элемент поля GF(2n));

 

- вычисление сопровождающей матрицы A. Пример 3.2. Построим поле GF(2n), где n = 3. Пусть даны:

- неприводимый полином-модуль ψ(x) = x3 + x + 1 и

 

- ξ - заранее известный примитивный элемент поля, являющийся корнем модуля, т.е. если ψ(ξ) = ξ3 + ξ + 1 = 0.

Тогда GF(23) = (0, 1, ξ, ξ2, ξ3, ξ4, ξ5, ξ6).

 

Элементы поля GF(23) в нормальном базисе можно построить следующим образом:

1) на каждом шаге будем умножать предыдущий элемент поля на ξ;

 

2) если получается полином, степень которого ≥ deg ψ(ξ) (x заменили на

ξ), то осуществляется взятие остатка от деления текущего результата на полином ψ.

 

ξ0=1 = (001) ξ1=ξ = (010) ξ2=ξ2 = (100) ξ3=1+ξ = (011)

ξ4=ξ+ξ2 = (110) ξ5=ξ3+ξ2 = (111) ξ6=ξ4+ξ3 = (101) ξ7=1=ξ0.

 

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

 

Способ представления данных с помощью нормального базиса:

 

- нерационален,

 

- так как хранится большое количество информации.

 

Существует 2 формы представления элементов поля в нормальномбазисе - в виде:

- значения степеней примитивного элемента;

 

- степеней примитивного элемента.

 

а) Хранение значений степеней примитивного элемента(эквивалент стандартного базиса):

- примитивный элемент в некоторой степени хранится в виде бинарного вектора;

- значение ξ i представляется в виде двоичных коэффициентов

 

n

многочлена ξ i;

 

- для хранения поля GF(2n) = (0, 1, ξ, …, ξ i, …,

 

двумерный вектор - матрица,

x2 -2 ) используется

 

- каждая i-ая строка матрицы содержит двоичное значение элемента ξ i.

 

Матрица будет иметь следующий размер:

 

- количество строк (количество степеней примитивного элемента)

 

равно 2n-1,

 

- количество столбцов n,

 

- где n - максимальная степень полинома-модуля,

 

- то размер равен (2n-1)? n ячеек.

 

б) Хранение степеней примитивного элемента, а не значения степеней примитивного элемента:

- для задания элемента ξ i хранится степень i;

 

- элемент, равный 1, заменяется на ξ 0, а соответственно его степень равна 0;

- если значение степени примитивного элемента равно 0, то принимается:

- что показатель степени примитивного элемента равен неопределенности,

- обозначаемой символом "¥".

 

Использование данного метода хранения:

 

- дает выигрыш в памяти,

 

- так как требуется хранить не вектор-полином, а целое число, размером в машинное слово;

- упрощает операции умножения элементов и возведения их в степень,

 

- так как операции выполняются не с векторами, а с целыми числами -

 

степенями элементов.

 

В качестве недостатков можно отметить:

 

- так как в основном в операциях с элементами поля участвуют сами значения элементов поля,

- то требуется система перевода степени примитивного элемента в его значение;

- неэффективен при сложении элементов;

 

- увеличивается время работы алгоритма:

 

- на преобразование из степени в значение и обратно;

 

- для этого используется предварительно полученная матрица из пункта а).

При вычислении некоторой операции с элементами, заданными в видестепеней (например, сложение элементов):

- элементы поля записываются в стандартном базисе (в векторном представлении);

- над ними выполняются арифметические операции;

 

- в конце возможно обратное преобразование результата:

 

- результирующий бинарный вектор ищется в матрице из пункта а),

 

- номер найденной строки i и будет задавать степень элемента ξ i.

 

Пример 3.3. В табл. 3.1 записаны элементы поля GF(24) в разных представлениях для полинома-модуля ψ(x) = x4 + x + 1.

В полиномиальном представлении следующий элемент получается:

 

- путем умножения предыдущего элемента, заданного в виде полинома,

 

на x;

 

- если максимальная степень результата операции получается равной

 

степени модуля,

 

- то выполняется нормирование результата - поразрядное сложение по модулю 2 результата и полинома ψ(x).

Таблица 3.1 (начало). Элементы поля в разных представлениях

Номер элемента	Нормальный базис ξ i (степенное)	Стандарт- ный базис (векторное)	Полиномиальное
	ξ ¥
	ξ 0
	ξ 1		x
	ξ 2		x2
	ξ 3		x3
	ξ 4		x+1
	ξ 5 = ξ 4ξ		(x+1)x = x2+x
	ξ 6= ξ 5ξ		(x2+x)x = x3+x2
	ξ 7= ξ 6ξ mod φ(x)		(x3+x2)x = (x4+x3)mod φ(x) = x3+x+1

 

Таблица 3.1 (окончание). Элементы поля в разных представлениях

 

	ξ 8 = ξ 7ξ mod φ(x)		(x3+x+1)x = (x4+x2+x)mod φ(x) = x2+1
	ξ 9 = ξ 8ξ		(x2+1)x = x3+x
	ξ10= ξ 9ξ mod φ(x)		(x3+x)x = (x4+x2)mod φ(x) = x2+x+1
	ξ11= ξ10ξ		(x2+x+1)x = x3+x2+x
	ξ12=ξ11ξ mod φ(x)		(x3+x2+x)x = (x4+x3+x2) mod φ(x) = x3+x2+x+1
	ξ13=ξ12ξ mod φ(x)		(x3+x2+x+1)x = (x4+x3+x2+x) mod φ(x)= x3+x2+1
	ξ14=ξ13ξ mod φ(x)		(x3+x2+1)x = (x4+x3+x) mod φ(x) = x3+1

 

Рассмотрим получение 11-го элемента. Для получения 11-го элемента

 

10−ый элемент умножается на x:

 

(x3 + x)·x = x4 + x2.

 

Поразрядно сложим векторы коэффициентов для полинома

 

x4+x2 (101002) и полинома-модуля x4 + x + 1 (100112):

 

Å100112

001112.

Получаем 11-ый элемент, равный:

 

- в стандартном базисе 01112,

 

- или в полиномиальном x2 + x + 1.

 

Если степень результата будет > степени модуля ψ(x), то осуществляется деление результата на ψ(x). Например:

- получим 11-ый элемент через 7-ой;

 

- умножим полином, соответствующий 7-му элементу, на x4: (x3 + x2)·x4= x7 + x6;

- так как степень результата > степени модуля, то выполняется деление результата на модуль ψ(x) (например, столбиком), а не сложение с ним:

 

x7 +x6

Å

x7 +

 

 

x4 +x3

x 4 + x + 1

x3 +x2 +1

 

x6 +x4 +x3

Å x6 +

 

x4 +

Å x4 +

 

x3 + x 2

 

x2

x + 1

 

x2 +x +1

Получим остаток x2 + x + 1, который и является 11-м элементом поля.