Расширение полей

 

Рассмотрим, какова связь полей GF(p) и GF( p n ).

 

Пусть F - поле. Подмножество К поля Р, которое само является полем относительно операций поля Р, называется подполем. В этом случае F называется расширением поля К. Если K≠F , то К - собственное подполе.

Пример .Поле с множеством R действительных чисел является расширением поля с множеством рациональных чисел.

Поле GF( p n ) содержит единственное подполе, число элементов в котором простое и поэтому может рассматриваться как расширение поля GF(p) [2].

Поле GF(p) не имеет собственных подполей. Такие поля называются

 

простыми.

 

Теорема .(о существовании и единственности конечных полей) [11]. Для каждого простого числа q и каждого натурального числа n существует конечное поле GF(qn) из qn элементов.

Поле GF(qn) является расширением поля GF(q). qn называется порядком

 

поля GF(qn), натуральное число n - степенью поля, а простое число q -

 

характеристикой поля GF(qn).

 

Каждое подполе GF(qm) поля GF(qn) имеет порядок qm, где m | n и m > 0. И обратно - если m | n и m > 0, то для поля GF(qn) существует только одно подполе GF(qm) из qm элементов.

Пример. Подполя конечного поля GF(230) можно найти, вычислив все

положительные делители числа 30: 1, 2, 3, 5, 6, 10, 15. Представим взаимосвязи подполей в виде следующего рис. 2.3.

 

 

GF(230)

 

GF(26)

 

 

GF(22)

GF(210) GF(2 )

 

GF(23)

GF(25)

 

GF(2)

Рис. 2.3. Взаимосвязи подполей поля GF(230)

 

Элементами конечного поля GF(qn) (поля полиномов), число которых равно qn,

являются все полиномы (многочлены) вида

 

f(x) = αn−1xn−1 + ... + α1x + α0

 

- c коэффициентами αi ÎGF(q),

 

- со степенями от 0 до n-1 ( i = 0, n - 1 ),

 

- со степенью deg(f(x)) = n-1.

 

Данные полиномы f(x) называются полиномами над полем GF(q).

 

Для проверки примитивности полинома f(x) над полем GF(qn)

 

достаточно убедиться, что выполняются условия:

 

qn -

1) x

1 ºx mod

f ( x) ;

 

 

2) x

qn -1

pi º/

 

x mod

 

f ( x)

 

для "i = 0, k - 1 ,

 

 

k -1

i

где pi определяются из канонического разложения числа qn − 1 = Õpai

 

на k

 

 

простых сомножителей, αi - натуральные числа.

i = 0

 

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

 

1. Что такое расширение конечного поля? Что такое подполе?

 

2. Какие полиномы над GF(qn) являются элементами конечного поля?

 

3. Поясните понятия порядок поля, степень поля, степень полинома.

 

4. Поясните понятия неприводимый и примитивный полиномы.

 

5. Поясните понятие эквивалентности двух полиномов.

 

6. Что такое НОД от двух полиномов? Как он вычисляется?

 

7. Каким образом можно определить примитивность полинома f(x) степени n над полем GF(q)?

 

 

Вычисление обратного элемента в конечном поле GF(2n)

 

Обратный элемент в конечном поле GF(2n) (n - натуральное число) используется как вспомогательный элемент при делении некоторого многочлена A(x) на многочлен B(x) в поле GF(2n) по полиному-модулю P(x). Результирующий полином C(x) будет получен как C(x) = A(x)? B-1(x) mod P(x), где B-1(x) - обратный элемент для многочлена A(x).

Одним из способов получения обратного элемента в поле полиномов является использование функции Эйлера. Понятие функции Эйлера по аналогии переносится из теории чисел в поле GF(2n).

Пусть задан неприводимый модуль-полином P(x). Функция Эйлера в поле GF(2n) будет задавать число взаимно простых с P(x) полиномов. Так как P(x) является неприводимым, то функция Эйлера φ(P(x)) = 2n - 1.

Тогда, применяя функцию Эйлера, обратный элемент будет

 

вычисляться как

 

- jP x - n -

A 1 ( x) =A (

( )) 1 (x) mod P( x) =A2

2 ( x) mod P(x) .

 

Обратный элемент в поле GF(qn), где q - простое число, также можно

 

