Véges mező - Finite field

A matematikában a véges mező vagy a Galois mező (úgynevezett Évariste Galois tiszteletére ) olyan mező , amely véges számú elemet tartalmaz . Mint minden mező esetében, a véges mező olyan halmaz , amelyen a szorzás, összeadás, kivonás és osztás műveletei meghatározottak, és megfelelnek bizonyos alapvető szabályoknak. A leggyakoribb példa a véges mező által megadott egész szám mod p , ha p egy prímszám .

A véges mezők alapvetőek a matematika és az informatika számos területén , beleértve a számelméletet , az algebrai geometriát , a Galois -elméletet , a véges geometriát , a kriptográfiát és a kódolási elméletet .

Tulajdonságok

A véges mező egy véges halmaz, amely egy mező ; ez azt jelenti, hogy a szorzás, összeadás, kivonás és osztás (a nullával való osztás kivételével) meg van határozva, és megfelelnek a mező axiómáknak nevezett számtani szabályoknak .

A véges mező elemeinek számát annak sorrendjének vagy néha méretének nevezzük . Véges mező érdekében q fennáll, ha, és csak akkor, ha q jelentése prımhatvány p ^k (ahol p egy prímszám, és k egy pozitív egész szám). A p ^k sorrendben bármely elem p másolatának hozzáadása mindig nullát eredményez; vagyis a jellemző a mező p .

Ha q = p ^k , minden területén annak érdekében, q jelentése izomorf (lásd § létezése és egyedisége alább). Ezenkívül egy mező nem tartalmazhat két különböző véges részmezőt azonos sorrendben. Lehet tehát azonosítani minden véges mezőket ugyanabban a sorrendben, és ezek egyértelműen jelöljük , F _q vagy GF ( q ) , ahol a betűk gf állni „Galois mező”. ${\ displaystyle \ mathbb {F} _ {q}}$

A véges mező érdekében q , a polinom X ^q - X az összes q elemei a véges mezőben, mint gyökerek . Egy véges mező nullától eltérő elemei multiplikatív csoportot alkotnak . Ez a csoport ciklikus , így minden nullától eltérő elem egyetlen elem hatványaként fejezhető ki, amelyet a mező primitív elemének neveznek . (Általában egy adott mezőhöz több primitív elem tartozik.)

A legegyszerűbb példa a véges mezők a mezők elsődleges érdekében: minden prímszám p , a elsődleges területén rend p , , lehet kialakítani, mint az egész számok modulo p , Z / o Z . ${\ displaystyle \ mathbb {F} _ {p}}$

A p sorrend elsődleges mezőjének elemeit a 0, ..., p - 1 tartományban lévő egész számok képviselhetik . Az összeg, a különbség, és a terméket a fennmaradó részlege által p az az eredménye, a megfelelő egész műveletet. Egy elem multiplikatív inverze kiszámítható a kiterjesztett euklideszi algoritmus használatával (lásd: Kiterjesztett euklideszi algoritmus § Moduláris egész számok ).

Legyen F véges mező. Bármely elem x a F és bármely egész szám n , Jelöljük n ⋅ x összege n példányban x . A legkevésbé pozitív n olyan, hogy n ⋅ 1 = 0 a mező p jellemzője . Ez lehetővé teszi, hogy meghatározzák egy szorzást egy elem k a GF ( p ) olyan elem révén X a F választásával egy egész szám képviselőjéhez k . A szorzás teszi F egy GF ( p ) - vektortér . Ebből következik, hogy az elemek számát a F jelentése p ⁿ néhány egész szám n . ${\ displaystyle (k, x) \ mapsto k \ cdot x}$

Az identitás

${\ displaystyle (x+y)^{p} = x^{p}+y^{p}}$

(néha a gólya álmának is nevezik ) a jellemző p . Ez a binomiális tételből következik , mivel az ( x + y ) ^p expanziójának minden binomiális együtthatója , az első és az utolsó kivételével, p többszöröse .

By Kis Fermat-tétel , ha p prímszám, és x jelentése terén GF ( p ) , majd x ^p = x . Ez magában foglalja az egyenlőséget

${\ displaystyle X^{p} -X = \ prod _ {a \ in {\ rm {GF}} (p)} (Xa)}$

GF ( p ) feletti polinomokra . Általánosságban elmondható, hogy a GF ( p ⁿ ) minden eleme kielégíti az x ^{p n} - x = 0 polinom egyenletet .

A véges mező bármely véges mező kiterjesztése elválasztható és egyszerű. Azaz, ha E véges mező, F pedig E részmezője , akkor E -t F -ből úgy kapjuk meg, hogy egyetlen elemet kapcsolunk össze, amelynek minimális polinomja elválasztható. A zsargon használatához a véges mezők tökéletesek .

Egy általánosabb algebrai struktúra, amely kielégíti az összes többi axiómák egy mező, de amelynek a szorzás nem szükséges, hogy legyen kommutatív, nevezzük ferdetest (vagy néha ferde területen ). By wedderburn-tétel , bármely véges ferdetest kommutatív, és így egy véges test.

