Тема: Конечные поляТема: Конечные поляКонечные поля Теория конечных полей является центральной математической теорией, лежащей в основе помехоустойчивого. - презентация

1 Тема: Конечные поля

2 Конечные поля Теория конечных полей является центральной математической теорией, лежащей в основе помехоустойчивого кодирования и криптологии. Конечные поля используются при кодировании, в современных блоковых шифрах таких как IDEA и AES, в поточных шифрах (сдвиговые регистры в мобильных телефонах), а также в открытых криптосистемах, например в протоколе обмена ключами Diffie- Hellman и Elliptic Curve Cryptosystems.

3 Определение Пусть F есть множество с двумя бинарными операциями + и *. F называется полем, если 1) F есть абелева группа по сложению + 2) F* = F\ {0} есть абелева группа по умножению * 3) Выполняется дистрибутивность для всех a,b и c из F a*(b + c) = a*b + a*c (a+b)*c = a*c + b*c

4 Определение Если число элементов F конечно, то F называется конечным полем

5 Арифметика по модулю Обозначим: Z n = {0, 1, …, n-1} a mod n есть остаток от деления a на n Пример:7mod2=1, 7mod4=3, 21mod7=0 если (a+b)=(a+c) mod n то b=c mod n Если ab = ac mod n то b=c mod n только если a и n взаимно просты a+b mod n = [a mod n + b mod n] mod n

6 Теорема: (p – простое число) с операциями сложения и умножения целых чисел по модулю p есть конечное поле

7 Пример конечного поля Конечное поле из двух элементов 0 и 1: *

8 Пример конечного поля (продолжение) Определелим поле GF(5) на множестве Z 5 (5 – просое число) с операциями сложения и умножения. Как в таблице

9 Циклические группы Определение: Элемент g конечной группы G называется порождающим или примитивным элементом, если все элементы группы являются степенями g. Такие группы называют циклическими Таким образом нейтральный элемент группы. Обозначение:

10 Определение Порядок группы G – число элементов группы (обозначение |G| ). Порядок элемента g є G – наименьшее n так что g n = e (обозначается ord g).

11 Теорема 1: является циклической только если n есть одно из чисел, где p есть нечетное простое число и n – положительное целое число. Теорема 2: Все циклические группы одного размера изоморфны. Теорема 3: Пусть G – циклическая группа из n элементов и g – порождающий элемент (т.е. ). Тогда порядок подгруппы равен

12 Теорема 4: Пусть G есть циклическая группа из n элементов и являются делителями n, тогда существуют в точности элементов порядка

13 Конечные поля Эварист Галуа( )

14 Многочлены Многочлен степени n a i – коэффициенты из некоторого множества (поля)

15 Многочлены (продолжение) Следующий рисунок иллюстрирует, как можно 8-разрядное слово ( ) представить в виде многочлена.

16 Расширенные конечные поля Конечные поляКонечные поля существуют только для порядков q=p m (p – простое, m – натуральное). Простое полеПростое поле порядка p, GF(p), можно трактовать как множество {0, 1, …, p–1} остатков от деления целых чисел на p с операциями сложения и умножения по модулю p.

17 Расширенные конечные поля Подобно этому расширенное поле GF(p m ) порядка q=p m при m>1 можно ассоциировать с множеством остатков от деления полиномов над GF(p) на некоторый неприводимый полином f(x) степени m с операциями сложения и умножения по модулю f(x).расширенное поле Другими словами, поле GF(p m ) можно представить всеми полиномами над простым полем GF(p) степени не выше m–1 с обычным полиномиальным сложением. Умножение же в нем выполняется в два шага – сперва как обычное умножение полиномов, но с удержанием в качестве конечного итога лишь остатка от деления полученного произведения на неприводимый полином f(x).остатка

18 4.18 Расширенные поля Галуа Определим поле GF(2 2 ), состоящее из 4 двухразрядных слов: {00, 01, 10, 11}. Определим операции сложения и умножения следующим образом.

