Какво трябва да знаем?

Примери за разширения на полета

Станчо Вълканов Павлов

В тази статия се разглеждат примери на разширение на полета. Това е процес, при който от едно изходно поле се получава друго, съдържащо първото като своя част. Той е възлов за разбирането на теорията на Галоа.
Въпреки достъпността на тази постройка, тя не е застъпена в средното училище а във висшите училища се преподава на доволно неразбираем за народа начин. Затова написах статията.

1. Разширение на Q с корените на 2 и 3

Към рационалните числа трябва да добавим корен от 2 и корен от 3 и да получим множество в което елементите могат да се събират, умножават и делят без да го напускат. Те трябва да образуват поле.
Понеже полето съдържа произведенията и частните на своите елементи в Съставно разширение-_1Q_SQRT_2_3 трябва да се съдържа и корен от 6 а и всички елементи от вида Елементи_1Q_SQRT_2_3_6 .
Що се отнася до частните - за тях трябва де си припомним рационализирането на знаменателя. Ето два примера:
Рационализиране на знаменателя-_RatDen
Оказва се, че разширението, получено с добавяне на 2 елемента може да се получи с добавянето само на един.
Да добавим към Q елемента Ирационално число-_1Alpha_2_Pl_3 .       Ирационално число-_1DivAlpha
Тогава разширението Q(α) ще съдържа корените на 2 и 3.
Това разширение ще съдържа и степените на α. Но Ирационално число-_1SQRAlpha Така, че разширението ще съдържа и корен от 6.
Но тогава ще съдържа и всички елементи на Съставно разширение-_1Q_SQRT_2_3
Така, че Съставно разширение _1Q_SQRT_2_3 = Просто разширение _1QSQRT2SQRT3 . и вместо да добавяме два елемента можем да минем само с един.
Разширения, които са получени от изходното поле с добавяне само на един елемент се наричат прости.
Ако един елемент от разширението е корен на уравнение с коефициенти от изходното поле той се нарича алгебричен.
Ако всички елементи от разширението са алгебрични то се нарича алгебрично разширение над изходното поле.
Досега разгледаните разширения на Q са алгебрични. Алгебрично е и числото:
Числото на Гаус_1FrmGaus
Тази формула Гаус я е измислил на 18 години. Тя е свързана с построяването на правилен 17-тоъгълник с линийка и пергел.
Този успех го е окуражил да стане математик. К'во ще кажете? А ... !?

2. Q(i)

Един полином с рационални коефициенти ( полином над Q ) се нарича неприводим, ако не може да се разложи на произведение на два полинома над Q със степени по-големи от 0. Например, полиномът x2 + 2 е неприводим над Q .
Полето Q(i) се получава от Q, чрез добавяне на елемент i, който е корен на неприводимия над Q многочлен f (x) = x2 + 1. Q(i) се състои от елементи от вида p + qi , където p,q Î Q. Тези елементи могат да се събират и изваждат, като на i е гледа като на променлива.
При умножаването обаче, i2 е заменя с -1.
Делението е още по особено: Комплексни числа_2Dev1 -дотук - нищо особено.
На i се гледа като на обикновена променлива, както казахме.
После умножаваме числителя и знаменателя на 2-i: Комплексни числа _2Dev2
Заменяме i2 с -1 и вижте, че се получава число от Q(i): Комплексни числа _2Dev3 .
Полето Q(i) се нарича поле на рационалните Гусови числа.
Целите елементи - от вида a + bi, където a и b са цели числа се нарича пръстен на целите Гаусови числа.
За него, даже, има разработена Теория на числата.

3. Zp

Най-простото крайно поле е множеството от остатъци по модул p. p - просто число.
Всеки ненулев елемент от това множество има обратен по отношение на умножението.
Ако 1 ≤ k ≤ p-1 то k е взаимно просто с p.
Тогава съществуват две цели a и b числа от Z, такива че ak+bp=1.
Следователно a ≡ 1 (mod p).
Друг начин за доказване на това твърдение е чрез малката теорема на Ферма. kp-1 ≡ 1 (mod p) и следователно kp-2 ≡ k-1 (mod p)
Привеждам таблиците за събиране и умножение по модул 5.
+  0   1   2   3   4 
001234
112340
223401
334012
440123
     
.  0   1   2   3   4 
000000
101234
202413
303142
404321

4. GF(22)(x2 + x + 1)