Létezés és egyediség

Legyen q = p ⁿ egy prímhatvány , és F az felosztása területén a polinom

${\ displaystyle P = X^{q} -X}$

a GF ( p ) prímmező felett . Ez azt jelenti, hogy az F jelentése véges mező legalacsonyabb rendű, amelyben P van q különálló gyökerei (a formális-származék a P jelentése P ' = -1 , utalva arra, hogy a GCD ( P , P ' ) = 1 , ami általában azt jelenti, hogy a felosztómező az eredeti leválasztható kiterjesztése ). A fenti azonosság azt mutatja, hogy az összeg, és a terméket két gyökerei P gyöke P , valamint a reciprok egy gyökere P . Más szóval, a P gyökei q sorrendű mezőt alkotnak , amely a felosztási mező minimálisával egyenlő F -vel .

A felosztó mezők egyedisége az izomorfizmusig azt jelenti, hogy a q sorrend összes mezője izomorf. Továbbá, ha egy F mező részmezőjének q = p ^k rendű mezője van , akkor annak elemei az X ^q - X q gyökei , és F nem tartalmazhat egy másik q sorrend részmezőt .

Összefoglalva, a következő osztályozási tétel áll rendelkezésünkre, amelyet először 1893 -ban bizonyított EH Moore :

A véges mező sorrendje elsődleges hatalom. Minden q elsődleges hatalomra vannak q rendű mezők , és mindegyik izomorf. Ezeken a területeken minden elem kielégíti

${\ displaystyle x^{q} = x,}$

és az X ^q polinom - X faktorok as

${\ displaystyle X^{q} -X = \ prod _ {a \ in F} (Xa).}$

Ebből következik, hogy a GF ( p ⁿ ) csak akkor és csak akkor tartalmaz GF ( p ^m ) izomorf almezőt, ha m osztója n -nek ; ebben az esetben ez az almező egyedi. Valójában az X ^{p m} - X polinom akkor és csak akkor osztja X ^{p n} - X -et, ha m osztója n -nek .

Kifejezett konstrukció

Nem elsődleges mezők

Ha egy q = p ⁿ prímteljesítményt ^{adunk meg,} és p > és n > 1 , akkor a GF ( q ) mező kifejezetten a következő módon szerkeszthető. Az egyik első kiválaszt egy irreducibilis polinom P a GF ( p ) [ X ] fokú N (mint redukálhatatlan polinom mindig fennáll). Aztán a hányadosgyűrű

${\ displaystyle {\ rm {GF}} (q) = {\ rm {GF}} (p) [X]/(P)}$

A GF ( p ) [ X ] polinomgyűrűnek a P által generált ideál egy q sorrendű mezője .

Kifejezettebben a GF ( q ) elemei azok a GF ( p ) feletti polinomok, amelyek foka szigorúan kisebb, mint n . Az összeadás és a kivonás a GF ( p ) feletti polinomoké . A termék a két elem a fennmaradó euklideszi részlege által P a termék GF ( p ) [ X ] . A nem nulla elem multiplikatív inverze kiszámítható a kiterjesztett euklideszi algoritmussal; lásd: Kiterjesztett euklideszi algoritmus § Egyszerű algebrai mező kiterjesztések .

A GF (4) konstrukcióját leszámítva számos lehetséges opció létezik a P számára , amelyek izomorf eredményeket produkálnak. Az euklideszi felosztás egyszerűsítése érdekében P esetében általában az alak polinomjait választjuk

${\ displaystyle X^{n}+aX+b,}$

amelyek a szükséges euklideszi hadosztályokat nagyon hatékonysá teszik. Egyes mezők esetében azonban, jellemzően a 2. karakterisztikában , nem létezhetnek X ⁿ + aX + b alakú, redukálhatatlan polinomok . A 2. karakterisztikában , ha az X ⁿ + X + 1 polinom redukálható, ajánlatos az X ⁿ + X ^k + 1 -et választani a lehető legkisebb k -val , ami redukálhatatlanná teszi a polinomot. Ha mindezen trinomials visszavezethetõk, az egyik dönt „pentanomials” X ⁿ + X ^egy + X ^b + X ^c + 1 , mint polinomok mértéke nagyobb, mint 1 , a páros számú kifejezések, soha nem irreduk- jellemző 2 , amelynek 1 mint gyökér.

Egy lehetséges polinomot a Conway polinomok adnak meg . Bizonyos kompatibilitást biztosítanak egy mező reprezentációja és az almezők ábrázolása között.

A következő szakaszokban megmutatjuk, hogyan működik a fent vázolt általános építési módszer kis véges mezők esetében.

Mező négy elemmel