19 Многочлены - модули Для построения поля GF(2 n ) используются многочлены – модули над полем GF(2), которые должны быть неприводимыми.

20 Пример. Обратимся к полиному f(x)=x 3 +x+1(неприводимый), deg(f(x))=3, тогдае го можно использовать для построения расширенного поля GF(2 3 )=GF(8). Для a(x)=x 2 +x+1 и b(x)=x+1 сумма в поле GF(8) a(x)+b(x)= x 2 +x+1+x+1= x 2 произведение в GF(8) (x 2 +x+1)(x+1) = x 3 +x 2 +x 2 +x+x+1 = x 3 +1, после чего разделим полученный результат на f(x) с последующим удержанием только остатка: x 3 +1=q(x)f(x)+r(x)=1·(x 3 +x+1)+x. Таким образом, a(x)b(x)=(x 2 +x+1)(x+1)=x.

21 Мультипликативный порядок элементов поля. Примитивные элементы В любом поле GF(q), будь оно простым или расширенным, можно перемножать любые операнды, в том числе l-кратно умножать элемент на себя. Естественно называть такое произведение l-й степенью элемента, обозначив его как

22 Возьмем некоторый ненулевой элемент GF(q) и рассмотрим его степени 1, 2, …, l, …. Поскольку все они принадлежат конечному полю GF(q), в рассматриваемой последовательности рано или поздно появятся повторения, так что для некоторых l и s (l>s) l = s, а значит, l-s =1. Назовем минимальное натуральное число t, для которого мультипликативным порядком элемента.

23 Пример 1. Элемент 2 поля GF(7) имеет мультипликативный порядок t=3 поскольку для него 2 1 =2, 2 2 =4, 2 3 =1. Подобно этому, как легко видеть, для элемента 3 t=6, для 4 t =3, для 5 t=6, для 6 t=2. Все найденные мультипликативные порядки делят число p–1=6 ненулевых элементов поля. Пример.2. В поле GF(8) число ненулевых элементов поля – простое: 8–1=7, а, значит, его делители – только числа 1 и 7. Так как единственный элементом мультипликативного порядка 1 – единица поля, все остальные ненулевые элементы имеют максимальный мультипликативный порядок, равный 7.

24 Структура конечных полей – Пусть f(x) – неприводимый многочлен степени n над полем F и α - корень f(x). Тогда поле F[x]/(f(x)) можно представить как F[α]={a 0 +a 1 α+ … +a n-1 α n-1 : a i из F} – Пусть α есть корень неприводимого многочлена степени m над полем GF(q), тогда α является также порождающим элементом поля

25 Структура конечных полей Пример: α корень многочлена 1+x+x 3 над GF(2), то есть 1+x+x 3 GF(2)[x]. Следовательно, GF(8)=GF(2)[α]. Порядок α есть делитель 8-1=7. Поэтому ord(α)=7 и α – примитивный элемент. Тогда: α 3 +α 6 = (1+α)+(1+α 2 ) = α+α 2 = α 4 α 3 α 6 = α 9 =α 2

26 Структура конечных полей Таблица логарифмов Zech: – Пусть α – примитивный элемент GF(q). Для каждого 0 i q-2 или i =, мы определяем и заносим в таблицу элемент z(i) такой что 1+α i =α z(i). (примем α = 0) – Для любых двух элементов α i и α j, 0 i j q-2 в поле GF(q). α i +α j = α i (1+α j-i ) = α i+z(j-i) (mod q-1) α i α j = α i+j (mod q-1)

27 Структура конечных полей iz(i)i i Таблица логарифмов для F 27

28 Теорема: Произвольный неприводимы многочлен над полем GF(2) делит многочлен X n +1, где n = 2 m -1 и m есть степень многочлена 28

