Normální základ - Normal basis

v matematika, konkrétně algebraický teorie pole, a normální základ je zvláštní druh základ pro Galois rozšíření konečného stupně, charakterizovaný jako formování singlu obíhat pro Galoisova skupina. The věta o normální bázi uvádí, že jakékoli konečné rozšíření polí Galois má normální základ. v algebraická teorie čísel, studium rafinovanější otázky existence a normální integrální základ je část Galoisův modul teorie.

Věta o normální bázi

Nechat ${ displaystyle F podmnožina K}$ být rozšíření Galois se skupinou Galois ${ displaystyle G}$. Klasický věta o normální bázi uvádí, že existuje prvek ${ displaystyle beta v K}$ takhle ${ displaystyle {g ( beta): g v G }}$ tvoří základ K., považováno za vektorový prostor nad F. To znamená jakýkoli prvek ${ displaystyle alpha v K}$ lze psát jednoznačně jako ${ displaystyle textstyle alpha = součet _ {g v G} a_ {g} , g ( beta)}$ pro některé prvky ${ displaystyle a_ {g} ve F.}$

Normální základ kontrastuje s a primitivní prvek na základě formuláře ${ displaystyle {1, beta, beta ^ {2}, ldots, beta ^ {n-1} }}$, kde ${ displaystyle beta v K}$ je prvek, jehož minimální polynom má stupeň ${ displaystyle n = [K: F]}$.

Hledisko skupinové reprezentace

Rozšíření pole ${ displaystyle K / F}$ se skupinou Galois G lze přirozeně považovat za zastoupení skupiny G přes pole F ve kterém je každý automorfismus představován sám sebou. Zastoupení G přes pole F lze zobrazit jako levé moduly pro skupinová algebra ${ displaystyle F [G]}$. Každý homomorfismus levice ${ displaystyle F [G]}$- moduly ${ displaystyle phi: F [G] rightarrow K}$ má formu ${ displaystyle phi (r) = r beta}$ pro některé ${ displaystyle beta v K}$. Od té doby ${ displaystyle {1 cdot sigma | sigma v G }}$ je lineární základ ${ displaystyle F [G]}$ přes F, snadno z toho vyplývá ${ displaystyle phi}$ je bijective iff ${ displaystyle beta}$ generuje normální základnu K. přes F. Normální základová věta se tedy rovná tvrzení, že pokud ${ displaystyle K / F}$ je tedy konečné rozšíření Galois ${ displaystyle K cong F [G]}$ jak vlevo ${ displaystyle F [G]}$-modul. Pokud jde o reprezentace G přes F, tohle znamená tamto K. je isomorfní s pravidelné zastoupení.

Případ konečných polí

Pro konečná pole lze to uvést následovně:^[1] Nechat ${ displaystyle F = GF (q) = mathbb {F} _ {q}}$ označit pole q prvky, kde q = str^m je hlavní síla, a nechť ${ displaystyle K = GF (q ^ {n}) = mathbb {F} _ {q ^ {n}}}$ označit jeho rozšiřovací pole stupně n ≥ 1. Zde je skupina Galois ${ displaystyle G = { text {Gal}} (K / F) = {1, Phi, Phi ^ {2}, ldots, Phi ^ {n-1} }}$ s ${ displaystyle Phi ^ {n} = 1,}$ A cyklická skupina generované q-Napájení Frobenius automorfismus ${ displaystyle Phi ( alfa) = alfa ^ {q},}$s ${ displaystyle Phi ^ {n} = 1 = { textrm {Id}} _ {K}.}$ Pak existuje prvek β ∈ K. takhle

${ displaystyle { beta, Phi ( beta), Phi ^ {2} ( beta), ldots, Phi ^ {n-1} ( beta) } = { beta , beta ^ {q}, beta ^ {q ^ {2}}, ldots, beta ^ {q ^ {n-1}} ! }}$

je základem K. přes F.

Důkaz konečných polí