A legkisebb nem elsődleges mező területén négy elemmel, amely általánosan jelöli GF (4) , illetve áll a négy elem , hogy és minden egyéb művelet eredménye, hogy könnyen levezethető az elosztó törvény . Lásd alább a teljes műveleti táblázatokat. ${\ displaystyle \ mathbb {F} _ {4}.}$${\ displaystyle 0,1, \ alpha, 1+\ alpha}$${\ displaystyle \ alpha ^{2} = 1+\ alpha,}$ ${\ displaystyle 1 \ cdot \ alpha = \ alpha \ cdot 1 = \ alpha,}$ ${\ displaystyle x+x = 0,}$${\ displaystyle x \ cdot 0 = 0 \ cdot x = 0,}$${\ displaystyle x \ in \ operatorname {GF} (4),}$

Ez az előző szakasz eredményeiből a következőkre vezethető le.

Több, mint GF (2) , csak egy irreducibilis polinom foka2 :

${\ displaystyle X^{2}+X+1}$

Ezért a GF (4) esetében az előző szakasz felépítésének tartalmaznia kell ezt a polinomot, és

${\ displaystyle {\ rm {GF}} (4) = {\ rm {GF}} (2) [X]/(X^{2}+X+1).}$

Jelölje α ennek a polinomnak a gyökét a GF -ben (4) . Ez arra utal

α ² = 1 + α ,

és hogy α és 1 + α a GF (4) azon elemei , amelyek nincsenek a GF -ben (2) . A GF (4) műveleteinek táblái ebből származnak, és a következők:

Összeadás x + y	Szorzás x ⋅ y	X / y körzet
x ╲ y 0 1 α 1 + α 0 0 1 α 1 + α 1 1 0 1 + α α α α 1 + α 0 1 1 + α 1 + α α 1 0	x ╲ y 0 1 α 1 + α 0 0 0 0 0 1 0 1 α 1 + α α 0 α 1 + α 1 1 + α 0 1 + α 1 α	x ╲ y 1 α 1 + α 0 0 0 0 1 1 1 + α α α α 1 1 + α 1 + α 1 + α α 1

A táblázat a kivonás nem adott, mert a kivonás azonos túlmenően, mint ez a helyzet minden területén jellemző 2. A harmadik táblázatban, a részlege x által y , az értékek x kell olvasni a bal oldali oszlopban , és y értékei a felső sorban. (Mivel a 0 ⋅ Z = 0 minden z minden gyűrű a osztás 0 állapotban keli maradnia definiálatlan.)

A térkép

${\ displaystyle \ varphi: x \ mapsto x^{2}}$

a nem triviális mezőautomorfizmus, az úgynevezett Frobenius-automorfizmus , amely α- t küld a fent említett irreducibilis polinom második gyökébe 1 + α${\ displaystyle X^{2}+X+1.}$

GF ( p ² ) páratlan prímszámra p

A véges mezők fenti általános konstrukciójának alkalmazásához a GF ( p ² ) esetében meg kell találni egy 2 -es fokú irreducibilis polinomot. A p = 2 esetében ezt az előző részben tettük meg. Ha p páratlan prímszám, mindig vannak irreducibilis polinomok az űrlap X ² - r , és r a GF ( p ) .

Pontosabban, a polinom X ² - r irreducibilis fölött GF ( p ) akkor és csak akkor, ha R egy kvadratikus nemmaradékot modulo p (ez szinte az meghatározása egy kvadratikus nemmaradékot). Vannak p - 1/2másodfokú nem maradékok modulo p . Például 2 2 másodfokú nem-maradék p = 3, 5, 11, 13, ... , és 3 másodfokú nem-maradék p = 5, 7, 17, ... esetén . Ha p ≡ 3 mod 4 , azaz p = 3, 7, 11, 19, ... , akkor az −1 ≡ p- 1 értéket választhatjuk másodfokú nem-maradékként, ami lehetővé teszi számunkra, hogy legyen egy nagyon egyszerű redukálhatatlan polinomunk X ² + 1 .

Miután kiválasztott egy kvadratikus nemmaradékot R , legyen α lehet szimbolikus négyzetgyöke r , hogy egy szimbólum, amely az a tulajdonsága, α ² = r , ugyanúgy, mint a komplex szám i szimbolikus négyzetgyöke -1 . Ekkor a GF elemei ( p ² ) az összes lineáris kifejezés

${\ displaystyle a+b \ alpha,}$

a a és b a GF ( p ) . A GF -en végzett műveletek ( p ² ) a következők szerint vannak definiálva (a GF ( p ) latin betűkkel jelölt elemei közötti műveletek a GF ( p ) műveletei ):

${\ displaystyle {\ begin {aligned}-(a+b \ alpha) & =-a+(-b) \ alpha \\ (a+b \ alpha)+(c+d \ alpha) & = (a+c )+(b+d) \ alfa \\ (a+b \ alfa) (c+d \ alfa) & = (ac+rbd)+(ad+bc) \ alfa \\ (a+b \ alfa)^ {-1} & = a (a^{2} -rb^{2})^{-1}+(-b) (a^{2} -rb^{2})^{-1} \ alpha \ end {igazítva}}}$

