Конечные поля
Цель работы: Изучитьконструкцию и простейшие свойства конечных полей. В частности, изучить напримерах конечных полей понятие степени расширения, конструкцию и однозначнуюопределенность поля разложения, простые поля, понятие примитивного элемента,строение конечной, мультипликативной подгруппы поля. Познакомиться сарифметикой конечных полей. Решить упражнение.
Докажем, что многочлен
/>
неприводим над
/>.
/>.
Корней нет. =>Многочлен неприводим.
Построим расширениеполя /> степени />. Пусть /> – корень />, т.е.
/>,
тогда />
Получим />: />.
/>
расширение /> степени 3.
Разделим
/>
/>.
/>.=
/>
Cоставимсистему:
/>=> /> Пусть />, тогда /> => />
При β=3 => /> γ=2
Отсюдаполучаем, что
/> />
/> следовательно />. Если qпорождает /> – то, онпримитивный. Найдем порядок />. Так как порядок элемента делит порядок группы, порядок /> может быть 2, 4, 31, 62, 124.
/>.
/>
Элемент θ – неявляется примитивным элементом GF(125),т.к не выполняются условия. Программа, проверяющая,будет ли /> примитивнымэлементом поля />.
TForm1*Form1;
classPolynom
{public:
int*coef;
intdeg;
Polynom();
Polynom(char*);
Polynom(int);
Polynom(Polynom*);
~Polynom();
Polynomoperator =(string);
Polynom*operator *(Polynom *);
Polynomoperator /(Polynom);
Polynom*operator %(Polynom *);
intoperator [](int);
voidoperator ++();
booloperator
booloperator ==(Polynom *);
Polynom*norm();
intcoef_count();
char*print();
};
Polynom:: Polynom()
{coef = new int[1];
coef[0]= 0;
deg= 0;
}
Polynom*Polynom :: norm()
{int f = 0;
for(inti = 0; i
if(coef[i] != 0 )
{f = i;
break;
}
intdeg_tmp = deg — f;
Polynom*tmp = new Polynom(deg_tmp+1);
for(inti = f; i
tmp->coef[i-f]= coef[i];
returntmp;
}
Polynom:: Polynom(char *str)
{deg = strlen(str)-1;
coef= new int[deg+1];
for(inti = 0; i
coef[i]= str[i] — 48;
}
Polynom:: Polynom(int d)
{deg = d-1;
coef= new int[d];
for(inti = 0; i
coef[i]= 0;
}
Polynom:: Polynom(Polynom *p)
{coef = p->coef;
deg= p->deg;
}
Polynom:: ~Polynom()
{delete coef;
}
intPolynom :: operator[](int it)
{return ( coef[it] );
}
intPolynom :: coef_count()
{int count = 0;
for(inti = 0; i
{if( coef[i] > 0 )
count++;
}
returncount;
}
Polynom*Polynom :: operator*(Polynom *B)
{Polynom *A = this;
Polynom*C = new Polynom(A->deg + B->deg + 1);
for(inti = A->deg; i >= 0; i--)
{for(int j = B->deg; j >= 0; j--)
{C->coef[i+j] += A->coef[i] * B->coef[j];
C->coef[i+j]%= 5;
}
}
returnC;
}
boolPolynom :: operator
{if( deg deg )
returntrue;
else
returnfalse;
}
boolPolynom :: operator ==(Polynom *B)
{Polynom *A = this;
if(A->deg != B->deg )
returnfalse;
for(inti = 0; i deg; i++)
if(A->coef[i] != B->coef[i] )
returnfalse;
returntrue;
}
intobr(int a)
{a = 5 — a;
a%= 5;
returna;
}
Polynom*Polynom :: operator %(Polynom *B)
{Polynom *tmp = this;
if(tmp->deg deg )
{return tmp;
}
for(inti = 0; i deg-tmp->deg; i++)
if(tmp->coef[i]>= 1)
{int tmp_coef = tmp->coef[i];
tmp->coef[i]= 0;
for(intj = 1; j deg; j++)
{tmp->coef[j] += obr(B->coef[j])*tmp_coef;
tmp->coef[j]%= 5;
}
}
tmp= tmp->norm();
returntmp;
}
voidPolynom :: operator++()
{bool flag = false;
for(inti = deg; i >= 0; i--)
{coef[i]++;
coef[i]%= 5;
if(coef[i] == 0 )
{flag = true;
}
else
flag= false;
if(flag == false )
break;
}
if(flag )
{int *tmp = new int[deg+2];
tmp[0]= 1;
for(inti = 1; i
{tmp[i] = coef[i-1];
}
coef= tmp;
deg= deg+1;
}
}
char*Polynom :: print()
{char *s = new char[deg*3+(deg-1)*3 + deg*3 + deg*3];
inti = 0, f = 0;
s[0]= 0;
while( i
{if (coef[i])
{if(f)
strcat(s,"+ ");
f= 1;
switch(deg-i)
{case 0:
wsprintfA(s,"%s%d", s, coef[i]);
break;
case1:
if(coef[i] == 1 )
wsprintfA(s,"%sq", s);
else
wsprintfA(s,"%s%d*q", s, coef[i]);
break;
default:
if(coef[i] == 1)
wsprintfA(s,"%sq^%d", s, deg-i);
else
wsprintfA(s,"%s%d*q^%d", s, coef[i], deg-i);
};
}
i++;
}
if(!f)
strcat(s,«0»);
returns;
}
boolTestPrimitive(Polynom *poly, Polynom *irr)
{Polynom *tmp = poly;
Polynom*one = new Polynom(«1»);
for(inti = 2; i deg); i++)
{poly = (*poly) * tmp;
poly= (*poly) % irr;
Form1->Memo1->Text= Form1->Memo1->Text + «q^» + i + " =" + ' ';
Form1->Memo1->Text= Form1->Memo1->Text + poly->print();
Form1->Memo1->Lines->Add("");
if(*poly == one && i != pow((double)5, irr->deg)-1 )
{
Form1->Memo1->Text= Form1->Memo1->Text + i;
Form1->Memo1->Lines->Add("");
returnfalse;
}
}
returntrue;
}
Polynom*DecToBin(int q)
{string m = "";
inta;
do
{if( q % 2 == 0 )
m+= «0»;
else
m+= «1»;
q/= 2;
}while( q != 0 );
Polynom*poly = new Polynom(m.size());
for(inti = 0; i
poly->coef[i]= m[m.size()-i-1] + 48;
returnpoly;
}
Polynom*FindPrimitiveElement(Polynom *irr)
{Polynom *test = new Polynom(«4»);
while(test->deg deg )
{
(*test)++;
Form1->Memo1->Text= Form1->Memo1->Text + «q^» + 1 + " =" + ' ';
Form1->Memo1->Text= Form1->Memo1->Text + test->print();
Form1->Memo1->Lines->Add("");
if(TestPrimitive(test, irr) )
break;
}
returntest;
}
__fastcallTForm1::TForm1(TComponent* Owner)
:TForm(Owner)
{
}
void__fastcall TForm1::Button1Click(TObject *Sender)
{Polynom *IrrPoly = new Polynom(LabeledEdit1->Text.c_str()); // Считываеммногочлен
Memo1->Text= Memo1->Text + «Неприводимый многочлен: » + IrrPoly->print(); //Вывожу
Memo1->Lines->Add("");
Polynom*prim = FindPrimitiveElement(IrrPoly); // Находимпримитивныйэлементполя
LabeledEdit2->Text= prim->print();Результаты выполнения программы:
/>
Фундаментальная группа
Цель работы: изучитьопределение и свойства фундаментальной группы топологического пространства.Познакомиться с понятием клеточного комплекса, со способом построенияклеточного комплекса путем последовательного приклеивания клеток. Научитьсязадавать группы с помощью образующих и их соотношений (т. е. с помощьюкопредставлений) и распознавать группы по их копредставлениям. Научитьсяприменять алгоритм вычисления фундаментальной группы клеточного комплекса.
Список групп-эталонов:
1. Циклические группы:
/> x/ />=1>,x– любое
2. Бинарные группыдиэдра:
/>=x, y //>=/>=/> >,n ≥ 2
3. Бинарные группытетраэдра и октаэдра:
/>=x, y / />=/>=/>,/>>,n =1, 2
4. Группы вида:
/>= x,y/ />>, k≥2,
5. Прямые произведениявышеуказанных групп на циклические.
Во всех случаях индексвнизу показывает число элементов групп.
/>
На рисунке условноизображен двумерный клеточный комплекс, т.е. топологическое пространство,получающееся приклеиванием нескольких двумерных клеток (дисков) к одномерномукомплексу (графу). Рисунок нужно понимать так: каждая «деталь» видасимволизирует вершину графа, каждая склейка «отростков» вида
/>
1. –ребро. Например, рисунок А символизирует граф на рисунке В. />
Далее требуетсяполучить копредставление фундаментальной группы, для этого проделаем следующее:
1) По очереди разрезаемрёбра графа, обозначая их буквами и указывая направления до тех пор, пока неполучится дерево (связанный граф без циклов), см. рис. ниже. Эти буквы будутслужить образующими группы:
/>
2) Выписываемсоотношения (слова), которые показывают, как кривые проходят по разрезаннымрёбрам. Эти соотношения таковы: 1. />2. />=1 3. />=1 4. />=1 5. />=1 6. />=1 3)Приводимвыписанное копредставление к копредставлению одной из эталонных групп.
/> Введём/> Витоге получается />, а именно />