Konečné pole - Finite field

V matematice je konečné pole nebo Galoisovo pole (takzvané na počest Évariste Galoise ) pole, které obsahuje konečný počet prvků . Jako u každého pole je konečné pole množina, na které jsou definovány operace násobení, sčítání, odčítání a dělení a splňují určitá základní pravidla. Nejběžnější příklady konečných polí jsou dána celými čísly mod p, když p je prvočíslo .

Konečná pole jsou zásadní v řadě oblastí matematiky a informatiky , včetně teorie čísel , algebraické geometrie , Galoisovy teorie , konečné geometrie , kryptografie a teorie kódování .

Vlastnosti

Konečné pole je konečná množina, což je pole ; to znamená, že násobení, sčítání, odčítání a dělení (kromě dělení nulou) jsou definovány a splňují pravidla aritmetiky známé jako pole axiomy .

Počet prvků konečného pole se nazývá jeho pořadí nebo někdy jeho velikost . Konečné pole řádu q existuje tehdy a jen tehdy, pokud q je primární mocnina p ^k (kde p je prvočíslo a k je kladné celé číslo). V poli řádu p ^k má přidání p kopií jakéhokoli prvku vždy za následek nulu; to znamená, že charakteristika pole je p .

Pokud q = p ^k , všechna pole řádu q jsou izomorfní (viz § Existence a jedinečnost níže). Pole navíc nemůže obsahovat dvě různá konečná podpole se stejným pořadím. Lze tedy identifikovat všechny konečná pole ve stejném pořadí, a jsou jednoznačně označeny , F _q nebo GF ( q ) , kde písmena GF znamenají „Osnova pole“. ${\ displaystyle \ mathbb {F} _ {q}}$

V konečném poli řádu q má polynom X ^q - X všechny q prvky konečného pole jako kořeny . Nenulové prvky konečného pole tvoří multiplikativní skupinu . Tato skupina je cyklická , takže všechny nenulové prvky lze vyjádřit jako mocniny jednoho prvku nazývaného primitivní prvek pole. (Obecně bude pro dané pole existovat několik primitivních prvků.)

Nejjednodušší příklady konečných polí jsou pole nultý pořadí: pro každé prvočíslo p , v primární oblasti objednávky p , , mohou být konstruovány jako celých čísel p , Z / p Z . ${\ displaystyle \ mathbb {F} _ {p}}$

Prvky primárního pole řádu p mohou být reprezentovány celými čísly v rozsahu 0, ..., p - 1 . Součet, rozdíl a produkt jsou zbytek dělení podle p výsledku odpovídající provozu celé číslo. Multiplikativní inverzi prvku lze vypočítat pomocí rozšířeného euklidovského algoritmu (viz rozšířený euklidovský algoritmus § modulární celá čísla ).

Nechť F je konečné pole. Pro jakýkoli prvek x ve F a jakékoli celé číslo n označte n ⋅ x součet n kopií x . Nejméně kladné n takové, že n ⋅ 1 = 0, je charakteristika p pole. To umožňuje definovat násobení prvku k o GF ( p ), pomocí prvku x z F zvolením zástupce celé číslo o k . Toto násobení dělá F do GF ( p ) - vektorového prostoru . Z toho vyplývá, že počet prvků F je p ⁿ pro nějaké celé číslo n . ${\ Displaystyle (k, x) \ mapsto k \ cdot x}$

identity

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

(někdy se mu říká sen prváka ) platí v oblasti charakteristických p . To vyplývá z binomické věty , protože každý binomický koeficient expanze ( x + y ) ^p , kromě prvního a posledního, je násobkem p .

Podle Fermatovy malé věty platí , že pokud p je prvočíslo a x je v poli GF ( p ), pak x ^p = x . To znamená rovnost

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

pro polynomy nad GF ( p ) . Obecněji platí, že každý prvek v GF ( p ⁿ ) splňuje polynomickou rovnici x ^{p n} - x = 0 .