GF (8) és GF (27)

A polinom

${\ displaystyle X^{3} -X-1}$

redukálhatatlan a GF (2) és a GF (3) felett , azaz redukálhatatlan 2. és 3. modul (ennek bemutatásához elegendő annak bemutatása, hogy nincs gyökere a GF (2) és a GF (3) -ban ). Ebből következik, hogy a GF (8) és a GF (27) elemeit kifejezések képviselhetik

${\ displaystyle a +b \ alpha +c \ alpha ^{2},}$

ahol a , b , c a GF (2) vagy a GF (3) (illetve) elemei , és olyan szimbólum, amely ${\ displaystyle \ alpha}$

${\ displaystyle \ alpha ^{3} = \ alpha +1.}$

A GF (8) és a GF (27) addíciója, additív inverze és szorzata így a következőképpen határozható meg; a következő képletek, a műveletek között elemei GF (2) vagy GF (3) , képviseli latin betűkkel, a műveletek GF (2) vagy GF (3) , illetve:

${\ displaystyle {\ begin {aligned}-(a +b \ alpha +c \ alpha ^{2}) & =-a +(-b) \ alpha +(-c) \ alpha ^{2} \ qquad {\ text {(for}} \ mathrm {GF} (8), {\ text {ez a művelet az identitás)}} \\ (a+b \ alpha+c \ alpha ^{2})+(d+e \ alfa+f \ alfa ^{2}) & = (a+d)+(b+e) \ alfa+(c+f) \ alfa ^{2} \\ (a+b \ alfa+c \ alfa ^ {2}) (d+e \ alpha+f \ alpha ^{2}) & = (ad+bf+ce)+(ae+bd+bf+ce+cf) \ alpha+(af+be+cd+ cf) \ alpha ^{2} \ end {igazított}}}$

GF (16)

A polinom

${\ displaystyle X^{4}+X+1}$

redukálhatatlan a GF (2) felett , azaz redukálhatatlan modulo 2 . Ebből következik, hogy a GF (16) elemeit kifejezések képviselhetik

${\ displaystyle a+b \ alpha+c \ alpha ^{2}+d \ alpha ^{3},}$

ahol a , b , c , d vagy 0 vagy 1 (a GF (2) elemei ), és α olyan szimbólum, amely

${\ displaystyle \ alpha ^{4} = \ alpha +1}$

(vagyis α az adott irreducibilis polinom gyökere). Mivel a GF (2) jellemzője 2 , minden elem az additív inverze a GF (16) -ban . Az összeadás és a szorzás a GF (16) -on a következőképpen határozható meg; a következő képletekben a GF (2) elemei közötti , latin betűkkel ábrázolt műveletek a GF (2) műveletei .

${\ displaystyle {\ begin {aligned} (a+b \ alpha+c \ alpha ^{2}+d \ alpha ^{3})+(e+f \ alpha+g \ alpha ^{2}+h \ alfa ^{3}) & = (a+e)+(b+f) \ alfa+(c+g) \ alfa ^{2}+(d+h) \ alfa ^{3} \\ (a+ b \ alfa+c \ alfa ^{2}+d \ alfa ^{3}) (e+f \ alfa+g \ alfa ^{2}+h \ alfa ^{3}) & = (ae+bh+ cg+df)+(af+be+bh+cg+df+ch+dg) \ alfa \;+\\ & \ quad \; (ag+bf+ce+ch+dg+dh) \ alfa ^{2 }+(ah+bg+cf+de+dh) \ alpha ^{3} \ end {igazítva}}}$

Multiplikatív szerkezet

A készlet nem nulla elemek GF ( q ) egy Abel-csoport alatt a szorzást, a rend q - 1 . A Lagrange-tétel , létezik egy osztóját k a q - 1 úgy, hogy x ^k = 1 minden nem nulla X a GF ( q ) . Mivel az x ^k = 1 egyenlet legfeljebb k megoldást tartalmaz bármely mezőben, q - 1 a k legalacsonyabb lehetséges értéke . A véges abeli csoportok szerkezeti tétele azt sugallja, hogy ez a multiplikatív csoport ciklikus , vagyis minden nem nulla elem egyetlen elem hatalma. Összefoglalva:

A multiplikatív csoportja a nem nulla elemek GF ( q ) ciklikus, és létezik egy elem egy , oly módon, hogy a q - 1 nemnulla elemeinek GF ( q ) van egy , a ² , ..., a ^{q −2} , a ^{q −1} = 1 .

Egy ilyen elemet egy nevezzük primitív elem . Hacsak q = 2, 3 , a primitív elem nem egyedi. A nagyszámú primitív elemek φ ( q - 1) , ahol φ jelentése Euler-függvény .

A fenti eredmény azt sugallja, hogy x ^q = x minden x -re GF ( q ) -ben . Az a konkrét eset, amikor q prím, Fermat kis tétele .

Diszkrét logaritmus

