Normal grund

Inom matematiken , särskilt den algebraiska teorin om fält , är en normal bas en speciell sorts bas för Galois-förlängningar av ändlig grad, kännetecknad av att den bildar en enda omloppsbana för Galois-gruppen . Normalbassatsen säger att varje finit Galois-utvidgning av fält har en normal bas . I algebraisk talteori är studiet av den mer raffinerade frågan om förekomsten av en normal integralbas en del av Galois modulteorin .

Normal grundsats

Låt $F\subset K$ vara en Galois-tillägg med Galois-grupp $G$ . Den klassiska normalbassatsen säger att det finns ett element $\beta \in K$ så att $\{g(\beta ):g\in G \}$ bildar en bas för K , betraktad som ett vektorrum över F . Det vill säga alla element $\alpha \in K$ kan skrivas unikt som ${\textstyle \alpha =\summa _{g\in G}a_ {g}\,g(\beta )}$ för vissa element $a_{g}\in F.$

En normal bas står i kontrast till en primitiv elementbas av formen $\{1,\beta ,\beta ^{2},\ldots ,\beta ^ {n-1}\}$ , där $\beta \in K$ är ett element vars minimala polynom har grad $n=[K:F]$ .

Grupprepresentationssynpunkt

En fältförlängning $K/F$ med Galois-grupp G kan naturligt ses som en representation av gruppen G över fältet F där varje automorfism representeras av sig själv. Representationer av G över fältet F kan ses som vänstermoduler för gruppalgebra $F[G]$ . Varje homomorfism av vänster $F[G]$ -moduler $\phi :F[G]\högerpil K$ har formen $\phi (r)=r\beta$ för vissa $\beta \in K$ . Sedan $\{1\cdot \sigma |\sigma \in G\}$ är en linjär bas för $F[G]$ över F , det följer lätt att ${\ displaystyle \phi }$ är bijektiv om $\beta$ genererar en normal bas av K över F . Den normala bassatsen motsvarar därför påståendet att om $K/F$ är finit Galois-förlängning, då $K\cong F[G]$ som vänster $F[G]$ -modul. När det gäller representationer av G över F betyder detta att K är isomorft med den reguljära representationen .

Fall av ändliga fält

För finita fält kan detta anges på följande sätt: Låt $F=\mathrm {GF} (q)=\mathbb {F} _{q}$ beteckna fältet för q element, där q = p ^m är en primpotens, och låt $K=\mathrm {GF} (q^{n})=\mathbb {F} _ {q^{n}}$ betecknar dess förlängningsfält av grad n ≥ 1. Här är Galois-gruppen $G={\text{Gal}}(K/F)=\{1,\Phi ,\Phi ^{2},\ldots ,\Phi ^{n-1}\}$ med ${ \displaystyle \Phi ^{n}=1,}$ en cyklisk grupp genererad av q -potentialen Frobenius automorfism $\Phi (\alpha )=\alpha ^{q},$ med $\Phi ^{n}=1=\mathrm {Id} _{K}.$ Då finns det ett element β ∈ K så att

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

är en bas av K över F .

Bevis för ändliga fält

Om Galois-gruppen är cyklisk enligt ovan, genererad av $\Phi$ med $\Phi ^{n}=1,$ följer normalbassatsen från två grundläggande fakta. Den första är det linjära oberoendet av tecken: ett multiplikativt tecken är en avbildning av χ från en grupp H till ett fält K som uppfyller $\chi (h_ {1}h_{2})=\chi (h_{1})\chi (h_{2})$ ; då är alla distinkta tecken $\chi _{1},\chi _{2},\ldots$ linjärt oberoende i K -vektorrymden av mappningar. Vi tillämpar detta på Galois-gruppens automorfismer $\chi _{i}=\Phi ^{i}:K\to K,$ tänkt som avbildningar från den multiplikativa gruppen $H=K^{\times }$ . Nu $K\cong F^{n}$ som ett F -vektorutrymme, så vi kan betrakta $\Phi :F^{n}\to F^ {n}$ som ett element i matrisalgebra $M_{n}(F);$ eftersom dess potenser $1,\Phi ,\ldots ,\Phi ^{n-1}$ är linjärt oberoende (över K och a fortiori över F ), måste dess minimala polynom ha graden minst n , dvs det måste vara $X^{n}-1$ .