Jakékoli rozšíření konečného pole konečného pole je oddělitelné a jednoduché. To znamená, že pokud E je konečné pole a F je dílčí pole E , pak E je získáno z F souseděním jednoho prvku, jehož minimální polynom je oddělitelný. Chcete -li použít žargon, konečná pole jsou perfektní .

Obecnější algebraická struktura, která splňuje všechny ostatní axiomy pole, ale jejíž násobení nemusí být komutativní, se nazývá dělící prstenec (nebo někdy šikmé pole ). Podle Wedderburnovy malé věty je jakýkoli prsten konečné divize komutativní, a je tedy konečným polem.

Existence a jedinečnost

Nechť q = p ⁿ je primární mocnina a F je dělící pole polynomu

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

nad hlavním polem GF ( p ) . To znamená, že F je konečné pole nejnižšího pořadí, ve kterém P má q zřetelné kořeny (dále formální derivát z P je P ' = -1 , což znamená, že gcd ( P , P ' ) = 1 , což obecně znamená, že dělící pole je oddělitelné rozšíření originálu). Tyto výše uvedené identifikační ukazuje, že součet a produkt dvou kořenů P jsou kořeny P , jakož i multiplikativní inverzní kořeni P . Jinými slovy, kořeny P tvoří pole řádu q , které se rovná F minimalitou dělícího pole.

Jedinečnost až do izomorfismu dělících se polí tedy znamená, že všechna pole řádu q jsou izomorfní. Také pokud má pole F jako podpolí pole řádu q = p ^k , jeho prvky jsou q kořeny X ^q - X a F nemůže obsahovat další dílčí pole řádu q .

Stručně řečeno, máme následující klasifikační větu, kterou poprvé prokázal v roce 1893 EH Moore :

Pořadí konečného pole je primární mocností. Za každou primární energie q existuje pole řádu q , a všichni jsou isomorphic. V těchto polích každý prvek splňuje

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

a polynomiální X ^q - X faktory jako

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

Z toho vyplývá, že GF ( p ⁿ ) obsahuje podpole izomorfní na GF ( p ^m ) právě tehdy, když m je dělitel n ; v tom případě je toto podpole jedinečné. Ve skutečnosti polynom X ^{p m} - X dělí X ^{p n} - X právě tehdy, když m je dělitel n .

Explicitní konstrukce

Pole, která nejsou primární

Vzhledem k tomu, že primární výkon q = p ⁿ s p prime a n > 1 , pole GF ( q ) lze explicitně sestrojit následujícím způsobem. Nejprve si vyberete neredukovatelný polynom P v GF ( p ) [ X ] stupně n (takový neredukovatelný polynom vždy existuje). Pak kvocient prsten

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

polynomiálního prstence GF ( p ) [ X ] podle ideálu generovaného P je pole řádu q .

Přesněji řečeno, prvky GF ( q ) jsou polynomy přes GF ( p ), jejichž stupeň je přísně menší než n . Sčítání a odčítání jsou polynomy přes GF ( p ) . Produkt ze dvou částí je zbytek euklidovské rozdělení podle P produktu v GF ( p ) [ X ] . Multiplikativní inverzi nenulového prvku lze vypočítat pomocí rozšířeného euklidovského algoritmu; viz Rozšířený euklidovský algoritmus § Jednoduchá rozšíření algebraických polí .

S výjimkou konstrukce GF (4) existuje několik možných voleb pro P , které produkují izomorfní výsledky. Aby se zjednodušilo euklidovské dělení, pro P se běžně volí polynomy formuláře

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

