Самсонов Б.Б., Плохов Е.М., Филоненков А.И. Компьютерная математика (основания информатики). Ростов-на-Дону: «Феникс», 2002. – С. 228-292.

440305

ПАМ

Толстиков А.В.

Лекция 8. Многочлены над конечными полями

 

1. Функция Мебиуса и формула обращения Мебиуса.

2. Неприводимые многочлены над конечными полями и их число.

3. Порядок многочлена над конечным полем.

4. Критерий неприводимости многочлена и способы построения неприводимых многочленов над конечным полем.

5. Конструкция конечного поля из pⁿ элементов. Вычисления в конечных полях.

 

Литература. Нечаев В.И. – С. 34-41, 79-83. С. 42-48.

Глухов М.М. и др. Т.1 – С. 244-251, 262-268; -Т2. –С. 202-220.

С. 221-237.

Самсонов Б.Б., Плохов Е.М., Филоненков А.И. Компьютерная математика (основания информатики). Ростов-на-Дону: «Феникс», 2002. – С. 228-292.

 

Конечные группы. Примеры конечных групп. Симметрическая группа. Теорема Кэли.

Определение 1. Непустое множество G называется группой, если на множестве G определена бинарная алгебраическая операция, обозначим ее значком умножение, которая каждой паре элементов a, b Î G ставит в соответствие единственный третий элемент из G, обозначаемый ab и для ее выполняются условия:

1)  - ассоциативный закон;

2)  - свойство нейтрального элемента;

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

Если операция в группе G, как и в нашем случае, обозначается значком «×», то группа G называется мультипликативной, нейтральный элемент называется в этом случае единицей, а симметричный элемент – обратным.

Если операция в группе G обозначается значком «+», то группа G называется аддитивной, нейтральный элемент называется тогда нулем, а симметричный элемент – противоположным.

Если операция в группе G обладает свойством коммутативности, т.е.

,

то группа G называется коммутативной или абелевой группой

Если число элементов в группе G конечно, то группа G называется конечной группой, если число элементов в группе G бесконечно, то группа G называется бесконечно. В случаеконечной группы число элементов в группе G обозначаем через | G | и называем порядком группы.

Примерами конечных групп являются.

Пример 1. Группа (Z _m,+) классов вычетов по модулю m. Порядок этой группы равен m.

Пример 2. Группа (Z _m ´,×) примитивных классов вычетов по модулю m. Порядок этой группы равен j(m).

Пример 3. Пусть S = {1, 2,…, n }. Подстановкой n -й степени называемлюбое взаимно однозначное отображение a множества S самого на себя. Любую подстановку a n -й степени можно записать в виде двух n -перестановок, записанных одна под другой, т.е. записать в виде:

,

где для каждого i Î S a _i = a(i). 

Если a _i = a(i) = i, то говорят, что элемент i переходит при подстановке a в элемент a _i. При этом, если a _i = i, то элемент i называется неподвижным элементом подстановки a, если   a _i ¹ i, то элемент i называется подвижным элементом подстановки a.

Композиции подстановок называется умножением подстановок: при умножение подстановок ab нужно сначала выполнить подстановку b, а затем подстановку a. Например, если

,

то для любого i Î S  (ba)(i) = b(a(i)) = b(a _i) = b _i, т.о.

.

Подстановки

называются соответственно единичной и обратной подстановкой для a.

Множество всех подстановок n -й степени обозначается символом S_n.

Справедлива теорема.

Теорема 1. Множество S_n   всех подстановок -й степени образует группу относительно операции умножения подстановок. ÿ

Группа S_n играет большую роль в математике и называется симметрической группой подстановок n -й степени.

Особое положение теории групп подстановок в теории групп поясняется следующей теоремой.

Теорема 2 (Кэли). Любая конечная группа G порядка n изоморфна некоторой подгруппе симметрической группы n -й степени S_n.