Det andra grundläggande faktumet är klassificeringen av ändligt genererade moduler över en PID såsom $F[X]$ . Varje sådan modul M kan representeras som ${\textstyle M\cong \bigoplus _{i=1}^{k}{\frac {F[ X]}{(f_{i}(X))}}}$ , där $\displaystyle f_{i}(X)}$$f_{i+1}(X)$ kan väljas så att de är monopolynom eller noll och är en multipel av $f_{i}(X)$ . $f_{k}(X)$ är det moniska polynomet av minsta grad som förstör modulen, eller noll om inget sådant polynom som inte är noll existerar. I det första fallet ${\textstyle \dim _{F}M=\summa _{i=1}^{k}\deg f_{i}} ,$ i det andra fallet $\dim _{F}M=\infty$ . I vårt fall med cyklisk G av storlek n genererad av $\Phi$ har vi en F -algebraisomorfism ${\textstyle F[G]\cong { \frac {F[X]}{(X^{n}-1)}}}$ där X motsvarar $1\cdot \Phi$ , så varje $F[G ]$ -modulen kan ses som en $F[X]$ -modul där multiplikation med X är multiplikation med $1\cdot \Phi$ . I fallet K betyder detta $X\alpha =\Phi (\alpha )$ , så det moniska polynomet av minsta grad som förintar K är det minimala polynomet av $\Phi$ . Eftersom K är ett ändligt dimensionellt F -rum, är representationen ovan möjlig med $f_{k}(X)=X^{n}-1$ . Eftersom $\dim _{F}(K)=n,$ kan vi bara ha $k=1$ , och ${\textstyle K\cong {\frac {F[X]}{(X^{n}{-}\,1)}}} som$ F $\displaystyle F[X]}$ - moduler. (Observera att detta är en isomorfism av F -linjära rum, men inte av ringar eller F -algebror!) Detta ger isomorfism av $F[G]$ -moduler $K \cong F[G]$ som vi pratade om ovan, och under den basen $\{1,X,X^{2},\ldots ,X^{n-1}\}$ på höger sida motsvarar en normal bas $\{\ beta ,\Phi (\beta ),\Phi ^{2}(\beta ),\ldots ,\Phi ^{n-1}(\beta )\}$ av K till vänster.

Observera att detta bevis även skulle gälla i fallet med en cyklisk Kummer-förlängning .

Exempel

Betrakta fältet $K=\mathrm {GF} (2^{3})=\mathbb {F} _{8}$ över ${\displaystyle F=\mathrm {GF} (2)=\mathbb {F} _{2}} ,$ med Frobenius automorfism $\Phi (\alpha )=\alpha ^{2}$ . Beviset ovan klargör valet av normala baser i termer av strukturen av K som en representation av G (eller F [ G ]-modul). Den oreducerbara faktoriseringen

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

betyder att vi har en direkt summa av F [ G ]-moduler (med den kinesiska restsatsen ):

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

Den första komponenten är bara $F\subset K$ , medan den andra är isomorf som en F [ G ]-modul till ${ \displaystyle \mathbb {F} _{2^{2}}\cong \mathbb {F} _{2}[X]/(X^{2}{+}X{+}1)} under$ åtgärden $\Phi \cdot X^{i}=X^{i+1}.$ (Därför $K\cong \mathbb {F} _{2}\oplus \mathbb {F} _{4}$ som F [ G ]-moduler, men inte som F -algebror.)

Elementen $\beta \in K$ som kan användas för en normal bas är just de utanför någon av undermodulerna, så att ( $\displaystyle (\Phi {+ }1)(\beta )\neq 0}$ och $(\Phi ^{2}{+}\Phi {+}1)(\beta )\neq 0$ . När det gäller G -banorna för K , som motsvarar de irreducerbara faktorerna för:

