close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
ИвГУ, ф-т МиКН, курс 2
"КОМПЬЮТЕРНАЯ АЛГЕБРА"
Тема 11.
Конечные поля
(заключение)
Лектор: Н. И. Яцкин, 2014
2
3
БИНОМ НЬЮТОНА В КОНЕЧНОМ ПОЛЕ
В любом коммутативном кольце справедлива формула
возведения суммы двух слагаемых в степень (бином Ньютона):
( + ) =
=
=
+
+ ⋯+
+ ,
где биномиальные коэффициенты являются целыми числами и
вычисляются по формуле:
)∙…∙(
)
∙(
=
∙ ∙…∙
.
4
Если кольцо (или поле) имеет ненулевую характеристику ,
то для любого элемента имеет место равенство
= .
Это обстоятельство необходимо учитывать при применении
бинома Ньютона в случае, когда показатель степени
равен (или кратен) .
При = для = , … , − , биномиальные коэффициенты
оказываются кратными . В самом деле, дробь
)∙…∙(
)
∙(
=
.
∙ ∙…∙
нельзя сократить на , поскольку число – простое, а каждый
из множителей в знаменателе - меньше , так что ни один из них
(кроме 1) не может делить .
5
Следовательно, все выделенные слагаемые в формуле
бинома обнуляются и получается
"бином Ньютона for freshmen":
( + ) =
+ .
Замечание = Упражнение. Верна также формула
( − ) =
− .
Попробуйте доказать ее, используя определение
разности: = ( − ) + .
6
АВТОМОРФИЗМ ФРОБЕНИУСА
Автоморфизм какого-либо алгебраического объекта –
это биективный гомоморфизм этого объекта на себя.
Автоморфизм поля обязан быть согласованным со
сложением и умножением и сохранять единицу.
Фердина́нд Гео́рг Фробе́ниус
(Ferdinand Georg Frobenius; 1849 — 1917) –
немецкий математик, ученик Карла Вейерштрасса,
профессор Берлинского университета (занял место
умершего Леопольда Кронекера). Основные работы
Фробениуса относятся к теории групп. Он первым
доказал, что ассоциативные алгебры с делением над
вещественными числами существуют только в
пространствах размерности один (вещественные
числа, ℝ), два (комплексные числа, ℂ) и четыре
(кватернионы, ℍ).
7
Теорема 7 (об автоморфизме Фробениуса).
Раcсмотрим конечное поле , где = .
Отображение
:
→ ; ( ) = ; ∈
является автоморфизмом поля
на себя.
Множество неподвижных точек этого
автоморфизма является простым подполем
в поле .
(*)
8
Доказательство. Для отображения (**) необходимо установить
справедливость следующих свойств:
( + ) = ( ) + ( );
( ∙ ) = ( ) ∙ ( );
( )= .
(**)
(***)
(****)
Условие (****) выполняется:
= ; условие (***) - тоже:
( ∙ ) =
∙
[здесь используется коммутативность полевого
умножения]. Остается доказать формулу (**):
( + ) =
+
,
но это есть не что иное как "бином Ньютона for freshmen".
(**)
9
Итак, является гомоморфизмом поля в себя. Поле является
частным случаем кольца, поэтому можно применить первую теорему о
гомоморфизмах колец (см. курс фундаментальной алгебры, 3-й семестр).
Ядро
( ) должно быть идеалом в поле. А поле (как известно
из того же курса) не имеет идеалов, кроме нулевого и несобственного
(совпадающего со всем полем). Последнее невозможно, поскольку тогда
( )= ,
сам гомоморфизм был бы нулевым, а наш
≠ . Значит,
и (по названной выше теореме) является мономорфизмом. Однако
инъективное отображение конечного множества в себя обязательно
является сюръективным (и, следовательно, - биективным)
отображением на себя. ∎
10
СТЕПЕНИ АВТОМОРФИЗМА ФРОБЕНИУСА
Всякая степень (в смысле композиции) всякого автоморфизма сама
является автоморфизмом. Для автоморфизма Фробениуса
и для любого элемента
∈
(где
( )=(
и, далее, при любом целом :
( )=
при
=
;
получится:
( )=
.
=
) будем иметь:
) =
;,
11
Но для любого элемента
поля (содержащей
−
∈
∗
из мультипликативной группы
элементов) по теореме Лагранжа получается
=
и, следовательно,
= , т. е. оказывается, что
=
(тождественный автоморфизм).
Это означает, что автоморфизм Фробениуса порождает
циклическую (порядка − ) подгруппу в группе
(
) всех
автоморфизмов поля
.
(Фактически порождается вся группа
автоморфизмов.)
12
ПОДПОЛЯ КОНЕЧНЫХ ПОЛЕЙ
Всякое подполе конечного поля
конечным полем
число
′=
=
=
(где
) само является
, причем, как объяснялось в предыдущей теме,
должно быть некоторой степенью числа
′:
=( ) .
′ поля ′ также должен быть
-примарным числом:
=
; поэтому
=
и =
т. е. должна иметь место делимость: | .
(При
= получается простое подполе .)
С другой стороны, порядок
,
13
НЕПОДВИЖНЫЕ ТОЧКИ
АВТОМОРФИЗМА ФРОБЕНИУСА
И ЕГО СТЕПЕНЕЙ
Элементы простого подполя
уравнению
=
в поле
удовлетворяют
, т. е. являются неподвижными точками
автоморфизма .
Других неподвижных точек нет, поэтому справедливо следующее
описание простого подполя:
=
( )={ ∈
: ( ) = }.
14
Теорема 8 (о подполях в конечном поле). Рассмотрим
конечное поле
. Для всякого делителя | в поле
существует единственное подполе порядка
: оно
может быть описано как подмножество элементов
данного поля, инвариантных относительно степени
автоморфизма Фробениуса :
(
)={ ∈
других подполей в
:
( )= }≅
нет.
Доказательство см. в учебной литературе. ∎
;
15
ФУНКЦИОНАЛЬНАЯ (вместо табличной)
ВЕРСИЯ ПРОЦЕДУРЫ, ОПРЕДЕЛЯЮЩЕЙ
АРИФМЕТИКУ ПОЛЯ ГАЛУА
Вместо таблиц (сложения, умножения, обращения и т. д., см. в предыдущей
теме процедуру GaloisField) ниже процедурно определяются функции
(от одной или двух переменных), задающие арифметику конечного поля.
Кроме того, добавлены процедуры:
- вычисления автоморфизма Фробениуса и его степеней,
- перечисления подполей.
16
> GField:=proc(p::prime,n::posint,x::name)
local numb,i,j,h,f,s,signal,ord,a,subf;
global q,f0,g,gadd,gmul,gopp,ginv,glog,
gfrob,gFrob,gSubfs;
# Применяем подход с объявлением
# возвращаемых данных глобальными переменными:
#
#
#
#
#
#
q – порядок поля;
f0 – неприводимый примитивный многочлен,
задающий поле;
g – список элементов поля;
gSubfs – список подполей
(каждое из них само задается списком);
17
#
#
#
#
#
#
#
#
#
gadd,gmul – функции двух переменных,
задающие сложение и умножение;
gopp,ginv,glog – функции одной переменной,
вычисляющие противоположный и обратный элементы,
а также - логарифмы;
gfrob – функции одной переменной,
задающая автоморфизм Фробениуса;
gFrob – функции двух переменных,
задающая степени автоморфизма Фробениуса.
18
q:=p^n;
g:=[];
for i from 0 to q-1 do
numb:=convert(i,base,p);
f:=sort(
convert(
sum('numb[h]*x^(h-1)','h'=1..nops(numb)),
polynom),
x);
g:=[g[],f];
end do;
# Сформирован список g.
19
for i from q to 2*q-1 do
numb:=convert(i,base,p);
f:=sort(convert(sum('numb[h]*x^(h-1)',
'h'=1..nops(numb)),
polynom),
x);
if Rem(x^(q-1)-1,f,x) mod p=0 then
signal:=true;
for s from 2 to q-2 do
if irem(q-1,s)=0 and
Rem(x^(s)-1,f,x) mod p=0 then
signal:=false;
break;
end if;
end do;
20
if signal then
f0:=f;
break;
end if;
end if;
end do;
# Вычислен многочлен f0(x).
21
gadd:=proc(a,b);
if a in g and b in g then
RETURN(Rem(a+b,f0,x) mod p);
end if;
end proc;
# Определена функция gadd(a,b).
gmul:=proc(a,b);
if a in g and b in g then
RETURN(Rem(a*b,f0,x) mod p);
end if;
end proc;
# Определена функция gmul(a,b).
22
gopp:=proc(a)
local b;
if a in g then
for b in g do
if Rem(a+b,f0,x) mod p=0 then
RETURN(b);
end if;
end do;
end if;
end proc;
# Определена функция gopp(a).
23
ginv:=proc(a)
local b;
if a in g and a<>0 then
for b in g do
if b<>0 and Rem(a*b,f0,x) mod p=1 then
RETURN(b);
end if;
end do;
end if;
end proc;
# Определена функция ginv(a).
24
glog:=proc(a);
if a in g and a<>0 then
for j from 0 to q-2 do
if Rem(x^j-a,f0,x) mod p=0 then
RETURN(j);
end if;
end do;
end if;
end proc;
# Определена функция glog(a).
25
gfrob:=proc(a)
local b,i;
if a in g then
b:=1;
for i from 1 to p do
b:=gmul(b,a);
end do;
RETURN(b);
end if;
end proc;
# Определена функция gfrob(a),
# задающая автоморфизм Фробениуса a->a^p.
26
gFrob:=proc(a,k::integer)
local s,b,i;
s:=k mod n;
if a in g then
if s=0 then
RETURN(a);
else
b:=gfrob(a);
for i from 1 to k-1 do
b:=gfrob(b);
end do;
RETURN(b);
end if;
end if;
end proc;
27
# Определена функция gFrob(a,k),
# задающая k-ю степень автоморфизм Фробениуса:
# (a,k)->a^(p^k).
gSubfs:=[];
for s from 1 to n-1 do
if irem(n,s)=0 then
ord:=p^s;
subf:=[];
for a in g do
if gFrob(a,s)=a then
subf:=[subf[],a];
end if;
end do;
gSubfs:=[gSubfs[],[ord,subf]];
end if;
end do;
28
# Определен список списков gSubfs вида
# [порядок подполя, [список элементов подполя]].
RETURN(q,f0,g,gadd,gmul,gopp,ginv,glog,
gfrob,gFrob,gSubfs);
end proc;
# Возвращаем последовательность из 11 ответов.
29
Пример 1. Арифметика в поле
.
> GField(3,4,x);
81, x 4x2, [ 0, 1, 2, x, x1, x2, 2 x, 2 x1, 2 x2, x 2, x 21, x 22, x 2x,
x 2x1, x 2x2, x 22 x, x 22 x1, x 22 x2, 2 x 2, 2 x 21, 2 x 22,
2 x 2x, 2 x 2x1, 2 x 2x2, 2 x 22 x, 2 x 22 x1, 2 x 22 x2, x 3, x 31,
x 32, x 3x, x 3x1, x 3x2, x 32 x, x 32 x1, x 32 x2, x 3x 2,
x 3x 21, x 3x 22, x 3x 2x, x 3x 2x1, x 3x 2x2, x 3x 22 x,
x 3x 22 x1, x 3x 22 x2, x 32 x 2, x 32 x 21, x 32 x 22, x 32 x 2x,
x 32 x 2x1, x 32 x 2x2, x 32 x 22 x, x 32 x 22 x1,
x 32 x 22 x2, 2 x 3, 2 x 31, 2 x 32, 2 x 3x, 2 x 3x1, 2 x 3x2,
30
2 x 32 x, 2 x 32 x1, 2 x 32 x2, 2 x 3x 2, 2 x 3x 21, 2 x 3x 22,
2 x 3x 2x, 2 x 3x 2x1, 2 x 3x 2x2, 2 x 3x 22 x, 2 x 3x 22 x1,
2 x 3x 22 x2, 2 x 32 x 2, 2 x 32 x 21, 2 x 32 x 22, 2 x 32 x 2x,
2 x 32 x 2x1, 2 x 32 x 2x2, 2 x 32 x 22 x, 2 x 32 x 22 x1,
2 x 32 x 22 x2 ], gadd, gmul , gopp, ginv , glog , gfrob , gFrob , [ [ 3, [ 0, 1, 2 ] ], [
9, [ 0, 1, 2, x 3x 22 x, x 3x 22 x1, x 3x 22 x2, 2 x 32 x 2x,
2 x 32 x 2x1, 2 x 32 x 2x2 ] ] ]
Разберемся подробнее. Порядок поля = , определяющий многочлен
( )=
+ + , список элементов g и список подполей gSubfs
выданы в окончательно вычисленном виде. Обратите внимание на то, что
в поле из 81 элемента присутствуют подполя из 3 и из 9 элементов (причем
первое содержится во втором), а подполя из 27 элементов нет. Почему?
31
{ , , }
=
↓
{ , , ,
+
+
+ ,
+
,
+
+
+
+
+ ,
+ ,
+
+
+
+
+ ,
+ }
≅
↓
32
Возвращаемые функции представлены на уровне имен. Поскольку они
назначены глобальными переменными, то их можно вызывать не только
как части общего ответа, но и – по именам.
См. умножение 75-го элемента поля на 17-й и др. действия:
> gmul(g[75],g[17]);
2 x 22
> ginv(g[75]); glog(g[75]);
2 x2
38
> g[81],gfrob(g[81]);
2 x 32 x 22 x2, 2 x 3x 22 x2
33
Простое подполе . выражается как множество
неподвижных точек автоморфизма Фробениуса ,
подполе, изоморфное , вычислено в процедуре как множество
неподвижных точек автоморфизма .
Пример 2. Арифметика в поле
>gf64:=GField(2,6,x);
.
34
gf64 := 64, x 6x1, [ 0, 1, x, x1, x 2, x 21, x 2x, x 2x1, x 3, x 31, x 3x,
x 3x1, x 3x 2, x 3x 21, x 3x 2x, x 3x 2x1, x 4, x 41, x 4x,
x 4x1, x 4x 2, x 4x 21, x 4x 2x, x 4x 2x1, x 4x 3, x 4x 31,
x 4x 3x, x 4x 3x1, x 4x 3x 2, x 4x 3x 21, x 4x 3x 2x,
x 4x 3x 2x1, x 5, x 51, x 5x, x 5x1, x 5x 2, x 5x 21, x 5x 2x,
x 5x 2x1, x 5x 3, x 5x 31, x 5x 3x, x 5x 3x1, x 5x 3x 2,
x 5x 3x 21, x 5x 3x 2x, x 5x 3x 2x1, x 5x 4, x 5x 41, x 5x 4x,
x 5x 4x1, x 5x 4x 2, x 5x 4x 21, x 5x 4x 2x, x 5x 4x 2x1,
x 5x 4x 3, x 5x 4x 31, x 5x 4x 3x, x 5x 4x 3x1, x 5x 4x 3x 2,
x 5x 4x 3x 21, x 5x 4x 3x 2x, x 5x 4x 3x 2x1 ], gadd , gmul,
gopp, ginv , gdiv , glog , gfrob , gFrob , [ [ 2, [ 0, 1 ] ],
[ 4, [ 0, 1, x 5x 4x 3x, x 5x 4x 3x1 ] ], [
8, [ 0, 1, x3x2x, x3x2x1, x4x2x, x4x2x1, x4x3, x4x31 ] ]
]
35
В данном примере имеем три собственных подполя:
- простое подполе ;
- подполе, изоморфное ;
– подполе, изоморфное .
Второе подполе не содержится в третьем, пересечением этих двух
подполей является простое подполе.
36
{ , }
=
↓ ↘
{ , ,
+
+
+
+
+
≅
+ ,
+ }
{ , , + + , + + + ,
+ + , + + + ,
+ , + + }
≅
↘ ↓
37
Покажем, как вычисляются указанные выше подполя с помощью
автоморфизма Форбениуса ( ) =
. Ниже, в четырехстолбцовой
таблице показаны элементы поля
и результаты применения к
ним автоморфизмов ,
,и
. Выделены те элементы, для
которых
( ) = (они образуют простое подполе );
( ) = (они образуют подполе , включающее );
( ) = (они образуют подполе , включающее ).
> for a in g do
[a,gFrob(a,1),gFrob(a,2),gFrob(a,3)];
od;
38
( )
( )
( )
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ +
+
+ +
+ +
+ + +
+
+
+
+
+
+
+
+ +
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ +
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
39
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ + +
+ +
+ + +
+ + +
+ + + +
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ +
+
+ +
+ +
+ + +
+
+ +
+ +
+ + +
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ +1
+ + +
+ +
+ + + +
+ + +
+ +
+
+ +
+ +
+ + +
+
+ +
+ + +
+ + + +
+ +
+ + +
+
+ +
+
+
+
+
+
+
+
+
+
+
+ +
+
+ + +
+
+ +
+
+ +
+ +
+
+ +
+
+ + + +
+ + +
+ +
+
+ + +
+ + + +
+
+ +
+ + + +
+
+
+
+
+
+
+
+
+
+
+
+
40
+
+
+
+
+
+
+
+
+
+ + +
+
+ +
+ +
+ + +
+ +
+ + +
+ + +
+ + + +
+ +
+ + +
+ + +
+ + + +
+ + +
+ + + +
+ + + +
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ + + +
+ + +
+
+
+
+
+
+
+
+
+
+
+
+ + + +
+ +
+ + +
+ + +
+ + + +
+
+
+
+
+
+
+
+ + +
+ + +
+ +
+ + +
+ +
+ + + +
+ + +
+
+
+
+
+
+
41
Конечными полями можно заниматься
бесконечно долго (шутка).
Эта тема практически неисчерпаема
и чрезвычайно полезна (для здоровья, опять шутка).
42
1/--страниц
Пожаловаться на содержимое документа