Доказательство. Пусть G = { a ₁, a ₂,…, a_n }, a ₁ = e - единичный элемент группы G. Рассмотрим n-ку (a ₁, a ₂,…, a_n). Возьмем произвольный элемент a Î G, и рассмотрим n-ку (aa ₁, aa ₂,…, aa_n). Все элементы этого множества принадлежат G и попарно различны. Действительно, если aa_i = aa_j, то по закону сокращения получаем a_i = a_j противоречие с тем, что все элементы множества { a ₁, a ₂,…, a_n } попарно различны. Таким образом, n -ка (aa ₁, aa ₂,…, aa_n) определяется однозначно и является перестановкой из элементов группы G, (aa ₁, aa ₂,…, aa_n) = = . Обозначим ее через j(a) подстановку n -степени , которая по элементу определяется однозначно. Покажем, что, если a, b Î G, a ¹ b, то j(a) ¹ j(b). Действительно, если a ¹ b, то для любого элемента a_i Î G aa_i ¹ ba_i. Поэтому элементам a, b соответствуют различные перестановки j(a), j(b). В В силу сказанного выше j - взаимно однозначное отображение G группы в группу S_n.

Покажем, что установленное соответствие является изоморфизмом группы G на подалгебру j(G) группы S_n..Покажем, что для любых двух элементов a, b Î G имеет место равенство j(ab) = j(a)j(b). Пусть

.

Тогда по определению произведения подстановок

.                                                      (1)

По определению установленного выше соответствия j имеем

(ba ₁, ba ₂,…, ba_n) = , .

Тогда в силу ассоциативного закона будем иметь

((ab) a ₁, (ab) a ₂,…, (ab) a_n) =(a (ba ₁), a (ba ₂),…, a (ba_n))=

По определению установленного выше соответствия j и формулы (1) получаем

.

Так как отображение j является изоморфизмом алгебр G и j(G), и G группа, то j(G) группа. Таким образом, G изоморфно подгруппе j(G) группы S_n. 

Следствие. Все конечные группы порядка n с точностью до изоморфизма являются подгруппами симметрической группы S_n подстановок n -й степени.

Определение 2. Подстановку aÎ S_n не равная единичной называют циклом длины k, если она перестановкой столбцов, может быть приведена к виду:

,

т.е. элементы a₁, a₂,…, a _k  подстановки переставляются по циклу, а остальные элементы остаются на своих местах.

Для записи цикла удобна более простая запись подстановки:

a = (a₁, a₂,…, a _k).

Заметим, что один и тот же цикл длины k можно записать k способами.

Два цикла называются независимыми, если они не содержат одинаковых элементов.

Теорема 3. Любая неединичная подстановка aÎ S_n либо является циклом, либо раскладывается в произведение некоторого числа попарно независимых циклов. Такое разложение однозначно с точностью до порядка следования сомножителей.

Доказательство.   Доказательство существования проведем методом математической индукции по числу m подвижных элементов в подстановке a. Число подвижных элементов в неединичной подстановке a не менее двух. Пусть   m = 2. Тогда в подстановке a два подвижных элемента a₁ и a₂ , которые образуют цикл длины 2 и подстановка a – цикл a = (a₁, a₂). Для m = 2 утверждение теоремы справедливо.

Допустим, что утверждение теоремы справедливо для любой подстановки, которая имеет менее    m подвижных элементов и докажем его для подстановки a, имеющей m подвижных элементов. Пусть a₁ – любой подвижный элемент подстановки a. Тогда имеем последовательность элементов

a₂ = a(a₁), a₃ = a(a₂) = a²(a₁), a₄ = a(a₃)= a³(a₁),…, a _i = a(a _{i - 1})= a ^{i -1}(a₁),… (1)

Так как все элементы последовательности (1) принадлежат S, то среди них обязательно найдется по крайней мере два равных:

a _i = a _j, (i < j), т.е. a ^{i -1}(a₁) = a ^{j -1}(a₁).

Применяя к обеим частям последнего равенства подстановку (a^-1) ^{i -1} получаем

. a ^{j - i} (a₁) = e(a₁) = a₁.

Таким образом, в последовательности (1) найдется элемент a _i; i > 1, равный элементу a₁. Пусть k - наименьшее натуральное число > 1 с таким свойством.