V případě, že skupina Galois je cyklická, jak je uvedeno výše, generovaná ${ displaystyle Phi}$ s ${ displaystyle Phi ^ {n} = 1,}$ Věta o normálním základu vyplývá ze dvou základních faktů. První je lineární nezávislost znaků: a multiplikativní charakter je mapování χ ze skupiny H na pole K. uspokojující ${ displaystyle chi (h_ {1} h_ {2}) = chi (h_ {1}) chi (h_ {2})}$; pak jakékoli odlišné znaky ${ displaystyle chi _ {1}, chi _ {2}, ldots}$ jsou lineárně nezávislé v K.-vektorový prostor mapování. Aplikujeme to na automorfismy skupiny Galois ${ displaystyle chi _ {i} = Phi ^ {i}: K až K,}$ myšlenka jako mapování z multiplikativní skupiny ${ displaystyle H = K ^ { times}}$. Nyní ${ displaystyle K cong F ^ {n}}$jako F-vektorový prostor, takže můžeme uvažovat ${ displaystyle Phi: F ^ {n} až F ^ {n}}$ jako prvek maticové algebry ${ displaystyle M_ {n} (F);}$ od jeho pravomocí ${ displaystyle 1, Phi, ldots, Phi ^ {n-1}}$ jsou lineárně nezávislé (přes K. a tím spíše F), své minimální polynom musí mít alespoň diplom n, tj. musí být ${ displaystyle X ^ {n} -1}$.

Druhým základním faktem je klasifikace konečně generovaných moduly přes PID jako ${ displaystyle F [X]}$. Každý takový modul M lze reprezentovat jako ${ displaystyle M cong bigoplus _ {i = 1} ^ {k} { frac {F [X]} {(f_ {i} (X))}}}$, kde ${ displaystyle f_ {i} (X)}$ mohou být vybrány tak, aby to byly monické polynomy nebo nula a ${ displaystyle f_ {i + 1} (X)}$ je násobkem ${ displaystyle f_ {i} (X)}$. ${ displaystyle f_ {k} (X)}$ je monický polynom nejmenšího stupně ničící modul, nebo nula, pokud takový nenulový polynom neexistuje. V prvním případě ${ displaystyle dim _ {F} M = součet _ {i = 1} ^ {k} deg f_ {i}}$ve druhém případě ${ displaystyle dim _ {F} M = infty}$. V našem případě cyklické G velikosti n generováno uživatelem ${ displaystyle Phi}$ máme F-algebra izomorfismus ${ displaystyle F [G] cong { frac {F [X]} {(X ^ {n} -1)}}}$ kde X odpovídá ${ displaystyle 1 cdot Phi}$, takže každý ${ displaystyle F [G]}$-module lze zobrazit jako ${ displaystyle F [X]}$-module s násobením X násobení ${ displaystyle 1 cdot Phi}$. V případě K. to znamená ${ displaystyle X alpha = Phi ( alpha)}$, takže monický polynom nejmenšího stupně ničí K. je minimální polynom z ${ displaystyle Phi}$. Od té doby K. je konečný rozměr F-prostor, výše uvedená reprezentace je možná s ${ displaystyle f_ {k} (X) = X ^ {n} -1}$. Od té doby ${ displaystyle dim _ {F} (K) = n,}$ můžeme jen mít ${ displaystyle k = 1}$, a ${ displaystyle K cong { frac {F [X]} {(X ^ {n} {-} , 1)}}}$ tak jako ${ displaystyle F [X]}$- moduly. (Všimněte si, že se jedná o izomorfismus F-lineární mezery, ale ne prstenů nebo F-algebry!) To dává izomorfismus ${ displaystyle F [G]}$- moduly ${ displaystyle K cong F [G]}$ o kterém jsme mluvili výše a pod ním základ ${ displaystyle {1, X, X ^ {2}, ldots, X ^ {n-1} }}$ na pravé straně odpovídá normálnímu základu ${ displaystyle { beta, Phi ( beta), Phi ^ {2} ( beta), ldots, Phi ^ {n-1} ( beta) }}$ z K. nalevo.