díky čemuž jsou potřebné euklidovské divize velmi efektivní. V některých polích, typicky v charakteristice 2 , však neredukovatelné polynomy tvaru X ⁿ + aX + b nemusí existovat. Pokud je v charakteristice 2 polynom X ⁿ + X + 1 redukovatelný, doporučuje se zvolit X ⁿ + X ^k + 1 s nejnižší možnou hodnotou k, která činí polynom neredukovatelným. Pokud jsou všechny tyto trinomie redukovatelné, zvolí se „pentanomály“ X ⁿ + X ^a + X ^b + X ^c + 1 , protože polynomy stupně většího než 1 se sudým počtem výrazů nejsou nikdy neredukovatelné v charakteristice 2 , která má 1 jako kořen.

Možná volba pro takový polynom je dána Conwayovými polynomy . Zajišťují určitou kompatibilitu mezi reprezentací pole a reprezentacemi jeho podpolí.

V dalších částech si ukážeme, jak výše popsaná obecná konstrukční metoda funguje pro malá konečná pole.

Pole se čtyřmi prvky

Nejmenší non-prime pole je pole se čtyřmi prvky, které se běžně označeny GF (4), nebo se skládá ze čtyř prvků , takže i pro každý další výsledek operace je snadno vyvodit z distribuční práva . Níže jsou uvedeny kompletní provozní tabulky. ${\ 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),}$

To lze odvodit následovně z výsledků předchozí části.

Přes GF (2) existuje pouze jeden neredukovatelný polynom stupně2 :

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

Proto pro GF (4) musí konstrukce předchozí části zahrnovat tento polynom, a

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

Označme α kořen tohoto polynomu v GF (4) . Z toho vyplývá

α ² = 1 + α ,

a že α a 1 + α jsou prvky GF (4), které nejsou v GF (2) . Z toho vyplývají tabulky operací v GF (4) a jsou následující:

Sčítání x + y	Násobení x ⋅ y	Divize x / r
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

Tabulka pro odčítání není uvedena, protože odčítání je shodné sčítáním, jako je tomu u každého pole charakteristiky 2. Ve třetí tabulce pro dělení x na y musí být hodnoty x čteny v levém sloupci , a hodnoty y v horním řádku. (Protože 0 ⋅ z = 0 pro každé z v každém kruhu musí dělení 0 zůstat nedefinováno.)

Mapa

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

je netriviální pole automorphism, nazývaný Frobenius automorphism , který posílá α do druhého kořene 1 + α výše uvedeného neredukovatelného polynomu${\ displaystyle X^{2}+X+1.}$

GF ( p ² ) pro liché prvočíslo p

Pro aplikaci výše uvedené obecné konstrukce konečných polí v případě GF ( p ² ) je třeba najít neredukovatelný polynom stupně 2. Pro p = 2 to bylo provedeno v předchozí části. Je -li p liché prvočíslo, vždy existují neredukovatelné polynomy tvaru X ² - r , s r v GF ( p ) .

Přesněji řečeno, polynom X ² - r je neredukovatelný na GF ( p ) právě tehdy, když r je kvadratický nezesilovací modul p (to je téměř definice kvadratického nezbytku). Existují p - 1/2kvadratické zbytky modulo p . Například, 2 je kvadratická než zbytek pro p = 3, 5, 11, 13, ... , a 3 je kvadratická než zbytek pro p = 5, 7, 17, ... . Pokud p ≡ 3 mod 4 , tj. P = 3, 7, 11, 19, ... , lze jako kvadratický zbytek zvolit −1 ≡ p -1 , což nám umožňuje mít velmi jednoduchý neredukovatelný polynom X ² + 1 .

Když jsme zvolili kvadratický nezbytek r , nechť α je symbolická odmocnina z r , to je symbol, který má vlastnost α ² = r , stejným způsobem jako komplexní číslo i je symbolická odmocnina −1 . Potom jsou prvky GF ( p ² ) všechny lineární výrazy

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

s a a b v GF ( p ) . Operace na GF ( p ² ) jsou definovány následovně (operace mezi prvky GF ( p ) reprezentované latinkou jsou operace v GF ( p ) ):

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

GF (8) a GF (27)

Polynom

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