Ha egy egy primitív eleme GF ( q ) , majd minden nem nulla elemet x a F , van egy egyedi egész szám n a 0 ≤ n ≤ q - 2 olyan, hogy

x = a ⁿ .

Ezt egész szám n nevezik diszkrét logaritmus az x , hogy a bázis egy .

Míg az ⁿ -t nagyon gyorsan ki lehet számítani, például négyzetes kitevéssel , nincs ismert hatékony algoritmus az inverz művelet, a diszkrét logaritmus kiszámításához. Ezt különböző kriptográfiai protokollokban használták, részletekért lásd: Diszkrét logaritmus .

Ha a GF ( q ) nem nulla elemeit diszkrét logaritmusuk képviseli, a szorzás és osztás egyszerű, mivel összeadásra és kivonásra redukálják a modulo q - 1 értéket . Az összeadás azonban az ^m + a ⁿ diszkrét logaritmusának kiszámítását jelenti . Az identitás

a ^m + a ⁿ = a ⁿ ( a ^{m - n} + 1)

lehetővé teszi a probléma megoldását azáltal, hogy felépítjük egy ⁿ + 1 diszkrét logaritmusainak táblázatát , amelyet Zech -féle logaritmusoknak nevezünk , n = 0, ..., q - 2 esetén (célszerű a nulla diszkrét logaritmusát úgy definiálni, hogy - ∞ ).

A Zech-féle logaritmusok hasznosak nagy számításokhoz, például lineáris algebrához közepes méretű mezőkön, azaz olyan mezőkhöz, amelyek elég nagyok ahhoz, hogy a természetes algoritmusok hatástalanok legyenek, de nem túl nagyok, mivel előzetesen ki kell számítani egy azonos méretű táblát. mint a mező rendje.

Az egység gyökerei

Egy véges mező minden nulla eleme az egység gyökere , mivel x ^{q −1} = 1 a GF ( q ) minden nulla elemére .

Ha n jelentése pozitív egész szám, egy n- edik primitív gyök az egység egy egyenlet megoldása x ⁿ = 1 , amely nem megoldása az egyenletnek X ^m = 1 minden pozitív egész m < n . Ha a az egység n -edik primitív gyökere az F mezőben , akkor F tartalmazza az egység összes n gyökét, amelyek 1, a , a ² , ..., a ^{n −1} .

A GF ( q ) mező akkor és csak akkor tartalmazza az egység n primitív gyökét, ha n osztója q - 1 ; ha n egy osztója q - 1 , akkor a száma primitív n edik egységgyök a GF ( q ) van φ ( n ) ( Euler-függvény ). A száma n edik egységgyök a GF ( q ) van GCD ( n , q - 1) .

Az olyan területen jellemző p , minden ( np ) th gyökere egység is egy n edik gyökere egységét. Ebből következik, hogy az egység primitív ( np ) gyökerei soha nem léteznek a jellemző p .

Másrészt, ha n jelentése relatív prím , hogy p , a gyökerek a N edik körosztási polinom különböznek minden területén jellemző p , mivel ez polinom osztója X ⁿ - 1 , amelynek diszkrimináns nem nulla modulo p . Ebből következik, hogy a n edik körosztási polinom tényezők fölött GF ( p ) a különböző irreducibilis polinomok, hogy az összes ugyanolyan mértékben, mondjuk d , és hogy a GF ( p ^d ) a legkisebb területén jellemző p , amely tartalmazza a n edik primitív gyökerei egység. ${\ displaystyle n^{n}}$

Példa: GF (64)

A GF (64) mező számos érdekes tulajdonsággal rendelkezik, amelyeket a kisebb mezők nem osztanak meg: két olyan almezője van, amelyek egyikét sem tartalmazza a másik; nem minden generátor ( a GF (2) feletti minimális 6. fokú polinommal rendelkező elemek) primitív elemek; és a primitív elemek nem mind konjugáltak a Galois -csoport alatt .

Az, hogy a ezen a területen, hogy 2 ⁶ , és osztói 6 hogy 1, 2, 3, 6 , az almezők GF (64) vannak GF (2) , GF (2 ² ) = GF (4) , GF (2 ³ ) = GF (8) , és maga GF (64) . Mivel 2 és 3 a relatív prím , a kereszteződésekben a GF (4) és a GF (8) a GF (64) az elsődleges mező GF (2) .

A GF (4) és a GF (8) egyesítése tehát 10 elemből áll. A GF (64) fennmaradó 54 eleme generálja a GF (64) -t abban az értelemben, hogy egyetlen almező sem tartalmazza azokat. Ebből következik, hogy a 6. fokozatú redukálhatatlan polinomok gyökerei a GF felett (2) . Ez azt jelenti, hogy a GF (2) felett pontosan 9 =54/66. fokú redukálhatatlan monikus polinomok . Ezt ellenőrizheti az X ⁶⁴ - X faktorozásával a GF -en keresztül (2) .