Полиномът x2 + x + 1 не може да се разложи на множители над Z2 ={0, 1}, защото елементите на Z2 не са негови корени.
Полиноми, които не могат да се разложат на произведение от два полинома над Z2 със степени по-големи от нула се наричат неприводими над Z2 .
Над Z2 полиномът x2 + 1 е приводим, защото x2 + 1 = (x+1)(x+1).       Това е така, защото в Z2 2 = 0.
Но за неприводимост вече разговаряхме.
Сега да разгледаме множеството от полиноми от първа степен над Z2 с променлива α: Z2(α) = {0, 1, α, α+1 } .
Те могат да се събират по обичайния начин по модул 2.
Ако при умножението на два или повече полинома се получи полином от степен по голяма от 1 го заменяме с остатъка при делението му на α2 + α + 1, като при това отново работим по модул 2 при коефициентите.
Ще получим в реултат отново полином от Z2(α).
Например:
Намиране на остатъка _3DblMod
Подобни преобразования, основани на остатъците при деление на 2 и на полинома x2 + x + 1 се наричат сравнения по двоен модул.
Самият модул се означава с ( 2, x2 + x + 1 ).
По-долу са приведени таблиците за събиране и умножение, като в първата е изключена нулата а във втората е изключена и единицата.
+ 1 α α+1
1 0 α+1 α
α α+1 0 1
α+1 α 1 0
     
. α α+1
α α+1 1
α+1 1 α+1

5. GF(23)( x4 + x3 + x2 + x + 1)

Над Z2 полиномът f(x) = x4 + x3 + x2 + x + 1 е неприводим, защото: f(x) няма линейни множители, понеже нито един от елементите на Z2 ={0, 1} не е негов корен. Така, че ако той се разлага на множители те са два от втора степен.
Изключваме тези, които имат корени от Z2 . Остава само един възможен: g(x) = x2 + x + 1.
Разделяйки f(x) на g(x) получаваме f(x)= x2g(x) + x + 1 , което показва че f не се дели на g.
Разглеждаме множеството от полиноми от Z2(α) от степен по-малка от 3. За краткост ще записваме само коефициентите им.
Например 1011 за нас ще означава полиномът 1x3 + 0x2+1x + 1.
Събирането е ясно. То се извършва както при полиномите над Z но по модул 2, където 1+1=2=0. Без пренос (наум)!
Сега за умножението: То се извършва както в Z , като отново 1+1=0 но полученото произведение се замества с остатъка от делението на при f(x), като действията отново се извършват по модул 2.
Например:
Писмено умножение_4Mult1

Сега трябва да разделим полученото произведение на f(x).
Писмено деление_4Div1
Осатъкът е 0011.
Има едно наблюдение, което да голяма степен облекчава нещата в тази аритметика.
От f(x) = x4 + x3 + x2 + x + 1 ≡ 0 по модул f(x) следва, че x4x3 + x2 + x + 1 или просто, че 10 000 = 1 111.
Т.е. единица в 4-тия разряд може да се замени с четири единици в по-младшите разряди.
Разрядите се броят отдясно-наляво като се започне от нула.
При това умножение ролята на единица се изпълнява от 0001.
Този тип сравнения, едновременно по полином и по модул 2 се наричат сравнения по двоен модул ( 2, x4 + x3 + x2 + x + 1 ), както бе казано.
Нашата цел е да попълним таблицата за умножение на ненулевите елементи.
Ще започнем с намирането на степените на x → 0010 ; x2 = 0100 ; x3 = 1000
Изобщо умножаването с x допълва една нула отдясно.
Но какво ще се получи, ако се получи единица в четвъртия разряд?
Тя трябва да се замести с 1 111 и да се прибави към младшите 4 разряда. x4 = 10000 = 0000 + 1111 = 1111.
Интересно! Да продължим: x5 = 11110 = 1110 + 1111 = 0001.
Достигнахме да единицата, което показва, че редът на x е 5 и разбира се той дели реда на мултипликативната група който е 15.
Ако продължаваме с умножението на x нещата ще се повторят.
Но нашата цел е да открием такъв елемент, който поражда цялата мултипликативна група, т.е. неговият ред да е 15 а не 3 или 5.
Редът на всеки елемент на група е делител на реда на групата.
Да опитаме с x + 1 → 0011. Тук нещата са по сложни.
При умножението с 0011 наборът трябва да се събере със същия, но изместен с един разряд вляво, както при писменото умножение. 1011*0011 = 1 011+10 110=11 101.
Може би така е по-ясно: Писмено умножение_4Mult2
За да получим окончателния резултат трябва да заменим единицата в петия разряд с 4 единици в младшите разряди и да съберем: Намиране на остатъка_4Red1
Можем да забележим, още, че наличието на 1 в петия рязряд "обръща" разрядите в младшите 4: Обръщане на младшите 4 разряда _4Inv
Въоръжени с тези знания и онези които ще получим в практиката, да влезем в бой с незнанието умножавайки x + 1 = q = 0011 със себе си 15 пъти.
Степени_4Pow
Сега е лесно да намираме реципрочния елемент.
Вярно е, че q15 = 1. Тогава (qa)-1 = q15-a , така, че ако искаме да намерим обратния набор на набора A ние трябва да намерим в таблицата такава степен n, че A = qn .
После от 15 изваждаме степента n , за да получим степента m = 15 - n. И отново от таблицата намираме B = A=qm . Това е обратният елемент на A.
Намирането на n прилича на логаритмуване, затова ще означаваме n с lgA.
Например, нека A = 1001. Тогава lgA = 8. m = 15 - lgA = 7.   A-1 = q7 = 0111
Не вярвайки на успеха си да проверим това с писмено умножение:
Писмено умножение _4Mult3
Да припомним: разрядите се номерират отдясно-наляво започвайки с 0: Намаляване на разрядите_4Red2 Заради единицата в 5-ия разряд, обръщаме съдържанието разрядите 4-1. Нулевият разряд остава непроменен. Единицата в 4-тия разряд изчезва.
Така, че се получава 0001 - единицата при умножението -Ура!
Същата таблица, подредена по нарастване на аргумента на A.
Таблица на логаритмите_4Lg
Таблиците могат да помогнат не само при намирането на обратния елемент спрямо умножението но и при умножението, като се използва правилата lg(AB) = lgA+ lgB и lg(A/B) = lgA - lgB. Тези равенства трябва да се разбират като такива по mod 15. Например: желаем да пресметнем (0101)2 . Логиримуваме двете страни: lg(0101)2 = 2. lg(0101) = 2.2 = 4. Сега антилогаритмуваме: q4 = 1110.
Проверяваме: Писмено умножение _4Mult4
Чертичката означава, както и преди "обръщане" на четири разряда предхождащи единицата в по-старшия разряд.
Както се вижда- всичко е наред.
Сега ако искаме можем и да попълним таблицата за умножение.
Но ние не искаме, защото противникът и без това е сразен, а добротата ни задължава да проявим милост към него.