je neredukovatelný přes GF (2) a GF (3) , to znamená, že je neredukovatelný modulo 2 a 3 (k prokázání toho stačí ukázat, že nemá kořen v GF (2) ani v GF (3) ). Z toho vyplývá, že prvky GF (8) a GF (27) mohou být reprezentovány výrazy

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

kde a , b , c jsou prvky GF (2) nebo GF (3) (v tomto pořadí) a je symbolem, který ${\ displaystyle \ alpha}$

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

Sčítání, aditivní inverze a násobení na GF (8) a GF (27) lze tedy definovat následovně; v následujících vzorcích jsou operace mezi prvky GF (2) nebo GF (3) , reprezentované latinkou, operace v GF (2) respektive GF (3) :

${\ Displaystyle {\ begin {aligned}-(a +b \ alpha +c \ alpha ^{2}) & =-a +(-b) \ alpha +(-c) \ alpha ^{2} \ qquad {\ text {(for}} \ mathrm {GF} (8), {\ text {this operation is the identity)}} \\ (a+b \ alpha+c \ alpha ^{2})+(d+e \ alfa+f \ alpha ^{2}) & = (a+d)+(b+e) \ alpha+(c+f) \ alpha ^{2} \\ (a+b \ alpha+c \ alpha ^ {2}) (d+e \ alpha+f \ alpha ^{2}) & = (ad+bf+ce)+(ae+bd+bf+ce+cf) \ alpha+(af+be+cd+ cf) \ alpha ^{2} \ end {aligned}}}$

GF (16)

Polynom

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

je neredukovatelný přes GF (2) , to znamená, že je neredukovatelný modulo 2 . Z toho vyplývá, že prvky GF (16) mohou být reprezentovány výrazy

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

kde a , b , c , d jsou buď 0 nebo 1 (prvky GF (2) ), a α je symbol takový, že

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

(to znamená, že α je definováno jako kořen daného neredukovatelného polynomu). Protože charakteristika GF (2) je 2 , každý prvek je jeho aditivní inverzní v GF (16) . Sčítání a násobení na GF (16) může být definováno následovně; v následujících vzorcích jsou operace mezi prvky GF (2) , reprezentované latinkou, operace v GF (2) .

${\ 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) \ alpha+(c+g) \ alpha ^{2}+(d+h) \ alpha ^{3} \\ (a+ b \ alpha+c \ alpha ^{2}+d \ alpha ^{3}) (e+f \ alpha+g \ alpha ^{2}+h \ alpha ^{3}) & = (ae+bh+ cg+df)+(af+be+bh+cg+df+ch+dg) \ alpha \;+\\ & \ quad \; (ag+bf+ce+ch+dg+dh) \ alpha ^{2 }+(ah+bg+cf+de+dh) \ alpha ^{3} \ end {zarovnáno}}}$

Multiplikativní struktura

Množina nenulových prvků v GF ( q ) je abelianská skupina pod násobením, řádu q -1 . Podle Lagrangeovy věty existuje dělitel k o q -1 takový, že x ^k = 1 pro každé nenulové x v GF ( q ) . Protože rovnice x ^k = 1 má nejvýše k řešení v jakémkoli poli, q - 1 je nejnižší možná hodnota pro k . Věta Struktura konečných abelian skupin, znamená, že tato skupina je multiplikativní cyklická , to znamená, že všechny nenulové prvky jsou síly jednoho prvku. Celkem:

Multiplikativní skupina nenulových prvků v GF ( q ) je cyklická a existuje prvek a , takže q -1 nenulových prvků GF ( q ) jsou a , a ² , ..., a ^{q −2} , a ^{q −1} = 1 .

Takovému prvku a se říká primitivní prvek . Pokud q = 2, 3 , primitivní prvek není jedinečný. Počet primitivních prvků je φ ( q - 1), kde φ je Eulerova totientová funkce .

Výše uvedený výsledek znamená, že x ^q = x pro každé x v GF ( q ) . Konkrétním případem, kde q je prvočíslo, je Fermatova malá věta .