A GF (64) elemei az egység primitív n -edik gyökerei néhány n osztó 63 esetében . Mivel az egység 3. és 7. gyökere a GF (4), illetve a GF (8) , az 54 generátor az egység primitív n -edik gyökere néhány n számára a {9, 21, 63} -ban . Euler totiens függvénye azt mutatja, hogy az egységnek 6 primitív 9. gyökere, 12 primitív 21. egységgyöke és 36 primitív 63. egységgyöke van. Ezeket a számokat összegezve ismét 54 elemet találunk .

A ciklotómiai polinomokat GF (2) fölé faktorálva megállapítható, hogy:

• Az egység hat primitív 9. gyökere a gyökere

${\ displaystyle X^{6}+X^{3} +1,}$

és mind a Galois csoport hatására konjugálódnak.

• Az egység tizenkét primitív 21. gyökere

${\ displaystyle (X^{6}+X^{4}+X^{2}+X+1) (X^{6}+X^{5}+X^{4}+X^{2} +1).}$

A Galois -csoport hatására két pályát alkotnak. Mivel a két tényező kölcsönös egymással, a gyök és annak (multiplikatív) inverze nem ugyanahhoz a pályához tartozik.

• A GF (64) 36 primitív eleme a gyökere

${\ displaystyle (X^{6}+X^{4}+X^{3}+X+1) (X^{6}+X+1) (X^{6}+X^{5}+ 1) (X^{6}+X^{5}+X^{3}+X^{2} +1) (X^{6}+X^{5}+X^{2}+X+ 1) (X^{6}+X^{5}+X^{4}+X+1),}$

A Galois csoport hatására hat elemből álló 6 pályára oszlanak.

Ez azt mutatja, hogy a legjobb választás a GF (64) megalkotásához az, ha GF (2) [ X ] / ( X ⁶ + X + 1) -ként definiáljuk . Valójában ez a generátor primitív elem, és ez a polinom az a redukálhatatlan polinom, amely a legegyszerűbb euklideszi osztást eredményezi.

Frobenius automorfizmus és Galois elmélet

Ebben a szakaszban p prímszám, q = p ⁿ pedig p hatványa .

A GF ( q ) -ben az ( x + y ) ^p = x ^p + y ^p azonosság azt jelenti, hogy a térkép

${\ displaystyle \ varphi: x \ mapsto x^{p}}$

egy GF ( p ) - lineáris endomorphism és egy mezőt automor a GF ( q ) , amely rögzíti minden elemét az almező GF ( p ) . Ferdinand Georg Frobenius után Frobenius automorfizmusnak hívják .

Jelölő által φ ^k a készítmény a φ önmagával k -szor, van

${\ displaystyle \ varphi^{k}: x \ mapsto x^{p^{k}}.}$

Az előző részben bemutattuk, hogy φ ⁿ az azonosság. A 0 < k < n , automorfizmus φ ^k nem azonosságát, mivel egyébként a polinom

${\ displaystyle X^{p^{k}}-X}$

több lenne, mint p ^k gyökere.

A GF ( q ) -nak nincs más GF ( p ) -automorfizmusa . Más szavakkal, GF ( p ⁿ ) pontosan n GF ( p ) -automorphisms, amelyek

${\ displaystyle \ mathrm {Id} = \ varphi ^{0}, \ varphi, \ varphi ^{2}, \ ldots, \ varphi ^{n-1}.}$

Ami a Galois-elmélet , ez azt jelenti, hogy a GF ( p ⁿ ) egy Galois kiterjesztése a GF ( p ) , amely egy ciklikus Galois-csoport.

Az a tény, hogy a Frobenius -térkép szujektív, azt sugallja, hogy minden véges mező tökéletes .

Polinomiális faktorizáció

Ha F véges mező, akkor az F-ben szereplő együtthatójú, nem konstans monikus polinom nem redukálható F fölött , ha nem két nem konstans monikus polinom szorzata, együtthatói F-ben .

Mivel egy mező feletti minden polinomgyűrű egyedi faktorizációs tartomány , minden véges mező feletti monon polinom egyedi módon (a tényezők sorrendjéig) redukálhatatlan monikus polinomok szorzatává alakítható.

Vannak hatékony algoritmusok a polinomi redukálhatatlanság tesztelésére és a polinomok véges mezőn történő faktorálására. Ezek kulcsfontosságú lépést jelentenek a polinomok egész számok vagy racionális számok figyelembevételével . Legalábbis emiatt minden számítógépes algebrai rendszer rendelkezik olyan funkciókkal, amelyek a polinomokat véges mezőkön vagy legalább véges prímmezőkön keresztül faktorálják.

Egy adott fokú redukálhatatlan polinomok

A polinom

${\ displaystyle X^{q} -X}$

tényezőket lineáris tényezőkké sorrendben q . Pontosabban, ez a polinom az első fokú monikus polinomok szorzata q rendű mező felett .