Рассмотрим цикл b = (a₁, a₂, …, a _{k - 1}). Тогда подстановка b^-1a оставляет элементы a₁, a₂, …, a _{k - 1} неподвижными и сохраняет неподвижные элементы подстановки a. Тогда число неподвижных элементов в подстановке b^-1a меньше m и к ней применимо индуктивное предположение b^-1a представляется в виде произведения независимых циклов, в которые войдут только подвижные элементы подстановки b^-1a: b^-1a = g…d. Отсюда a = bg…d. Тогда первая часть теоремы доказана.

Методом от противного доказывается единственность разложения.

Пример 1.

.

 

Доказательство.

1) Следует из равенства (1).

2) Следует из того, что порядок элемента конечной группы является делителем порядка группы.

3) Следует из того, что q – 1 делит qⁿ – 1.

4) Для a = 0 очевидно, а для a ¹0 следует из 3).ÿ

Теорема 2. Для любого элемента   a Î F_q ^* порядка d выполняются свойства:

1⁰ для любых натуральных чисел a ^m = a ^k тогда и только тогда, когда         m º k (mod d);

2⁰ все элементы множества

1, a, a ², …, a ^d-1                                                   (3)

различны;

3⁰ элементы множества (3) есть все корни многочлена

x ^d - 1;                                                     (4)

4⁰ для любого натурального числа k порядок элемента a^k равен .

5⁰ для любого натурального числа k ord a^k = d тогда и только тогда, когда числа k и d взаимно простые;

6⁰ число элементов b Î F_q порядка d равно j(d).  

Доказательство. Свойства 1⁰ и 2⁰ следуют из свойства порядка элемента мультипликативной группы.

3⁰ Так как для любого натурального числа k

,

то все элементы множества (3) являются корнями многочлена (4). Так как многочлен степени d над полем F_q имеет не более d корней, то все корни многочлена (4) исчерпываются элементами множества (3).

4⁰ Пусть ord a^k = m. Тогда

.

Тогда по следствию теоремы Лагранжа d делит km. Поэтому

.

Так как числа

взаимно простые, то

.                                                     (5)

С другой стороны,

.

Поэтому

.                                                     (6)

Из (5) и (6) следует, что

.                                            (7)

5⁰ Пусть числа k иd взаимно простые. Тогда НОД(k, d) = 1 и из формулы (7) следует, что ord a^k = d. Обратно, если ord a^k = d, то из формулы (7) следует, что НОД(k, d) = 1 и числа k иd взаимно простые.

6⁰ По определению всяких элемент b порядка d корень уравнения (4). По свойству 3⁰ все корни уравнения (4) исчерпываются элементами множества (3). По свойству 5⁰ элемент a^k  из множества (3) имеет порядок k тогда и только тогда, когда (k, d) = 1. Таким образом, элементов порядка d в поле F_q столько, сколько во множестве {0, 1, …, d -1} имеется чисел взаимно простых с числом d. По определению функции Эйлера таких чисел j(d). Следовательно, в поле F_q имеется j(d) элементов, имеющих порядок d.ÿ

 

6.

Выписывается элемент 1.

2. Умножается полученный элемент на x.

Переход к пункту 2.

Пример 3. Генерировать все элементы поле , f (x) = x ³ + x + 1 в полиномиальном представлении:

1, x, x ² , x ³ = x + 1, x ⁴= x (x + 1) = x ² + x, x ⁵= x (x ² + x) = x ³ + x ² = x ² + x + 1,

x ⁶= x (x ² + x + 1) = x ³ + x ² + 1= x ² + x.

 При векторном и полиномиальном представлении элементов поля сложение и вычитание выполняются естественным образом как поразрядное сложение и соответственно вычитание по модулю p. При полиномиальном представлении элементов умножении элементов поля осуществляется по следующему алгоритму:

440305

ПАМ

Толстиков А.В.

Лекция 8. Многочлены над конечными полями

 

1. Функция Мебиуса и формула обращения Мебиуса.

2. Неприводимые многочлены над конечными полями и их число.

3. Порядок многочлена над конечным полем.

4. Критерий неприводимости многочлена и способы построения неприводимых многочленов над конечным полем.