Všimněte si, že tento důkaz by platil také v případě cyklického Prodloužení Kummer.

Příklad

Zvažte pole ${ displaystyle K = GF (2 ^ {3}) = mathbb {F} _ {8}}$ přes ${ displaystyle F = GF (2) = mathbb {F} _ {2}}$, s Frobenius automorphism ${ displaystyle Phi ( alfa) = alfa ^ {2}}$. Výše uvedený důkaz objasňuje výběr normálních bází z hlediska struktury K. jako reprezentace G (nebo F[G]-modul). Neredukovatelná faktorizace

${ displaystyle X ^ {n} -1 = X ^ {3} -1 = (X {+} 1) (X ^ {2} {+} X {+} 1) v F [X]}$

znamená, že máme přímý součet F[G] -moduly (podle Čínská věta o zbytku ):

${ displaystyle K cong { frac {F [X]} {(X ^ {3} {-} , 1)}} cong { frac {F [X]} {(X { +} 1)}} oplus { frac {F [X]} {(X ^ {2} {+} X {+} 1)}}.}$

První složka je spravedlivá ${ displaystyle F podmnožina K}$, zatímco druhá je izomorfní jako F[G] -modul do ${ displaystyle mathbb {F} _ {2 ^ {2}} cong mathbb {F} _ {2} [X] / (X ^ {2} {+} X {+} 1)}$ pod akcí ${ displaystyle Phi cdot X ^ {i} = X ^ {i + 1}.}$ (Tím pádem ${ displaystyle K cong mathbb {F} _ {2} oplus mathbb {F} _ {4}}$ tak jako F[G] -modulů, ale ne tak jako F-algebry.)

Elementy ${ displaystyle beta v K}$ které lze běžně použít, jsou právě ty, které jsou mimo některý z podmodulů, takže ${ displaystyle ( Phi {+} 1) ( beta) neq 0}$ a ${ displaystyle ( Phi ^ {2} {+} Phi {+} 1) ( beta) neq 0}$. Z hlediska G-orbity K., které odpovídají neredukovatelným faktorům:

${ displaystyle t ^ {2 ^ {3}} - t = t (t {+} 1) (t ^ {3} {+} t {+} 1) (t ^ {3} {+} t ^ {2} {+} 1) in F [t],}$

prvky ${ displaystyle F = mathbb {F} _ {2}}$ jsou kořeny ${ displaystyle t (t {+} 1)}$, nenulové prvky submodulu ${ displaystyle mathbb {F} _ {4}}$ jsou kořeny ${ displaystyle t ^ {3} {+} t {+} 1}$, zatímco normální základ, který je v tomto případě jedinečný, je dán kořeny zbývajícího faktoru ${ displaystyle t ^ {3} {+} t ^ {2} {+} 1}$.

Naproti tomu pro pole rozšíření ${ displaystyle L = GF (2 ^ {4}) = mathbb {F} _ {16}}$ ve kterém n = 4 je dělitelné str = 2, máme F[G] izomorfismus modulu

${ displaystyle L cong mathbb {F} _ {2} [X] / (X ^ {4} {-} 1) = mathbb {F} _ {2} [X] / (X {+} 1) ^ {4}.}$

Tady operátor ${ displaystyle Phi cong X}$ není úhlopříčně, modul L má vnořené dílčí moduly dané uživatelem zobecněné vlastní prostory z ${ displaystyle Phi}$a běžné základní prvky β jsou ti mimo největší vlastní zobecněný vlastní prostor, prvky s ${ displaystyle ( Phi {+} 1) ^ {3} ( beta) neq 0}$.

Aplikace na kryptografii

Normální základ se často používá v kryptografické aplikace založené na problém diskrétního logaritmu, jako kryptografie eliptické křivky, protože aritmetika pomocí normálního základu je obvykle výpočetně efektivnější než použití jiných základen.