Diskrétní logaritmus

Pokud a je primitivní prvek v GF ( q ) , pak pro jakýkoli nenulový prvek x ve F existuje jedinečné celé číslo n s 0 ≤ n ≤ q -2 tak, že

x = a ⁿ .

Toto celé číslo n se nazývá diskrétního logaritmu o x k základně A .

Zatímco ⁿ může být vypočítána velmi rychle, například za použití umocňování tím, že srovná , není známa žádná efektivní algoritmus pro výpočet inverzní operaci, diskrétního logaritmu. To bylo použito v různých kryptografických protokolech , podrobnosti viz Diskrétní logaritmus .

Když jsou nenulové prvky GF ( q ) reprezentovány svými diskrétními logaritmy, je násobení a dělení snadné, protože se redukují na modul sčítání a odčítání q - 1 . Avšak přídavek činí výpočtem diskrétní logaritmus a ^m + s ⁿ . Identita

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

dovoluje vyřešit tento problém tím, že postaví tabulku diskrétních logaritmů na ⁿ + 1 , s názvem Zech je logaritmus , pro n = 0, ..., q - 2 (to je výhodné definovat diskrétního logaritmu nula jako - ∞ ).

Zechovy logaritmy jsou užitečné pro velké výpočty, jako je lineární algebra nad středně velkými poli, to znamená pro pole, která jsou dostatečně velká na to, aby přirozené algoritmy byly neúčinné, ale ne příliš velké, protože je třeba předem vypočítat tabulku stejné velikosti. jako pořadí pole.

Kořeny jednoty

Každý nenulový prvek konečného pole je kořenem jednoty , protože x ^{q −1} = 1 pro každý nenulový prvek GF ( q ) .

If n is a positive integer, an nth primitive root of unity is a solution of the equation xⁿ = 1 that is not a solution of the equation x^m = 1 for any positive integer m < n. If a is a nth primitive root of unity in a field F, then F contains all the n roots of unity, which are 1, a, a², ..., aⁿ⁻¹.

Pole GF ( q ) obsahuje n -tý primitivní kořen jednoty právě tehdy, když n je dělitelem q - 1 ; pokud n je dělitelem q - 1 , pak počet primitivní n th kořeny jednoty v GF ( q ) je φ ( n ) ( Eulerovo totient funkce ). Počet n -tých kořenů jednoty v GF ( q ) je gcd ( n , q - 1) .

V poli charakteristiky p je každý ( np ) th kořen jednoty také n -tým kořenem jednoty. Z toho vyplývá, že primitivní ( np ) th kořeny jednoty nikdy neexistují v poli charakteristických p .

Na druhé straně, jestliže n je coprime k p , kořeny n th cyclotomic polynomiální jsou odlišné v každé oblasti charakteristické p , jak je to polynom je dělitelem X ⁿ - 1 , jehož diskriminační nenulová modulo p . Z toho vyplývá, že n th cyclotomic polynomiální faktory přes GF ( p ) do různých nesnížitelnýma polynomů, které mají všechny stejný stupeň, řekněme D , a že GF ( p ^d ) je nejmenší oblast charakteristické p , který obsahuje n -tého primitivní kořeny jednota. ${\ displaystyle n^{n}}$

Příklad: GF (64)

Pole GF (64) má několik zajímavých vlastností, které menší pole nesdílejí: má dvě podpolí, takže ani jedno není obsaženo v druhém; ne všechny generátory (prvky s minimálním polynomem stupně 6 nad GF (2) ) jsou primitivní prvky; a primitivní prvky nejsou všechny konjugované pod Galoisovou skupinou .

Pořadí tomto poli je 2 ⁶ , a dělitelé 6 je 1, 2, 3, 6 , subfields GF (64) jsou GF (2) , GF (2 ² ) = GF (4) , GF (2 ³ ) = GF (8) a samotný GF (64) . Protože 2 a 3 jsou coprime , je průnik GF (4) a GF (8) v GF (64) hlavním polem GF (2) .