5. Конструкция конечного поля из pⁿ элементов. Вычисления в конечных полях.

 

Литература. Нечаев В.И. – С. 34-41, 79-83. С. 42-48.

Глухов М.М. и др. Т.1 – С. 244-251, 262-268; -Т2. –С. 202-220.

С. 221-237.

Самсонов Б.Б., Плохов Е.М., Филоненков А.И. Компьютерная математика (основания информатики). Ростов-на-Дону: «Феникс», 2002. – С. 228-292.

 

Конечные группы. Примеры конечных групп. Симметрическая группа. Теорема Кэли.

Определение 1. Непустое множество G называется группой, если на множестве G определена бинарная алгебраическая операция, обозначим ее значком умножение, которая каждой паре элементов a, b Î G ставит в соответствие единственный третий элемент из G, обозначаемый ab и для ее выполняются условия:

1)  - ассоциативный закон;

2)  - свойство нейтрального элемента;

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

Если операция в группе G, как и в нашем случае, обозначается значком «×», то группа G называется мультипликативной, нейтральный элемент называется в этом случае единицей, а симметричный элемент – обратным.

Если операция в группе G обозначается значком «+», то группа G называется аддитивной, нейтральный элемент называется тогда нулем, а симметричный элемент – противоположным.

Если операция в группе G обладает свойством коммутативности, т.е.

,

то группа G называется коммутативной или абелевой группой

Если число элементов в группе G конечно, то группа G называется конечной группой, если число элементов в группе G бесконечно, то группа G называется бесконечно. В случаеконечной группы число элементов в группе G обозначаем через | G | и называем порядком группы.

Примерами конечных групп являются.

Пример 1. Группа (Z _m,+) классов вычетов по модулю m. Порядок этой группы равен m.

Пример 2. Группа (Z _m ´,×) примитивных классов вычетов по модулю m. Порядок этой группы равен j(m).

Пример 3. Пусть S = {1, 2,…, n }. Подстановкой n -й степени называемлюбое взаимно однозначное отображение a множества S самого на себя. Любую подстановку a n -й степени можно записать в виде двух n -перестановок, записанных одна под другой, т.е. записать в виде:

,

где для каждого i Î S a _i = a(i). 

Если a _i = a(i) = i, то говорят, что элемент i переходит при подстановке a в элемент a _i. При этом, если a _i = i, то элемент i называется неподвижным элементом подстановки a, если   a _i ¹ i, то элемент i называется подвижным элементом подстановки a.

Композиции подстановок называется умножением подстановок: при умножение подстановок ab нужно сначала выполнить подстановку b, а затем подстановку a. Например, если

,

то для любого i Î S  (ba)(i) = b(a(i)) = b(a _i) = b _i, т.о.

.

Подстановки

называются соответственно единичной и обратной подстановкой для a.

Множество всех подстановок n -й степени обозначается символом S_n.

Справедлива теорема.

Теорема 1. Множество S_n   всех подстановок -й степени образует группу относительно операции умножения подстановок. ÿ

Группа S_n играет большую роль в математике и называется симметрической группой подстановок n -й степени.

Особое положение теории групп подстановок в теории групп поясняется следующей теоремой.

Теорема 2 (Кэли). Любая конечная группа G порядка n изоморфна некоторой подгруппе симметрической группы n -й степени S_n.

Доказательство. Пусть G = { a ₁, a ₂,…, a_n }, a ₁ = e - единичный элемент группы G. Рассмотрим n-ку (a ₁, a ₂,…, a_n). Возьмем произвольный элемент a Î G, и рассмотрим n-ку (aa ₁, aa ₂,…, aa_n). Все элементы этого множества принадлежат G и попарно различны. Действительно, если aa_i = aa_j, то по закону сокращения получаем a_i = a_j противоречие с тем, что все элементы множества { a ₁, a ₂,…, a_n } попарно различны. Таким образом, n -ка (aa ₁, aa ₂,…, aa_n) определяется однозначно и является перестановкой из элементов группы G, (aa ₁, aa ₂,…, aa_n) = = . Обозначим ее через j(a) подстановку n -степени , которая по элементу определяется однозначно. Покажем, что, если a, b Î G, a ¹ b, то j(a) ¹ j(b). Действительно, если a ¹ b, то для любого элемента a_i Î G aa_i ¹ ba_i. Поэтому элементам a, b соответствуют различные перестановки j(a), j(b). В В силу сказанного выше j - взаимно однозначное отображение G группы в группу S_n.