Například v terénu ${ displaystyle K = GF (2 ^ {3}) = mathbb {F} _ {8}}$ výše můžeme představovat prvky jako bitové řetězce:

${ displaystyle alpha = (a_ {2}, a_ {1}, a_ {0}) = a_ {2} Phi ^ {2} ( beta) + a_ {1} Phi ( beta) + a_ {0} beta = a_ {2} beta ^ {4} + a_ {1} beta ^ {2} + a_ {0} beta,}$

kde koeficienty jsou bity ${ displaystyle a_ {i} v GF (2) = {0,1 }.}$ Nyní můžeme čtvercové prvky provést levým kruhovým posunem, ${ displaystyle alpha ^ {2} = Phi (a_ {2}, a_ {1}, a_ {0}) = (a_ {1}, a_ {0}, a_ {2})}$, protože kvadratura β⁴ dává β⁸ = β. Díky tomu je normální základna obzvláště atraktivní pro kryptosystémy, které využívají časté kvadratury.

Důkaz pro případ nekonečných polí

Předpokládat ${ displaystyle K / F}$ je konečné Galoisovo rozšíření nekonečného pole F. Nechat ${ displaystyle [K: F] = n}$, ${ displaystyle { text {Gal}} (K / F) = G = { sigma _ {1} ... sigma _ {n} }}$, kde ${ displaystyle sigma _ {1} = { text {Id}}}$. Podle věta o primitivním prvku existují ${ displaystyle alpha v K}$ takhle ${ displaystyle K = F [ alpha]}$. Nechat F být minimální monický polynom z ${ displaystyle alpha}$. Pak F je neredukovatelný monický polynom stupně n přes F/ Označte ${ displaystyle alpha _ {i} = sigma _ {i} alpha}$. Od té doby F je stupně n, my máme ${ displaystyle alpha _ {i} neq alpha _ {j}}$ pro ${ displaystyle i neq j}$. Označit

${ displaystyle { begin {zarovnané} g (X) & = { frac {f (X)} {(X- alpha) f '( alpha)}} g_ {i} (X) & = { frac {f (X)} {(X- alpha _ {i}) f '( alpha _ {i})}} & = sigma _ {i} (g (X)) konec {zarovnáno}}}$

Jinými slovy, máme

${ displaystyle { begin {zarovnáno} f (X) & = prod _ {i = 1} ^ {n} (X- alpha _ {i}) g_ {i} (X) & = prod _ { begin {array} {c} 1 leq j leq n j neq i end {array}} { frac {X- alpha _ {j}} { alpha _ {i } - alpha _ {j}}} g (X) & = g_ {1} (X) konec {zarovnáno}}}$

Všimněte si, že ${ displaystyle g ( alpha) = 1}$ a ${ displaystyle g_ {i} ( alfa) = 0}$ pro ${ Displaystyle i neq 1}$. Dále definujte ${ displaystyle n krát n}$ matice A polynomů přes K. a polynomiální D podle