вычислить и по модификации алгоритма Евклида, находящей переменные выражения α·a + β·b = НОД(a, b) (раздел 1.1), только вместо чисел в формулу будут подставляться полиномы. Для нахождения обратного элемента g−1(x) для полинома g(x) по полиному-модулю f(x) в качестве решаемого уравнения используется g−1(x)g(x)+t(x)f(x) = 1, где g−1(x), g(x), t(x), f(x)ÎGF(qn).

Пример 3.11. Пусть заданы элемент поля A(x) = x2 + 1 и полином-

 

модуль P(x) = x3 + x + 1 в поле GF(23). Найдем обратный элемент A-1(x).

 

Тогда, применяя формулу Эйлера, получим:

 

A-1 ( x) = Aj( P( x ))-1 (x) mod P(x) = (x 2 + 1)2 -2 mod( x3 + x + 1) =

= ( x 2 + 1)6 mod(x3 + x +1) = (x 2 + 1)2 ( x 2 + 1)4 mod(x3 + x + 1) .

 

Найдем остаток от деления для первого слагаемого

 

(x2 +1)2 =x4 +2x2 +1=x4 +1

 

(слагаемое 2x2 сокращается, так как

 

коэффициенты полиномов складываются по модулю 2) на модуль P(x),

 

например, делением столбиком.

 

Åx4 +0·x2+0·x+1 | x3 + x + 1

x4 + x2 + x | x x2 + x + 1

То есть

(x2 +1)2 mod(x3 +x +1) =x2 +x +1.

 

Далее найдем остаток от деления для второго слагаемого

 

((x 2 + 1)2 )2 = (x 2 + x + 1)2 = x 4 + x 2 + 1 на модуль P(x).

 

Åx4 + x2+0·x+ 1 | x3 + x + 1

x4 + x2 + x | x x + 1

То есть

(x2 +1)4 mod(x3 +x +1) =x +1.

 

Вычислим итоговое выражение:

 

(x2 +1)2 (x2 +1)4 mod(x3 +x +1) =(x2 +x +1)(x +1)mod(x3 +x +1) =

=(x3 +1)mod(x3 +x +1)

и найдем остаток от деления:

 

Åx3 +0·x+1 | x3 + x + 1

x3 + x + 1| 1

x

Тогда, обратным элементом является A-1(x) = x.

 

Выполним проверку: должно выполняться сравнение

 

A(x)? A−1(x)mod P(x) ≡ 1.

 

(x2 + 1) ? x mod P(x) = (x3 + x) mod (x3 + x + 1).

 

Так как частное имеет степень, не большую модуля, то результат можно найти арифметическим сложением коэффициентов полиномов по модулю 2.

Å 1010

1011

То есть результатом является полином 1 и A(x)? A−1(x)mod P(x) ≡ 1.

 

Ответ: обратным элементом для полинома A(x) = x2 + 1 в поле GF(23),

 

где полином-модуль P(x) = x3 + x + 1, является многочлен A-1(x) = x.

 

Пример 3.12. Рассмотрим предыдущий пример с помощью взаимосвязи векторного и степенного представлений элементов. Пусть заданы элемент поля A(x) = x2 + 1 и полином-модуль P(x) = x3 + x + 1 в поле GF(23). Найдем обратный элемент A-1(x).

Примитивным элементом, с помощью которого можно получить все остальные элементы, является полином x (табл.3.8). Остальные элементы получим, умножая предыдущий элемент на x.

 

Для элементов 4, 6 и 7 необходимо выполнить нормировку модулем

 

P(x), например, с помощью деления столбиком:

 

4-ый элемент

Åx3 |x3+x+1

x3+x+1| 1

x+1

6-ой элемент

Åx3+x2 |x3+x+1

x3+ x+1| 1

x2+x+1

7-ой элемент

Åx3+x2+x |x3+x+1

x3+ x+1| 1

x2+ 1

 

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

 

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

 

 

Применяя формулу Эйлера, получим:

 

A-1 ( x) = Aj( P( x ))-1 (x) mod P(x) = (x 2 + 1)2 -2 mod( x3 + x + 1) =

= ( x 2 + 1)6 mod(x3 + x +1) = (x 2 + 1)2 ( x 2 + 1)4 mod(x3 + x + 1) .

 

Выражение (x2+1)2 mod P(x) можно вычислить, используя взаимосвязь векторного и степенного представлений элементов. Полиномиальная запись x2+1 соответствует векторной записи 101 и степенной ξ 6. Тогда, применяя

правило умножения степеней примитивного элемента (раздел 3.2), получим

 

n