Покажем, что установленное соответствие является изоморфизмом группы G на подалгебру j(G) группы S_n..Покажем, что для любых двух элементов a, b Î G имеет место равенство j(ab) = j(a)j(b). Пусть

.

Тогда по определению произведения подстановок

.                                                      (1)

По определению установленного выше соответствия j имеем

(ba ₁, ba ₂,…, ba_n) = , .

Тогда в силу ассоциативного закона будем иметь

((ab) a ₁, (ab) a ₂,…, (ab) a_n) =(a (ba ₁), a (ba ₂),…, a (ba_n))=

По определению установленного выше соответствия j и формулы (1) получаем

.

Так как отображение j является изоморфизмом алгебр G и j(G), и G группа, то j(G) группа. Таким образом, G изоморфно подгруппе j(G) группы S_n. 

Следствие. Все конечные группы порядка n с точностью до изоморфизма являются подгруппами симметрической группы S_n подстановок n -й степени.

Определение 2. Подстановку aÎ S_n не равная единичной называют циклом длины k, если она перестановкой столбцов, может быть приведена к виду:

,

т.е. элементы a₁, a₂,…, a _k  подстановки переставляются по циклу, а остальные элементы остаются на своих местах.

Для записи цикла удобна более простая запись подстановки:

a = (a₁, a₂,…, a _k).

Заметим, что один и тот же цикл длины k можно записать k способами.

Два цикла называются независимыми, если они не содержат одинаковых элементов.

Теорема 3. Любая неединичная подстановка aÎ S_n либо является циклом, либо раскладывается в произведение некоторого числа попарно независимых циклов. Такое разложение однозначно с точностью до порядка следования сомножителей.

Доказательство.   Доказательство существования проведем методом математической индукции по числу m подвижных элементов в подстановке a. Число подвижных элементов в неединичной подстановке a не менее двух. Пусть   m = 2. Тогда в подстановке a два подвижных элемента a₁ и a₂ , которые образуют цикл длины 2 и подстановка a – цикл a = (a₁, a₂). Для m = 2 утверждение теоремы справедливо.

Допустим, что утверждение теоремы справедливо для любой подстановки, которая имеет менее    m подвижных элементов и докажем его для подстановки a, имеющей m подвижных элементов. Пусть a₁ – любой подвижный элемент подстановки a. Тогда имеем последовательность элементов

a₂ = a(a₁), a₃ = a(a₂) = a²(a₁), a₄ = a(a₃)= a³(a₁),…, a _i = a(a _{i - 1})= a ^{i -1}(a₁),… (1)

Так как все элементы последовательности (1) принадлежат S, то среди них обязательно найдется по крайней мере два равных:

a _i = a _j, (i < j), т.е. a ^{i -1}(a₁) = a ^{j -1}(a₁).

Применяя к обеим частям последнего равенства подстановку (a^-1) ^{i -1} получаем

. a ^{j - i} (a₁) = e(a₁) = a₁.

Таким образом, в последовательности (1) найдется элемент a _i; i > 1, равный элементу a₁. Пусть k - наименьшее натуральное число > 1 с таким свойством.

Рассмотрим цикл b = (a₁, a₂, …, a _{k - 1}). Тогда подстановка b^-1a оставляет элементы a₁, a₂, …, a _{k - 1} неподвижными и сохраняет неподвижные элементы подстановки a. Тогда число неподвижных элементов в подстановке b^-1a меньше m и к ней применимо индуктивное предположение b^-1a представляется в виде произведения независимых циклов, в которые войдут только подвижные элементы подстановки b^-1a: b^-1a = g…d. Отсюда a = bg…d. Тогда первая часть теоремы доказана.

Методом от противного доказывается единственность разложения.

Пример 1.

.