Электрическое поле
<<  Электроскоп электрическое поле Поль Сезанн  >>
Поля
Поля
Конечные поля
Конечные поля
Определение
Определение
Число элементов
Число элементов
Арифметика по модулю
Арифметика по модулю
Теорема
Теорема
Конечное поле из двух элементов 0 и 1:
Конечное поле из двух элементов 0 и 1:
Пример конечного поля
Пример конечного поля
Циклические группы
Циклические группы
Порядок группы
Порядок группы
Циклическая группа
Циклическая группа
Циклическая группа из n элементов
Циклическая группа из n элементов
Эварист Галуа
Эварист Галуа
Многочлены
Многочлены
Рисунок
Рисунок
Расширенные конечные поля
Расширенные конечные поля
Расширенное поле
Расширенное поле
Расширенные поля Галуа
Расширенные поля Галуа
Модули
Модули
Произведение
Произведение
Мультипликативный порядок элементов поля
Мультипликативный порядок элементов поля
Ненулевой элемент
Ненулевой элемент
Элемент
Элемент
Структура конечных полей
Структура конечных полей
Корень многочлена
Корень многочлена
Таблица логарифмов
Таблица логарифмов
Таблица
Таблица
Степень
Степень
Неприводимый многочлен
Неприводимый многочлен
Ненулевые элементы
Ненулевые элементы
Построение расширенного поля
Построение расширенного поля
Полином
Полином
Свойства расширенных конечных полей
Свойства расширенных конечных полей
Построение полиномов
Построение полиномов
Утверждение
Утверждение
Длина сопряженного цикла
Длина сопряженного цикла
Алгоритм Евклида
Алгоритм Евклида
Векторное пространство
Векторное пространство
Источники
Источники

Презентация: «Конечные поля». Автор: Lena. Файл: «Конечные поля.ppt». Размер zip-архива: 399 КБ.

Конечные поля

содержание презентации «Конечные поля.ppt»
СлайдТекст
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 Арифметика по модулю

Арифметика по модулю

Обозначим: 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:

Конечное поле из двух элементов 0 и 1:

Пример конечного поля

+

0

1

*

0

1

0

0

1

0

0

0

1

1

0

1

0

1

8 Пример конечного поля

Пример конечного поля

Пример конечного поля (продолжение)

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

9 Циклические группы

Циклические группы

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

10 Порядок группы

Порядок группы

Определение

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

11 Циклическая группа

Циклическая группа

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

Теорема 1: является циклической только если n есть одно из чисел , где p есть нечетное простое число и n – положительное целое число.

12 Циклическая группа из n элементов

Циклическая группа из n элементов

Теорема 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 Расширенные поля Галуа

Расширенные поля Галуа

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

4.18

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 Таблица

Таблица

Структура конечных полей

i

z(i)

i

z(i)

i

z(i)

?

0

8

15

17

20

0

13

9

3

18

7

1

9

10

6

19

23

2

21

11

10

20

5

3

1

12

2

21

12

4

18

13

?

22

14

5

17

14

16

23

24

6

11

15

25

24

19

7

4

16

22

25

8

Таблица логарифмов для F27

28 Степень

Степень

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

28

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)

Примитивные многочлены

29

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 Длина сопряженного цикла

Длина сопряженного цикла

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

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

37 Алгоритм Евклида

Алгоритм Евклида

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

Алгоритмы

38 Векторное пространство

Векторное пространство

Векторное пространство(V,F, +, .)

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

39 Источники

Источники

Ленг С. Алгебра -М:, Мир, 1967 Р. Лидл, Г. Нидеррайтер. Конечные поля. В 2-х томах. - Москва, "Мир", 1988. Э.Берлекэмп, Алгебраическая теория кодирования, Мир, Москва, 1971. Р.Блейхут, Теория и практика кодов, контролирующих ошибки, Мир, Москва, 1986. http://www.ksu.ru/f9/index.php?id=20

«Конечные поля»
http://900igr.net/prezentacija/fizika/konechnye-polja-65229.html
cсылка на страницу

Электрическое поле

10 презентаций об электрическом поле
Урок

Физика

134 темы
Слайды