Spojení GF (4) a GF (8) má tedy 10 prvků. Zbývajících 54 prvků GF (64) generuje GF (64) v tom smyslu, že žádné jiné podpole neobsahuje žádné z nich. Z toho vyplývá, že jsou kořeny neredukovatelných polynomů stupně 6 nad GF (2) . To znamená, že přes GF (2) je přesně 9 =54/6neredukovatelné monické polynomy stupně 6 . To lze ověřit součinitelem X ⁶⁴ - X nad GF (2) .

Prvky GF (64) jsou primitivními n kořeny jednoty pro některé n dělící 63 . Jelikož 3. a 7. kořen jednoty patří GF (4) a GF (8) , je 54 generátorů primitivními n kořeny jednoty pro některé n v {9, 21, 63} . Eulerova totientová funkce ukazuje, že existuje 6 primitivních 9. kořenů jednoty, 12 primitivních 21. kořenů jednoty a 36 primitivních 63 kořenů jednoty. Když tyto čísla sečteme, znovu najdeme 54 prvků.

Faktoringovými na cyclotomic polynomy nad GF (2) , zjistíme, že:

• Šest primitivních 9. kořenů jednoty je kořeny

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

a všechny jsou konjugované působením skupiny Galois.

• Dvanáct primitivních 21. kořenů jednoty je kořeny

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

Pod působením skupiny Galois tvoří dvě oběžné dráhy. Protože jsou tyto dva faktory vzájemné , kořen a jeho (multiplikativní) inverze nepatří na stejnou oběžnou dráhu.

• K 36 primitivní prvky GF (64) jsou kořeny

${\ 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),}$

Pod působením skupiny Galois se rozdělili na 6 oběžných drah 6 prvků.

To ukazuje, že nejlepší volbou pro konstrukci GF (64) je definovat jej jako GF (2) [ X ] / ( X ⁶ + X + 1) . Ve skutečnosti je tento generátor primitivním prvkem a tento polynom je neredukovatelný polynom, který produkuje nejjednodušší euklidovské dělení.

Frobenius automorfismus a Galoisova teorie

V této sekci je p prvočíslo a q = p ⁿ je mocnina p .

V GF ( q ) identita ( x + y ) ^p = x ^p + y ^p znamená, že mapa

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

je GF ( p ) - lineární endomorphism a pole Automorphism z GF ( q ) , který řeší každý prvek podpole GF ( p ) . Říká se mu automorfismus Frobenius , po Ferdinandu Georgu Frobeniovi .

Označíme-li by cp ^K o složení a cp s sebou K časy, máme

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

V předchozí části bylo ukázáno, že φ ⁿ je identita. Pro 0 < k < n není automorfismus φ ^k identita, protože jinak je polynom

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

bude mít více než p ^k kořenů.

Neexistují žádné jiné GF ( p ) -automorfismy GF ( q ) . Jinými slovy, GF ( p ⁿ ) má přesně n GF ( p ) -automorfismy, které jsou

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

Z hlediska teorie Osnova , to znamená, že GF ( p ⁿ ) je rozšíření Galoisovo z GF ( p ) , který má cyklickou Galoisova skupinu.

Skutečnost, že mapa Frobenius je surjektivní, znamená, že každé konečné pole je dokonalé .

Polynomiální faktorizace

Jestliže F je konečné pole, nekonstantní monic polynom s koeficienty v F je nesnížitelný přes F , pokud není produkt dvou nekonstantní monic polynomů, s koeficienty v F .

Protože každý polynomický prstenec nad polem je jedinečnou doménou faktorizace , každý monický polynom nad konečným polem může být začleněn jedinečným způsobem (až do pořadí faktorů) do produktu neredukovatelných monických polynomů.