29 Примитивные многочлены Неприводимый многочлен p(X) степени m называется примитивным, если n – наименьшее положительное целое число такое что p(X) делит X n +1 и n=2 m -1 Пример – p(X)=X 4 +X+1 делит X но не делит никакой многочлен X n +1 для 1n

30 Пример. Элементы 3 и 5 поля GF(7) являются примитивными, тогда как остальные ненулевые элементы непримитивны. Действительно, p–1=6 степеней элемента 3 различны: 3 1 =3, 3 2 =2, 3 3 =6, 3 4 =4, 3 5 =5, 3 6 =3 0 =1. Для непримитивного элемента поля, например 2, подобные вычисления дают 2 1 =2, 2 2 =4, 2 3 =1, 2 4 =2, 2 5 =4, 2 6 =1, так что возведением 2 в различные степени можно получить лишь некоторые (но не все!) ненулевые элементы GF(7).

31 Построение расширенного поля GF(p m ) в виде таблицы степеней примитивного элемента начинается с выбора примитивного полинома степени m над простым полем GF(p): f(x)=x m +f m-1 x m-1 +…+f 0. Подобные полиномы либо даются в специальных таблицах, либо маркируются особой меткой в таблицах неприводимых полиномов. Для m-й степени элемента x по модулю f(x) имеет место равенство x m = –f m-1 x m–1 –f m-2 x m–2 –…–f 0.

32 Пример. Полином f(x)=x 3 +x+1 примитивен над GF(2). Учтя, что в GF(8) построенном с помощью f(x), x 3 = x+1 и обозначив x=, имеем 3 = +1. Вычислив следующие степени, придем к таблице Перемножая два элемента поля, например +1 and , можно воспользоваться представлениями +1= 3 и = 5, так что 3 5 = 8 = 7 =.

33 Некоторые свойства расширенных конечных полей Теорема 1. Среди всех элементов расширенного поля GF(2 m ) лишь элементы основного подполя GF(2), т.е. 0 и 1, удовлетворяют равенству Теорема 2. Для любых элементов, поля GF(2 m )

34 Построение полиномов с заданными корнями Одно из фундаментальных положений классической алгебры утверждает, что любой полином f(x) степени m с действительными или комплексными коэффициентами всегда имеет ровно m действительных или комплексных корней x 1, x 2, …, x m, что означает справедливость разложения (при единичном старшем коэффициенте)

35 Пример 1. Рассмотрим полином g(z)=z 3 +z Легко убедиться, что у него нет корней в GF(2): g(1)= g(0)=1. Вместе с тем, обратившись к таблице поля GF(8) в примере 8.2.4, можно видеть, что g( 3 )= = =0, и значит, 3 является корнем g(z) в поле GF(8). Двоичный полином наименьшей степени, для которого элемент GF(2 m ) является корнем, называется минимальным полиномом. Введем для него обозначение g (z) и сформулируем следующее утверждение.

36 где все q–1 ненулевых элементов GF(q) выражены как степени примитивного элемента. Теорема 1. Пусть l – длина сопряженного цикла элемента. Тогда Теорема 2. Пусть GF(q) - расширение GF(2), где q=2 m. Тогда все ненулевые элементы GF(q) являются корнями биномаz q–1 –1= z q–1 +1. Как следствие этой теоремы справедливо следующее равенство

37 Алгоритмы Алгоритм Евклида нахождения НОД Расширенный алгоритм Евклида Возведение в степень

38 Векторное пространство(V,F, +,.) F - поле V множество элементов(векторов) Сложение векторов(коммутативное, ассоциат-е) Умножение на число Линейная зависимость, базисы, подпространства

39 Источники Ленг С. Алгебра -М:, Мир, 1967 Р. Лидл, Г. Нидеррайтер. Конечные поля. В 2-х томах. - Москва, "Мир", Э.Берлекэмп, Алгебраическая теория кодирования, Мир, Москва, Р.Блейхут, Теория и практика кодов, контролирующих ошибки, Мир, Москва,