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

Сентябрь 14, 2022

Главная
Математика
Тема: Конечные поля

Содержание

2. Конечные поля Теория конечных полей является центральной математической теорией, лежащей в основе помехоустойчивого кодирования и криптологии.
3. Определение Пусть F есть множество с двумя бинарными операциями + и *. F называется полем, если
4. Определение Если число элементов F конечно, то F называется конечным полем
5. Арифметика по модулю Обозначим: Zn = {0, 1, … , n-1} a mod n есть остаток
6. Теорема: (p – простое число) с операциями сложения и умножения целых чисел по модулю p есть
7. Пример конечного поля Конечное поле из двух элементов 0 и 1:
8. Пример конечного поля (продолжение) Определелим поле GF(5) на множестве Z5 (5 – просое число) с операциями
9. Циклические группы Определение: Элемент g конечной группы G называется порождающим или примитивным элементом, если все элементы
10. Определение Порядок группы G – число элементов группы (обозначение |G| ). Порядок элемента g є G
11. Теорема 1: является циклической только если n есть одно из чисел , где p есть нечетное
12. Теорема 4: Пусть G есть циклическая группа из n элементов и являются делителями n, тогда существуют
13. Конечные поля Эварист Галуа(1811 -1832)
14. Многочлены Многочлен степени n ai – коэффициенты из некоторого множества (поля)
15. Многочлены (продолжение) Следующий рисунок иллюстрирует, как можно 8-разрядное слово (10011001) представить в виде многочлена.
16. Расширенные конечные поля Конечные поля существуют только для порядков q=pm (p – простое, m – натуральное).
17. Расширенные конечные поля Подобно этому расширенное поле GF(pm) порядка q=pm при m>1 можно ассоциировать с множеством
18. 4. Расширенные поля Галуа Определим поле GF(22) , состоящее из 4 двухразрядных слов: {00, 01, 10,
19. Многочлены - модули Для построения поля GF(2n) используются многочлены – модули над полем GF(2), которые должны
20. Пример. Обратимся к полиному f(x)=x3+x+1(неприводимый), deg(f(x))=3, тогдае го можно использовать для построения расширенного поля GF(23)=GF(8). Для
21. Мультипликативный порядок элементов поля. Примитивные элементы В любом поле GF(q), будь оно простым или расширенным, можно
22. Возьмем некоторый ненулевой элемент α∈GF(q) и рассмотрим его степени α1, α2, …, αl, … . Поскольку
23. Пример 1. Элемент 2 поля GF(7) имеет мультипликативный порядок t=3 поскольку для него 21=2, 22=4, 23=1.
24. Структура конечных полей Пусть f(x) – неприводимый многочлен степени n над полем F и α -
25. Структура конечных полей Пример: α корень многочлена 1+x+x3 над GF(2) , то есть 1+x+x3 GF(2)[x]. Следовательно,
26. Структура конечных полей Таблица логарифмов Zech: Пусть α – примитивный элемент GF(q). Для каждого 0≦i≦q-2 или
27. Структура конечных полей Таблица логарифмов для F27
28. Теорема: Произвольный неприводимы многочлен над полем GF(2) делит многочлен Xn+1, где n = 2m-1 и m
29. Примитивные многочлены Неприводимый многочлен p(X) степени m называется примитивным, если n – наименьшее положительное целое число
30. Пример. Элементы 3 и 5 поля GF(7) являются примитивными, тогда как остальные ненулевые элементы непримитивны. Действительно,
31. Построение расширенного поля GF(pm) в виде таблицы степеней примитивного элемента начинается с выбора примитивного полинома степени
32. Пример. Полином f(x)=x3+x+1 примитивен над GF(2). Учтя, что в GF(8) построенном с помощью f(x), x3= x+1
33. Некоторые свойства расширенных конечных полей Теорема 1. Среди всех элементов расширенного поля GF(2m) лишь элементы основного
34. Построение полиномов с заданными корнями Одно из фундаментальных положений классической алгебры утверждает, что любой полином f(x)
35. Пример 1. Рассмотрим полином g(z)=z3+z2+1. Легко убедиться, что у него нет корней в GF(2): g(1)= g(0)=1.
36. где все q–1 ненулевых элементов GF(q) выражены как степени примитивного элемента ς. Теорема 1. Пусть l
37. Алгоритмы Алгоритм Евклида нахождения НОД Расширенный алгоритм Евклида Возведение в степень
38. Векторное пространство(V,F, +, .) F - поле V множество элементов(векторов) Сложение векторов(коммутативное, ассоциат-е) Умножение на число
40. Скачать презентацию

Слайд 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

Арифметика по модулю
Обозначим: Zn = {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) на множестве Z5 (5 –

просое число) с операциями сложения и умножения. Как в таблице

Слайд 9

Циклические группы
Определение: Элемент g конечной группы G называется порождающим или примитивным

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

Слайд 10

Определение
Порядок группы G – число элементов группы (обозначение |G| ).
Порядок элемента

g є G – наименьшее n так что gn = e (обозначается ord g).

Слайд 11

Теорема 1: является циклической только если n есть одно из чисел

, где p есть нечетное простое число и n – положительное целое число.

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

Слайд 12

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

являются делителями n, тогда существуют в точности элементов порядка

Слайд 13

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

Слайд 14

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

Слайд 15

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

виде многочлена.

Слайд 16

Расширенные конечные поля
Конечные поля существуют только для порядков q=pm (p –

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

Слайд 17

Расширенные конечные поля
Подобно этому расширенное поле GF(pm) порядка q=pm при m>1

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

Слайд 18

4.
Расширенные поля Галуа
Определим поле GF(22) , состоящее из 4 двухразрядных слов:

{00, 01, 10, 11}. Определим операции сложения и умножения следующим образом.

Слайд 19

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

полем GF(2), которые должны быть неприводимыми.

Слайд 20

Пример. Обратимся к полиному f(x)=x3+x+1(неприводимый), deg(f(x))=3, тогдае го можно использовать для

построения расширенного поля GF(23)=GF(8).
Для a(x)=x2+x+1 и b(x)=x+1
сумма в поле GF(8) a(x)+b(x)= x2+x+1+x+1= x2
произведение в GF(8) (x2+x+1)(x+1) = x3+x2+x2+x+x+1 = x3+1, после чего разделим полученный результат на f(x) с последующим удержанием только остатка: x3+1=q(x)f(x)+r(x)=1·(x3+x+1)+x. Таким образом, a(x)b(x)=(x2+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 поскольку

для него 21=2, 22=4, 23=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[α]={a0 +a1α+ … +an-1 αn-1: ai из F}
Пусть α есть корень неприводимого многочлена степени m над полем GF(q), тогда α является также порождающим элементом поля

Слайд 25

Структура конечных полей
Пример: α корень многочлена 1+x+x3 над GF(2) , то

есть 1+x+x3 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

Структура конечных полей
Таблица логарифмов для F27

Слайд 28

Теорема: Произвольный неприводимы многочлен над полем GF(2) делит многочлен Xn+1, где

n = 2m-1 и m есть степень многочлена

Слайд 29

Примитивные многочлены
Неприводимый многочлен p(X) степени m называется примитивным, если n –

наименьшее положительное целое число такое что p(X) делит Xn+1 и n=2m-1
Пример
p(X)=X4+X+1 делит X15+1 но не делит никакой многочлен Xn+1 для 1≤n<15 (Primitive)
p(X)= X4+X3+X2+X+1 делит X5+1 (Irreducible but Not Primitive)

Слайд 30

Пример.
Элементы 3 и 5 поля GF(7) являются примитивными, тогда как

остальные ненулевые элементы непримитивны. Действительно, p–1=6 степеней элемента 3 различны: 31=3, 32=2, 33=6, 34=4, 35=5, 36=30=1. Для непримитивного элемента поля, например 2, подобные вычисления дают 21=2, 22=4, 23=1, 24=2, 25=4, 26=1, так что возведением 2 в различные степени можно получить лишь некоторые (но не все!) ненулевые элементы GF(7).

Слайд 31

Построение расширенного поля GF(pm) в виде таблицы степеней примитивного элемента начинается

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

Слайд 32

Пример. Полином f(x)=x3+x+1 примитивен над GF(2). Учтя, что в GF(8) построенном

с помощью f(x), x3= x+1 и обозначив x=ς, имеем ς3=ς+1. Вычислив следующие степени ς, придем к таблице

Перемножая два элемента поля, например ς+1 and ς2+ς+1, можно воспользоваться представлениями ς+1=ς3 и ς2+ς+1=ς5, так что ς3ς5=ς8=ς7ς=ς.

Слайд 33

Некоторые свойства расширенных конечных полей
Теорема 1. Среди всех элементов расширенного

поля GF(2m) лишь элементы основного подполя GF(2) , т.е. 0 и 1, удовлетворяют равенству

Теорема 2. Для любых элементов α, β поля GF(2m)

Слайд 34

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

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

Слайд 35

Пример 1. Рассмотрим полином g(z)=z3+z2+1. Легко убедиться, что у него нет

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

Слайд 36

где все q–1 ненулевых элементов GF(q) выражены как степени примитивного элемента

ς.

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

Слайд 37

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

Слайд 38

Векторное пространство(V,F, +, .)
F - поле
V множество элементов(векторов)
Сложение векторов(коммутативное, ассоциат-е)
Умножение

на число
Линейная зависимость, базисы, подпространства

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

Содержание

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

ОпределениеПусть F есть множество с двумя бинарными операциями + и *.F

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

Арифметика по модулюОбозначим: Zn = {0, 1, … , n-1}a mod

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

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

Пример конечного поля (продолжение)Определелим поле GF(5) на множестве Z5 (5 –

Циклические группыОпределение: Элемент g конечной группы G называется порождающим или примитивным

ОпределениеПорядок группы G – число элементов группы (обозначение |G| ).Порядок элемента

Теорема 1: является циклической только если n есть одно из чисел

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

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

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

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

Расширенные конечные поляКонечные поля существуют только для порядков q=pm (p –

Расширенные конечные поляПодобно этому расширенное поле GF(pm) порядка q=pm при m>1

4.Расширенные поля ГалуаОпределим поле GF(22) , состоящее из 4 двухразрядных слов:

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