${ displaystyle { begin {zarovnáno} A_ {ij} (X) & = & sigma _ {i} ( sigma _ {j} (g (X)) & = & sigma _ {i} (g_ { j} (X)) D (X) & = & det A (X) end {zarovnáno}}}$

Dodržujte to ${ displaystyle A_ {ij} (X) = g_ {k} (X)}$, kde k je určeno ${ displaystyle sigma _ {k} = sigma _ {i} cdot sigma _ {j}}$, zejména ${ displaystyle k = 1}$ iff ${ displaystyle sigma _ {i} = sigma _ {j} ^ {- 1}}$. Z toho vyplývá, že ${ displaystyle A ( alpha)}$ je permutační matice odpovídající permutaci G který posílá každý ${ displaystyle sigma _ {i}}$ na ${ displaystyle sigma _ {i} ^ {- 1}}$. (Označujeme ${ displaystyle A ( alpha)}$ maticové prvky, z nichž jsou hodnoty prvků ${ displaystyle A (X)}$ na ${ displaystyle alpha}$.) Proto máme ${ displaystyle D ( alpha) = det A ( alpha) = pm 1}$. Vidíme to D je nenulový polynom, proto může mít pouze konečný počet kořenů. Protože předpokládáme F je nekonečný, můžeme najít ${ displaystyle a v F}$ takhle ${ displaystyle D (a) neq 0}$. Definovat

${ displaystyle { begin {aligned} beta & = & g (a) beta _ {i} & = & g_ {i} (a) & = & sigma _ {i} ( beta) end { zarovnaný}}}$

Tvrdíme to ${ displaystyle { beta _ {1} ... beta _ {n} }}$ je normální základ. Musíme to jen ukázat ${ displaystyle beta _ {1} ... beta _ {n}}$ jsou lineárně nezávislé F, tak předpokládejme ${ displaystyle sum _ {j = 1} ^ {n} x_ {j} beta _ {j} = 0}$ pro některé ${ displaystyle x_ {1} ... x_ {n} ve F}$. Uplatňování automorfismu ${ displaystyle sigma _ {i}}$ dostaneme ${ displaystyle sum _ {j = 1} ^ {n} x_ {j} sigma _ {i} (g_ {j} (a)) = 0}$ pro všechny i. Jinými slovy, ${ displaystyle A (a) cdot { overline {x}} = { overline {0}}}$. Od té doby ${ displaystyle det A (a) = D (a) neq 0}$, uzavíráme ${ displaystyle { overline {x}} = { overline {0}}}$, který doplňuje důkaz.

Všimněte si, že jsme využili skutečnost, že ${ displaystyle a v F}$, takže pro všechny F-automorfismus ${ displaystyle sigma}$ a polynomiální ${ displaystyle h (X)}$ přes ${ displaystyle K}$ hodnota polynomu ${ displaystyle sigma (h (X))}$ na ${ displaystyle a}$ rovná se ${ displaystyle sigma (h (a))}$. Proto jsme nemohli jednoduše vzít ${ displaystyle a = alpha}$.

Primitivní normální základ

A primitivní normální základ rozšíření konečných polí E/F je normální základ pro E/F který je generován a primitivní prvek z E, to je generátor multiplikativní skupiny ${ displaystyle K ^ { times}.}$ (Všimněte si, že se jedná o restriktivnější definici primitivního prvku, než byla uvedena výše po obecné větě o normálním základu: vyžaduje se, aby elementy produkovaly každý nenulový prvek K., nejen pouhý základ.) Lenstra a Schoof (1987) prokázali, že každé rozšíření konečného pole má primitivní normální základ, v případě, že F je hlavní pole který byl urovnán Harold Davenport.

Zdarma prvky

Li K./F je rozšíření Galois a X v E generuje normální základ F, pak X je volný, uvolnit v K./F. Li X má vlastnost, která pro každou podskupinu H skupiny Galois G, s pevným polem K.^H, X je zdarma pro K./K.^H, pak X se říká, že je zcela zdarma v K./F. Každé rozšíření Galois má zcela bezplatný prvek.^[2]

Viz také

• Dvojí základ v rozšíření pole
• Polynomiální základ
• Zechův logaritmus

Reference

• Cohen, S .; Niederreiter, H., eds. (1996). Konečná pole a aplikace. Sborník z 3. mezinárodní konference, Glasgow, Velká Británie, 11. – 14. Července 1995. Série přednášek London Mathematical Society. 233. Cambridge University Press. ISBN  978-0-521-56736-7. Zbl  0851.00052.
• Lenstra, HW, ml; Schoof, R.J. (1987). "Primitivní normální základy pro konečná pole". Matematika výpočtu. 48 (177): 217–231. doi:10.2307/2007886. JSTOR  2007886. Zbl  0615.12023.
• Menezes, Alfred J., vyd. (1993). Aplikace konečných polí. Mezinárodní série Kluwer ve strojírenství a informatice. 199. Boston: Kluwer Academic Publishers. ISBN  978-0792392828. Zbl  0779.11059.