Ez azt jelenti, hogy ha q = p ^n, akkor X ^q - X a GF ( p ) feletti összes monikussal redukálhatatlan polinom szorzata , amelynek foka osztja az n -t . Valójában, ha P egy redukálhatatlan tényező az X ^q - X GF ( p ) fölött , akkor annak mértéke osztja az n -t, mivel felosztási mezőjét a GF ( p ⁿ ) tartalmazza . Ezzel szemben, ha P egy irreducibilis monic polinom több mint GF ( p ) fokú d elosztják n , ez határozza meg a mező kiterjesztésének fokú d , amely megtalálható a GF ( p ⁿ ) , és az összes gyökerei P tartoznak GF ( p ⁿ ) , és X ^q - X gyökerei ; így P osztja X ^q - X -et . Mivel X ^q - X nem rendelkezik többszörös tényezővel, így az összes redukálhatatlan monikus polinom szorzata, amely osztja.

Ez a tulajdonság a GF ( p ) feletti polinomok minden fokának redukálhatatlan tényezőinek szorzatának kiszámítására szolgál ; lásd: Különböző fokú faktorizálás .

Egy adott fokú monikus redukálhatatlan polinomok száma egy véges mezőn

A GF ( q ) feletti n fokú monikus redukálhatatlan polinomok N ( q , n ) számát a

${\ displaystyle N (q, n) = {\ frac {1} {n}} \ sum _ {d \ mid n} \ mu (d) q^{n/d},}$

ahol μ a Möbius -függvény . Ez a képlet szinte közvetlen következménye X ^q - X fenti tulajdonságának .

A fenti képletben az száma nem csökkenthető (nem feltétlenül monic) polinomokként n feletti GF ( q ) van ( q - 1) N ( q , n ) .

A (kissé egyszerűbb) alsó határa N ( q , n ) az

${\ displaystyle N (q, n) \ geq {\ frac {1} {n}} \ left (q^{n}-\ sum _ {p \ mid n, \ p {\ text {prime}}} q ^{n/p} \ ugye).}$

Egy könnyen következtetni, hogy, minden q , és minden n , van legalább egy irreducibilis polinom foka n feletti GF ( q ) . Ez az alsó határ éles, ha q = n = 2 .

Alkalmazások

A kriptográfiában a diszkrét logaritmusfeladat nehézsége véges mezőkben vagy elliptikus görbékben számos széles körben használt protokoll, például a Diffie – Hellman protokoll alapja . Például 2014 -ben egy biztonságos internetkapcsolat a Wikipédiához magában foglalta a Diffie – Hellman protokoll ( ECDHE ) elliptikus görbéjét egy nagy véges területen. A kódelméleti sok kódok vannak kialakítva altereinek a vektorterekben véges testek felett.

A véges mezőket számos hibajavító kód használja , például Reed – Solomon hibajavító kód vagy BCH -kód . A véges mező szinte mindig 2 -es jellemzővel rendelkezik, mivel a számítógépes adatok bináris formában vannak tárolva. Például egy adat bájt értelmezhető elemként . Az egyik kivétel a PDF417 vonalkód, amely . Egyes CPU-k speciális utasításokkal rendelkeznek, amelyek hasznosak lehetnek a 2. jellemző véges mezőiben, általában a hordozható termék változataiban . ${\ displaystyle GF (2^{8})}$${\ displaystyle GF (929)}$

Véges testek széles körben használják a számelmélet , ugyanis számos probléma az egész megoldható csökkentésével őket modulo egy vagy több prímszám . Például a leggyorsabban ismert algoritmusok a polinomiális faktorizációra és a lineáris algebrára a racionális számok mezején keresztül egy vagy több prímszámú redukcióval, majd a megoldás rekonstrukciójával kínai maradék tétel , Hensel -emelés vagy az LLL algoritmus használatával jönnek létre .

Hasonlóképpen a számelmélet számos elméleti problémája megoldható, ha figyelembe vesszük a redukcióikat néhány vagy az összes prímszámmal. Lásd például a Hasse -elvet . Az algebrai geometria számos közelmúltbeli fejlesztését az motiválta, hogy növelni kell e moduláris módszerek erejét. Wiles bizonyítéka Fermat utolsó tételére egy példa a mély eredményre, amely számos matematikai eszközt tartalmaz, beleértve a véges mezőket is.

A Weil -sejtések a véges mezők feletti algebrai változatok pontjaira vonatkoznak, és az elméletnek számos alkalmazása van, beleértve az exponenciális és karakterösszeg -becsléseket.

A véges mezők széles körben alkalmazhatók a kombinatorikában , két jól ismert példa a Paley Graphs definíciója és a Hadamard Matrices kapcsolódó konstrukciója . Az aritmetikai kombinatorikában a véges mezőket és a véges mező modelleket széles körben használják, például Szemerédi számtani progresszióról szóló tételében .

Bővítmények

Algebrai zárás

Egy F véges mező nem algebrai szempontból zárt: a polinom

${\ displaystyle f (T) = 1+\ prod _ {\ alfa \ in F} (T- \ alfa),}$