Existují účinné algoritmy pro testování polynomiální neredukovatelnosti a faktoring polynomů přes konečné pole. Jsou klíčovým krokem pro faktoring polynomů přes celá čísla nebo racionální čísla . Přinejmenším z tohoto důvodu má každý počítačový algebraický systém funkce pro faktoring polynomů přes konečná pole nebo alespoň přes konečná primární pole.

Neredukovatelné polynomy daného stupně

Polynom

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

faktory na lineární faktory v poli řádu q . Přesněji, tento polynom je součinem všech monických polynomů stupně jedna přes pole řádu q .

To znamená, že pokud q = p ^n, pak X ^q - X je součinem všech monických neredukovatelných polynomů přes GF ( p ) , jejichž stupeň dělí n . Ve skutečnosti, pokud P je ireducibilní faktor přes GF ( p ) z X ^q - X , stupeň jeho dělí n , jak je jeho rozdělení pole je obsažena v GF ( p ⁿ ) . Naopak, pokud P je neredukovatelný monický polynom nad GF ( p ) stupně d dělícího n , definuje rozšíření pole stupně d , které je obsaženo v GF ( p ⁿ ) , a všechny kořeny P patří do GF ( p ⁿ ) , a jsou kořeny X ^q - X ; tak P dělí X ^q - X . Protože X ^q - X nemá žádný násobný faktor, je tedy součinem všech neredukovatelných monických polynomů, které jej dělí.

Tato vlastnost se používá k výpočtu součinu neredukovatelných faktorů každého stupně polynomů přes GF ( p ) ; viz Faktorizace odlišného stupně .

Počet monicky neredukovatelných polynomů daného stupně v konečném poli

Počet N ( q , n ) monických neredukovatelných polynomů stupně n nad GF ( q ) je dán vztahem

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

kde μ je Möbiova funkce . Tento vzorec je téměř přímým důsledkem výše majetku X ^q - X .

Podle výše uvedeného vzorce, počet nerozložitelné (ne nutně monic) polynomy stupně n přes GF ( q ) je ( q - 1) N ( q , n ) .

A (o něco jednodušší) dolní mez pro N ( q , n ) je

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

Lze snadno odvodit, že pro každé q a každé n existuje alespoň jeden neredukovatelný polynom stupně n nad GF ( q ) . Tato dolní hranice je ostrá pro q = n = 2 .

Aplikace

V kryptografii je obtížnost problému diskrétního logaritmu v konečných polích nebo v eliptických křivkách základem několika široce používaných protokolů, jako je protokol Diffie – Hellman . Například v roce 2014 zahrnovalo zabezpečené internetové připojení k Wikipedii protokol eliptické křivky Diffie – Hellman ( ECDHE ) přes velké konečné pole. V teorii kódování , mnoho kódy jsou konstruovány jako subspaces z vektorových prostorů přes konečná pole.

Konečná pole používá mnoho kódů pro opravu chyb , například kód pro opravu chyb Reed – Solomon nebo kód BCH . Konečné pole má téměř vždy charakteristiku 2, protože počítačová data jsou ukládána binárně. Bajt dat lze například interpretovat jako prvek . Jedinou výjimkou je čárový kód PDF417 , což je . Některé CPU mají speciální instrukce, které mohou být užitečné pro konečná pole charakteristiky 2, obecně variace beznástrojového produktu . ${\ displaystyle GF (2^{8})}$${\ displaystyle GF (929)}$

Konečná pole jsou široce používána v teorii čísel , protože mnoho problémů s celými čísly lze vyřešit jejich snížením modulo o jedno nebo několik prvočísel . Například nejrychlejší známé algoritmy pro polynomickou faktorizaci a lineární algebru v oblasti racionálních čísel pokračují redukcí modulo jednou nebo několika prvočísly a poté rekonstrukcí řešení pomocí čínské věty o zbytku , Henselova zvedání nebo algoritmu LLL .