$$t^{2^{3}}-t\ =\ t(t{+}1)\vänster(t^{3}+t+1\höger)\vänster(t^{3}+t^{2}+1\höger)\ \in \ F[ t],$$

elementen i $F=\mathbb {F} _{2}$ är rötterna till $t(t{+}1)$ , elementen som inte är noll undermodul $\mathbb {F} _{4}$ är rötterna till ${\displaystyle t^{3}+t+1} ,$ medan den normala basen, som i detta fall är unik, ges av rötterna av den återstående faktorn $t^{3}{+}t^{2}{+}1$ .

Däremot för tilläggsfältet $L=\mathrm {GF} (2^{4})=\mathbb {F} _{16}$ där n = 4 är delbart med p = 2, vi har F [ G ]-modulen isomorfism

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

Här är operatorn $\Phi \cong X$ inte diagonaliserbar , modulen L har kapslade undermoduler givna av generaliserade egenrymd av ${\displaystyle \Phi } ,$ och de normala baselementen β är de utanför den största egentliga generaliserat egenrum, elementen med $(\Phi {+}1)^{3}(\beta )\neq 0$ .

Applikation för kryptografi

Den normala basen används ofta i kryptografiska applikationer baserade på det diskreta logaritmproblemet, såsom elliptisk kurvkryptografi , eftersom aritmetik som använder en normal bas vanligtvis är mer beräkningseffektivt än att använda andra baser.

Till exempel, i fältet $K=\mathrm {GF} (2^{3})=\mathbb {F} _{8}$ ovan, kan vi representera element som bitsträngar:

$$\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 ,$$

där koefficienterna är bitar $a_{i}\in \mathrm {GF} (2)=\{0,1\}.$ Nu kan vi kvadratiska element genom att göra en cirkulär vänsterförskjutning, $\alpha ^{2}=\Phi (a_{2},a_{1},a_{0})=(a_{1},a_{0 },a_{2})$ , eftersom kvadrering av β ⁴ ger β ⁸ = β . Detta gör den normala basen särskilt attraktiv för kryptosystem som använder frekvent kvadrering.

Bevis för fallet med oändliga fält

Antag att $K/F$ är en finit Galois-förlängning av det oändliga fältet F . Låt $[K:F]=n$ , ${\displaystyle {\text{Gal}}(K/F)=G=\{\sigma _{1}...\sigma _{n}\}} , där σ$ 1 $displaystyle \sigma _{1}={\text{Id}}}$ . Genom den primitiva elementsatsen finns det $\alpha \in K$ såsom $i\neq j\implies \sigma _{i} (\alpha )\neq \sigma _{j}(\alpha )$ och $K=F[\alpha ]$ . Låt oss skriva $\alpha _{i}=\sigma _{i}(\alpha )$ . $\alpha$ s (moniska) minimala polynom f över K är den irreducerbara graden n polynom som ges av formeln

$${\begin{aligned}f(X)&=\prod _{i=1}^{n}(X-\alpha _{ i})\end{aligned}}$$

Eftersom f är separerbart (det har enkla rötter) kan vi definiera

$${\begin{aligned}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)).\ end{aligned}}$$

Med andra ord,

$${\begin{aligned}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).\end{aligned}}$$

Observera att $g(\alpha )=1$ och $g_{i}(\alpha )=0$ för $\displaystyle i\neq 1}$ . Definiera sedan en $n\ gånger n$ matris A av polynom över K och ett polynom D med