6. GF(32) (x2 + x + 2)

f(x) = x2 + x + 2 няма линейни множители в Z3 , понеже нито един от елементите на Z3 = {0, 1, 2} не е негов корен.
Елементите от множеството на остатъците ще означаваме, както и преди, като набори ab където a, b Î Z3 .
Ето елементите на остатъците от Z3[x] по двоен модул ( 3, x2 + x + 2 ): {00, 01, 02, 10, 11, 12, 20, 21, 22}.
Това множество ще означаваме с GF(32) (x2 + x + 2).
Събирането го знаем. То се извършва по модул 3 без пренос (наум).
Например 22+21=10.
Що се отнася до произведението - отново нищо ново.
Извършва се писмено, като при събирането се работи по модул 3.
От сравненията x2 + x + 2 ≡ 0 ↠ x2 ≡ -x - 2 ≡ 2x + 1 следва, правилото, че ако се появи единица в втория рязряд тя може да се замести с 21 в предните две разряда.
Да припомним, че номерацията на разрядите започва от 0 и се отчита отляво - надясно.
Или 100 = 21.
По подобен начин се обосновава, че x2 ≡ 4x - 4 ≡ x + 2 по двоен модул ( 3, x2 + x + 2 ).
Ето пример, как един полином от висока степен може да се сведе до такъв от първа с използване на описаните правила:
Полиномът е A = 121 022.
Единицата в старшия разряд я заменяме със събираемото 21 000 и го прибавяме към младшите разряди на A: A=21 022+21 000 = 12 022.
Отново заменяме единицата от четвъртия разряд с 2 100 и събираме с младшите разряди на новото A: A = 2 022 + 2 100 = 1 122.
Постъпваме така отново: A = 122 + 210 = 002 = 02.
Разбира се, по-добре е описаните действия да се подредят в таблица, в която са нанесени и номерата на разрядите:
Писмено умножение _5Mult1
Нашата цел е да попълним таблицата за умножение на ненулевите елементи по двоен модул ( 3, x2 + x + 2 ) .
Да започнем да умножаваме 10 само със себе си в надеждата този елемент да има ред 8, колкото е броят на ненулевите елементи от GF(32).
Умножаването с 10 е просто - трябва да се допълни една нула в най-младшия рязряд и да извършим действията, водещи до намаляване на степента.
q2 = 100 = 21.
q3 = 210 = 10+12 = 22.
q4 = 220 = 20+12 = 02.
q5 = 020 = 20.
q6 = 200 = 00 + 12 = 12.
q7 = 120 = 20 + 21 = 11.
q8 = 110 = 10 + 21 = 01.
Сега ще попълним таблиците за показателите и логаритмите:
Таблици на степените и логаритмите_5TblPowLg
И най-накрая таблицата за умножение.
За да намерим AB първо намираме lg(AB) = lg(A)+lg(B) и след това намираме AB като повдигнем q на намерения логаритъм.
Събирането на логаритмите се извършва по модул 8 - редът на групата.
Например A=02, B=12, lg(AB) = 4 + 6 = 10 ≡ 2 ( mod 8 ) . AB = q2 = 21.
И така за всяко A и всяко B общо 64 пъти.
Всъщност на половина ( горе-долу ), защото това произведение е разместително.
Разбира се, произведенията могат да се изпълняват и директно.
Таблица на умножението_5TblMult
Какво ще научим?