Podobně mnoho teoretických problémů v teorii čísel lze vyřešit zvážením jejich redukce modulo některých nebo všech prvočísel. Viz například Hasseův princip . Mnoho nedávných vývojů algebraické geometrie bylo motivováno potřebou rozšířit sílu těchto modulárních metod. Wilesův důkaz Fermatovy poslední věty je příkladem hlubokého výsledku zahrnujícího mnoho matematických nástrojů, včetně konečných polí.

Tyto Weil dohady se týkají počtu bodů na algebraických odrůd nad konečných polí a teorie má mnoho aplikací, včetně exponenciální a charakterových suma odhady.

Konečná pole mají široké uplatnění v kombinatorice , dva dobře známé příklady jsou definice Paley Graphs a související konstrukce pro Hadamard Matrices . V aritmetické kombinatorice se hojně používají konečná pole a modely konečných polí, například ve Szemerédiho větě o aritmetických postupech.

Rozšíření

Algebraické uzavření

Konečné pole F není algebraicky uzavřeno: polynom

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

nemá žádné kořeny v F , protože f  ( α ) = 1 pro všechny alfa v F .

Opravit algebraické uzavření všech . Mapa odeslání každé x až x ^q se nazývá q th výkonu Frobeniova automorfismus . Podpole fixované n -tou iterací je množina nul polynomu x ^{q n} - x , která má odlišné kořeny, protože její derivace v je −1 , která nikdy není nulová. Proto má toto podpole q ⁿ prvků, takže je to jedinečná kopie souboru in . Každé konečné rozšíření in je pro nějaké n , takže ${\ displaystyle {\ overline {\ mathbb {F}}} _ {q}}$${\ displaystyle \ mathbb {F} _ {q}}$${\ Displaystyle \ varphi _ {q} \ colon {\ 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}}.}$

Absolutní Galois skupina ze je profinite skupina${\ displaystyle \ mathbb {F} _ {q}}$

${\ displaystyle \ operatorname {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}}}.}$

Jako každá nekonečná skupina Galois může být vybavena krullskou topologií a pak právě uvedené izomorfismy jsou izomorfismy topologických skupin . Obraz ve skupině je generátor 1 , takže odpovídá . Z toho vyplývá, že má nekonečný řád a generuje hustou podskupinu , nikoli celou skupinu, protože prvek má nekonečný řád a generuje hustou podskupinu. Jeden říká, že je topologickým generátorem . ${\ displaystyle \ operatorname {Gal} ({\ overline {\ mathbb {F}}} _ {q}/\ mathbb {F} _ {q})}$${\ displaystyle \ varphi _ {q}}$${\ displaystyle \ operatorname {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 \ operatorname {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 \ operatorname {Gal} ({\ overline {\ mathbb {F}}} _ {q}/\ mathbb {F} _ {q})}$

Kvazi-algebraické uzavření

Ačkoli konečná pole nejsou algebraicky uzavřená, jsou kvazialgebraicky uzavřená , což znamená, že každý homogenní polynom nad konečným polem má netriviální nulu, jejíž složky jsou v poli, pokud je počet jeho proměnných větší než jeho stupeň. Toto byla domněnka Artina a Dicksona, kterou dokázal Chevalley (viz Chevalley - Varovná věta ).

Wedderburnova malá věta

Rozdělení ring je zobecněním pole. Divizní prsteny se nepředpokládají jako komutativní. Neexistují žádné nekomutativní prstence konečných divizí: Wedderburnova malá věta uvádí, že všechny prsteny konečných divizí jsou komutativní, tedy konečná pole. Výsledek platí, i když uvolníme asociativitu a uvažujeme o alternativních prstencích , podle Artin -Zornovy věty .

Viz také

• Kvazi-konečné pole
• Pole s jedním prvkem
• Aritmetika konečného pole
• Konečný prsten
• Konečná skupina
• Elementární abelianská skupina
• Hammingův prostor

Poznámky

Reference

externí odkazy

• Konečná pole ve výzkumu Wolfram.