ξ 6?ξ 6 mod P(x) = x12mod(2 -1)

= x12 mod 7

= ξ5. То есть 6-му элементу ξ5 поля

 

GF(23) соответствует полиномиальное представление x2 + x + 1 (векторное

 

111).

 

Аналогично, (x2+1)4 mod P(x) = (ξ5)2 mod P(x) = x 10 mod 7 = ξ 3. То есть 4-му элементу ξ3 поля GF(23) соответствует полиномиальное представление x + 1

(векторное 011).

 

В итоге,

(x2 +1)2 (x2 +1)4 modP(x)

= ξ5?ξ3 mod P(x) = x8 mod 7 = ξ. То есть

 

2−му элементу ξ поля GF(23) соответствует полиномиальное представление x

 

(векторное 001).

 

Обратный элемент можно было найти и сразу:

 

(x2 +1)6 modP(x)

= (ξ 6)6 mod P(x) = ξ 36 mod7 = ξ .

 

Проверим условие существование обратного элемента - выполнимость сравнения A(x)? A−1(x)mod P(x) ≡ 1. Получим

(x2 + 1) ? x mod P(x) = ξ6? ξ mod P(x) = ξ7 mod 7 = ξ0 ≡ 1.

 

Ответ: обратным элементом для полинома A(x) = x2 + 1 в поле GF(23),

 

где полином-модуль P(x) = x3 + x + 1, является многочлен A-1(x) = x.

 

Пример 3.13. Рассмотрим пример 3.11, оперируя элементами поля, заданными в векторном представлении. Пусть заданы элемент поля A(x) = x2 + 1 и полином-модуль P(x) = x3 + x + 1 в поле GF(23). Найдем обратный элемент A−1(x). Будем использовать таблицу 3.8 из примера 3.12.

Применяя формулу Эйлера, получим:

 

A-1 ( x) = Aj( P( x ))-1 (x) mod P(x) = (x 2 + 1)2 -2 mod( x3 + x + 1) =

= ( x 2 + 1)6 mod(x3 + x +1) = (x 2 + 1)2 ( x 2 + 1)4 mod(x3 + x + 1) .

 

Полином (x2 + 1) можно записать в векторном виде как 101 (табл. 3.8).

 

1. Найдем значение (x2 + 1)2 в векторном виде:

Ä101

101

Å101

101

10001 «x4 + 1

3. Найдем значение ((x2 + 1)2)2 =

= (x2 + x + 1)2 в векторном виде:

Ä111

111

Å111

111

10101 «x4 + x2 + 1

 

2. Нормируем полученный результат x4 + 1 модулем P(x):

Å10001 | 1011

1011 | 1

111 «x2 + x + 1

 

4. Нормируем результат x4 + x2 + 1

модулем P(x):

Å10101 | 1011

1011 | 1

11 «x + 1

 

5. Вычислим в векторном виде

( x 2 + 1)2 (x 2 + 1)4 = ( x 2 + x +1)(x + 1) :

Ä 111

011

Å111

111

1001 «x3 + 1

6. Нормируем результат x3 + 1

модулем P(x):

Å1001 | 1011

1011 | 1

10 « x

Тогда, обратным элементом является A-1(x) = x.

 

Выполним проверку: должно выполняться сравнение

 

A(x)?A−1(x)mod P(x) ≡ 1.

 

1. Вычислим значение (x2 + 1) ? x в векторном виде:

Ä101

010

1010 «x3 + x

 

2. Нормируем результат x3 + x

модулем P(x):

Å1010 | 1011

1011 | 1

1 « 1

Результатом является полином 1 и

A(x)?A−1(x)mod P(x) ≡ 1.

Ответ: обратным элементом для полинома A(x) = x2 + 1 в поле GF(23),

 

где полином-модуль P(x) = x3 + x + 1, является многочлен A-1(x) = x.

 

 

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

 

Вычислите обратные элементы для:

 

1) x+1 по модулю x4 + x + 1 в поле GF(24) (ответ: x3+x2+x);

 

2) x2+x по модулю x3 + x + 1 в поле GF(23) (ответ: x + 1),

 

с помощью полиномиального и векторно-степенного представлений.

 

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

 

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

 

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

3. Как выполняется сложение и умножение элементов в степенном представлении?

 

4. Каким образом нормируются результаты большей, а также равной степени, чем у полинома-модуля?

5. Как можно проверить, что обратный элемент был найден правильно?