nincs gyökere az F -ben , mivel f  ( α ) = 1 az összes α esetében F -ben .

Fix egy algebrai lezárása a . A térkép küldő egyes x , hogy x ^q az úgynevezett Q edik hatványa Frobenius automor . A mezőrészével által meghatározott n- edik hajtogat a halmaza nullákat a polinom x ^{q n} - X , amelyek elkülönülő gyökerei óta származék jelentése -1 , ami soha nem nulla. Ezért ez az almező q ⁿ elemet tartalmaz, tehát az in egyedi példánya . Az in minden véges kiterjesztése ez néhány n esetében , tehát ${\ displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ displaystyle \ mathbb {F} _ {q}}$${\ displaystyle \ varphi _ {q} \ kettőspont {\ overline {\ mathbb {F}}} _ {q} \ to {\ overline {\ mathbb {F}}} _ {q}}$${\ displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ displaystyle \ varphi _ {q}}$${\ displaystyle \ mathbb {F} _ {q} [x]}$${\ displaystyle \ mathbb {F} _ {q^{n}}}$${\ displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ displaystyle \ mathbb {F} _ {q}}$${\ displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ displaystyle \ mathbb {F} _ {q^{n}}}$

${\ displaystyle {\ overline {\ mathbb {F}}} _ {q} = \ bigcup _ {n \ geq 1} \ mathbb {F} _ {q^{n}}.}$

A abszolút Galois csoportja az a profinite csoport${\ displaystyle \ mathbb {F} _ {q}}$

${\ displaystyle \ operatornév {Gal} ({\ overline {\ mathbb {F}}} _ {q}/\ mathbb {F} _ {q}) \ simeq \ varprojlim _ {n} \ operatorname {Gal} ({ \ overline {\ mathbb {F}}} _ {q^{n}} /\ mathbb {F} _ {q}) \ simeq \ varprojlim _ {n} (\ mathbf {Z} /n \ mathbf {Z} ) = {\ widehat {\ mathbf {Z}}}.}$

Mint minden végtelen Galois -csoport, fel lehet szerelve a Krull topológiával , majd az imént megadott izomorfizmusok a topológiai csoportok izomorfizmusai . A kép a csoportban az 1 generátor , tehát megfelel . Ebből következik, hogy végtelen rendű, és nem az egész csoportból, hanem egy sűrű alcsoportot generál , mivel az elem végtelen rendű, és létrehozza az Egy sűrű alcsoportot, amely azt mondja, hogy a topológiai generátora . ${\ displaystyle \ operatornév {Gal} ({\ overline {\ mathbb {F}}} _ {q}/\ mathbb {F} _ {q})}$${\ displaystyle \ varphi _ {q}}$${\ displaystyle \ operatornév {Gal} ({\ overline {\ mathbb {F}}} _ {q^{n}} /\ mathbb {F} _ {q}) \ simeq \ mathbf {Z} /n \ mathbf {Z}}$${\ displaystyle \ varphi _ {q}}$${\ displaystyle 1 \ in {\ widehat {\ mathbf {Z}}}}$${\ displaystyle \ varphi _ {q}}$${\ displaystyle \ operatornév {Gal} ({\ overline {\ mathbb {F}}} _ {q}/\ mathbb {F} _ {q})}$${\ displaystyle 1 \ in {\ widehat {\ mathbf {Z}}}}$${\ displaystyle \ mathbf {Z} \ subsetneqq {\ widehat {\ mathbf {Z}}}.}$${\ displaystyle \ varphi _ {q}}$${\ displaystyle \ operatornév {Gal} ({\ overline {\ mathbb {F}}} _ {q}/\ mathbb {F} _ {q})}$

Kvázi algebrai zárás

Bár a véges mezők algebrai szempontból nem zártak, kvázi algebrai szempontból zártak , ami azt jelenti, hogy minden véges mező feletti homogén polinomnak van egy nem triviális nullája, amelynek összetevői abban a mezőben vannak, ha változóinak száma nagyobb, mint a mértéke. Ez Artin és Dickson sejtése volt, amelyet Chevalley bizonyított (lásd Chevalley – Warning tétel ).

Wedderburn kis tétele

A ferdetest általánosítása mező. Az osztógyűrűket nem feltételezzük kommutatívnak. Nincsenek nem kommutatív véges ferdetest: wedderburn-tétel kimondja, hogy minden véges ferdetest vannak kommutatív, ezért véges területen. Az eredmény akkor is érvényes, ha lazítjuk az asszociativitást, és figyelembe vesszük az alternatív gyűrűket , az Artin – Zorn -tétel szerint .

Lásd még

• Kvázi véges mező
• Mező egy elemmel
• Véges mező aritmetika
• Véges gyűrű
• Véges csoport
• Elemi abeli csoport
• Hamming tér

Megjegyzések

Hivatkozások

Külső linkek

• Véges mezők a Wolfram kutatásában.