$${\begin{aligned}A_{ ij}(X)&=\sigma _{i}(\sigma _{j}(g(X))=\sigma _{i}(g_{j}(X))\\D(X)&= \det A(X).\end{aligned}}$$

Observera att ${\displaystyle A_{ij}(X)=g_{k}(X)} ,$ där k bestäms av $\sigma _{k}=\sigma _{i}\cdot \sigma _{j}$ ; i synnerhet $k=1$ iff $\sigma _{i}=\sigma _{j}^{-1}$ . Det följer att $A(\alpha )$ är permutationsmatrisen som motsvarar permutationen av G som skickar varje $\sigma _{i}$ till $\ sigma _{i}^{-1}$ . (Vi betecknar med $A(\alpha )$ matrisen som erhålls genom att utvärdera $A(X)$ vid $x=\alpha$ .) Därför, $D(\alpha )=\det A(\alpha )=\pm 1$ . Vi ser att D är ett polynom som inte är noll, och därför har det bara ett ändligt antal rötter. Eftersom vi antog att F är oändlig kan vi hitta $a\in F$ så att $D(a)\neq 0$ . Definiera

$${\begin{aligned}\beta &=g(a)\\\beta _{i}&=g_{i}(a)=\sigma _{i}(\beta ).\end{aligned }}$$

Vi hävdar att $\{\beta _{1},\ldots ,\beta _{n}\}$ är en normal bas. Vi behöver bara visa att $\beta _{1},\ldots ,\beta _{n}$ är linjärt oberoende av F , så anta att ${\textstyle \sum _{j=1}^{n}x_{j}\beta _{j}=0}$ för några $x_{1}...x_{n}\in F$ . Att tillämpa automorfismen $\sigma _{i}$ ger ${\textstyle \sum _{j=1}^{n}x_{ j}\sigma _{i}(g_{j}(a))=0}$ för alla i . Med andra ord, $A(a)\cdot {\overline {x}}={\overline {0}}$ . Eftersom $\det A(a)=D(a)\neq 0$ drar vi slutsatsen att ${\overline {x}}={ \overline {0}}$ , vilket kompletterar beviset.

Det är frestande att ta $a=\alpha$ eftersom $D(\alpha )\neq 0$ . Men detta är otillåtet eftersom vi använde det faktum att $a\in F$ för att dra slutsatsen att för varje F -automorfism $\sigma$ och polynom $h(X)$ över $K$ värdet av polynomet $\sigma (h(X))$ vid $a$ är lika med $\ sigma (h(a))$ .

Primitiv normalgrund

En primitiv normalbas för en förlängning av finita fält E / F är en normal bas för E / F som genereras av ett primitivt element av E , det vill säga en generator av den multiplikativa gruppen $K^{\times }$ . (Observera att detta är en mer restriktiv definition av primitivt element än den som nämns ovan efter den allmänna normalbassatsen: man kräver krafter hos elementet för att producera varje element som inte är noll, inte bara en bas.) Lenstra och Schoof (1987) ) bevisade att varje finit fältförlängning har en primitiv normal bas, fallet när F är ett primfält har avgjorts av Harold Davenport .

Gratis element

Om K / F är en Galois-förlängning och x i K genererar en normal bas över F , då är x fri i K / F . Om x har egenskapen att för varje undergrupp H i Galois-gruppen G , med fast fält K ^H , är x fri för K / K ^H , så sägs x vara helt fri i K / F . Varje Galois-tillägg har ett helt gratis element.

Se även

• Dubbel basis i en fältförlängning
• Polynombas
• Zechs logaritm

•    Cohen, S.; Niederreiter, H. , red. (1996). Finita fält och applikationer. Handlingar från den tredje internationella konferensen, Glasgow, Storbritannien, 11–14 juli 1995 . London Mathematical Society föreläsningsanteckningsserie. Vol. 233. Cambridge University Press . ISBN 978-0-521-56736-7 . Zbl 0851.00052 .
•    Lenstra, HW, jr ; Schoof, RJ (1987). "Primitiva normala baser för finita fält" . Beräkningsmatematik . 48 (177): 217–231. doi : 10.2307/2007886 . JSTOR 2007886 . Zbl 0615.12023 .
•    Menezes, Alfred J. , red. (1993). Tillämpningar av finita fält . Kluwer International Series in Engineering and Computer Science. Vol. 199. Boston: Kluwer Academic Publishers. ISBN 978-0792392828 . Zbl 0779.11059 .