Endliches Feld - Finite field

In der Mathematik ist ein endlicher Körper oder Galois-Körper (so genannt zu Ehren von Évariste Galois ) ein Körper , der eine endliche Anzahl von Elementen enthält . Wie bei jedem Körper ist ein endlicher Körper eine Menge, auf der die Operationen der Multiplikation, Addition, Subtraktion und Division definiert sind und bestimmte Grundregeln erfüllen. Die gebräuchlichsten Beispiele für endliche Körper sind die ganzen Zahlen mod p, wenn p eine Primzahl ist .

Finite Felder sind in einer Reihe von Gebieten der Mathematik und Informatik von grundlegender Bedeutung , darunter Zahlentheorie , algebraische Geometrie , Galois-Theorie , endliche Geometrie , Kryptographie und Codierungstheorie .

Eigenschaften

Ein endlicher Körper ist eine endliche Menge, die ein Körper ist ; das bedeutet, dass Multiplikation, Addition, Subtraktion und Division (ohne Division durch Null) definiert sind und die als Feldaxiome bekannten arithmetischen Regeln erfüllen .

Die Anzahl der Elemente eines endlichen Körpers wird seine Ordnung oder manchmal seine Größe genannt . Ein endlicher Körper der Ordnung q existiert genau dann, wenn q eine Primzahl p ^{k ist} (wobei p eine Primzahl und k eine positive ganze Zahl ist). In einem Feld der Ordnung p ^k führt das Addieren von p Kopien eines beliebigen Elements immer zu Null; das heißt, die Charakteristik des Feldes ist p .

Wenn q = p ^k , werden alle Felder der Ordnung q sind isomorph (siehe § Existenz und Eindeutigkeit unten). Außerdem kann ein Feld nicht zwei verschiedene endliche Unterfelder mit derselben Ordnung enthalten. Man kann daher alle endlichen Körper mit der gleichen Ordnung identifizieren, und sie werden eindeutig mit , F _q oder GF( q ) bezeichnet , wobei die Buchstaben GF für "Galois-Feld" stehen. ${\displaystyle \mathbb{F} _{q}}$

In einem endlichen Körper der Ordnung q hat das Polynom X ^q − X alle q Elemente des endlichen Körpers als Nullstellen . Die von Null verschiedenen Elemente eines endlichen Körpers bilden eine multiplikative Gruppe . Diese Gruppe ist zyklisch , sodass alle von Null verschiedenen Elemente als Potenzen eines einzelnen Elements ausgedrückt werden können, das als primitives Element des Feldes bezeichnet wird. (Im Allgemeinen gibt es mehrere primitive Elemente für ein gegebenes Feld.)

Die einfachsten Beispiele für endliche Körper sind die Körper Primzahl: Für jede Primzahl p kann der Primkörper der Ordnung p , , als ganze Zahlen modulo p , Z / p Z konstruiert werden . ${\displaystyle \mathbb{F}_{p}}$

Die Elemente des Primkörpers der Ordnung p können durch ganze Zahlen im Bereich 0, ..., p − 1 dargestellt werden . Die Summe, die Differenz und das Produkt sind der Rest der Division durch p des Ergebnisses der entsprechenden ganzzahligen Operation. Die multiplikative Inverse eines Elements kann unter Verwendung des erweiterten euklidischen Algorithmus berechnet werden (siehe Erweiterter euklidischer Algorithmus § Modulare ganze Zahlen ).

Sei F ein endlicher Körper. Bezeichne für jedes Element x in F und jede ganze Zahl n mit n ⋅ x die Summe von n Kopien von x . Die am wenigsten positiv n derart , dass n ⋅ 1 = 0 ist die charakteristische p des Feldes. Dies ermöglicht das Definieren einer Multiplikation eines Elements k von GF( p ) mit einem Element x von F durch Auswählen eines ganzzahligen Repräsentanten für k . Diese Multiplikation macht F in einem GF ( p ) - Vektorraum . Daraus folgt , dass die Anzahl der Elemente von F ist , p ⁿ für eine ganze Zahl n . ${\displaystyle (k,x)\mapsto k\cdot x}$

Die Identität

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

(manchmal auch der Traum des Studienanfängers genannt ) ist in einem Bereich mit charakteristischem p wahr . Dies folgt aus dem Binomialsatz , da jeder Binomialkoeffizient der Entwicklung von ( x + y ) ^p , außer dem ersten und dem letzten, ein Vielfaches von p ist .

Nach dem kleinen Satz von Fermat gilt : Wenn p eine Primzahl ist und x im Körper GF( p ) liegt, dann gilt x ^p = x . Dies impliziert die Gleichheit

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

für Polynome über GF( p ) . Allgemeiner gesagt erfüllt jedes Element in GF( p ⁿ ) die Polynomgleichung x ^{p n} − x = 0 .

Jede endliche Körpererweiterung eines endlichen Körpers ist separierbar und einfach. Das heißt, wenn E ein endlicher Körper und F ein Unterkörper von E ist , dann wird E aus F erhalten, indem ein einzelnes Element angefügt wird, dessen minimales Polynom trennbar ist. Um einen Jargon zu verwenden, sind endliche Felder perfekt .

Eine allgemeinere algebraische Struktur, die alle anderen Axiome eines Körpers erfüllt, deren Multiplikation jedoch nicht kommutativ sein muss, wird als Divisionsring (oder manchmal auch als Schrägfeld ) bezeichnet. Nach dem kleinen Satz von Wedderburn ist jeder endliche Teilungsring kommutativ und somit ein endlicher Körper.

Existenz und Einzigartigkeit

Sei q = p ⁿ eine Primzahlpotenz und F der Teilungskörper des Polynoms

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

über dem Primkörper GF( p ) . Dies bedeutet , dass F ein endlicher Körper von niedrigster Ordnung ist, in der P hat q verschiedene Wurzeln (die Formale Ableitung von P ist P ' = -1 , was impliziert , dass GCD ( P , P ' ) = 1 , was im allgemeinen bedeutet , dass die Aufteilungsfeld ist eine trennbare Erweiterung des Originals). Die obige Identität zeigt, dass die Summe und das Produkt zweier Wurzeln von P Wurzeln von P sowie die multiplikative Inverse einer Wurzel von P sind . Mit anderen Worten, die Wurzeln von P bilden einen Körper der Ordnung q , der durch die Minimalität des Teilungskörpers gleich F ist .

Die Eindeutigkeit bis auf Isomorphie der Teilungskörper impliziert also, dass alle Körper der Ordnung q isomorph sind. Auch wenn ein Körper F einen Körper der Ordnung q = p ^k als Unterkörper hat, sind seine Elemente die q Wurzeln von X ^q − X , und F kann keinen weiteren Unterkörper der Ordnung q enthalten .

Zusammenfassend haben wir den folgenden Klassifikationssatz, der erstmals 1893 von EH Moore bewiesen wurde :

Die Ordnung eines endlichen Körpers ist eine Primzahlpotenz. Zu jeder Primzahl q gibt es Körper der Ordnung q , und sie sind alle isomorph. In diesen Bereichen erfüllt jedes Element

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

und das Polynom X ^q − X Faktoren als

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

Daraus folgt, dass GF( p ⁿ ) genau dann einen Teilkörper enthält, der zu GF( p ^m ) isomorph ist, wenn m ein Teiler von n ist ; in diesem Fall ist dieses Unterfeld eindeutig. Tatsächlich teilt das Polynom X ^{p m} − X X ^{p n} − X genau dann, wenn m ein Teiler von n ist .

Explizite Konstruktion

Nicht-Prime-Felder

Gegeben eine Primzahl q = p ⁿ mit p prim und n > 1 kann der Körper GF( q ) explizit auf folgende Weise konstruiert werden. Man wählt zunächst ein irreduzibles Polynom P in GF( p )[ X ] vom Grad n (ein solches irreduzibles Polynom existiert immer). Dann ist der Quotientenring

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

des Polynomrings GF( p )[ X ] durch das von P erzeugte Ideal ist ein Körper der Ordnung q .

Genauer gesagt sind die Elemente von GF( q ) die Polynome über GF( p ), deren Grad streng kleiner als n ist . Die Addition und die Subtraktion sind die von Polynomen über GF( p ) . Das Produkt zweier Elemente ist der Rest der euklidischen Division durch P des Produkts in GF( p )[ X ] . Die multiplikative Inverse eines Nicht-Null-Elements kann mit dem erweiterten euklidischen Algorithmus berechnet werden; siehe Erweiterter euklidischer Algorithmus § Einfache algebraische Körpererweiterungen .

Außer bei der Konstruktion von GF(4) gibt es mehrere mögliche Auswahlmöglichkeiten für P , die isomorphe Ergebnisse liefern. Um die euklidische Division zu vereinfachen, wählt man für P üblicherweise Polynome der Form

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

die die benötigten euklidischen Divisionen sehr effizient machen. Für einige Felder, typischerweise in Merkmal 2 , existieren jedoch möglicherweise keine irreduziblen Polynome der Form X ⁿ + aX + b . In Merkmal 2 wird empfohlen , wenn das Polynom X ⁿ + X + 1 reduzierbar ist, X ⁿ + X ^k + 1 mit dem kleinstmöglichen k zu wählen , das das Polynom irreduzibel macht. Wenn alle diese Trinome reduzierbar sind, wählt man "Pentanome" X ⁿ + X ^a + X ^b + X ^c + 1 , da Polynome vom Grad größer als 1 mit einer geraden Anzahl von Termen in der Eigenschaft 2 niemals irreduzibel sind , mit 1 als Wurzel.

Eine mögliche Wahl für ein solches Polynom sind die Conway-Polynome . Sie gewährleisten eine gewisse Kompatibilität zwischen der Darstellung eines Feldes und den Darstellungen seiner Unterfelder.

In den nächsten Abschnitten werden wir zeigen, wie die oben skizzierte allgemeine Konstruktionsmethode für kleine endliche Körper funktioniert.

Feld mit vier Elementen

Der kleinste nicht-prime Körper ist der Körper mit vier Elementen, der allgemein als GF(4) bezeichnet wird oder aus den vier Elementen besteht, so dass und für jede andere Operation die Ergebnisse leicht aus dem Distributivgesetz abgeleitet werden können . Die vollständigen Betriebstabellen finden Sie unten. ${\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),}$

Dies lässt sich aus den Ergebnissen des vorangegangenen Abschnitts wie folgt ableiten.

Über GF(2) gibt es nur ein irreduzibles Polynom vom Grad2 :

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

Daher muss für GF(4) die Konstruktion des vorherigen Abschnitts dieses Polynom beinhalten, und

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

Lassen α bezeichnen eine Wurzel dieses Polynom in GF (4) . Dies impliziert, dass

α ² = 1 + α ,

und dass α und 1 + α die Elemente von GF(4) sind , die nicht in GF(2) sind . Daraus ergeben sich die Tabellen der Operationen in GF(4) , die wie folgt aussehen:

Addition x + y	Multiplikation x ⋅ y	Teilung x / y
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

Eine Tabelle für die Subtraktion wird nicht angegeben, da die Subtraktion wie bei jedem Feld des Merkmals 2 identisch mit der Addition ist. In der dritten Tabelle müssen für die Division von x durch y die Werte von x in der linken Spalte gelesen werden , und die Werte von y in der obersten Zeile. (Weil 0 ⋅ z = 0 für jedes z in jedem Ring die Division durch 0 undefiniert bleiben muss.)

Die Karte

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

ist der nicht-triviale Feldautomorphismus, Frobenius-Automorphismus genannt , der α in die zweite Wurzel 1 + α des oben erwähnten irreduziblen Polynoms sendet${\displaystyle X^{2}+X+1.}$

GF( p ² ) für eine ungerade Primzahl p

Um die obige allgemeine Konstruktion endlicher Körper im Fall von GF( p ² ) anzuwenden , muss man ein irreduzibles Polynom vom Grad 2 finden. Für p = 2 wurde dies im vorherigen Abschnitt getan. Wenn p eine ungerade Primzahl ist, gibt es immer irreduzible Polynome der Form X ² − r , mit r in GF( p ) .

Genauer gesagt ist das Polynom X ² − r über GF( p ) genau dann irreduzibel, wenn r ein quadratischer Nichtrest modulo p ist (dies ist fast die Definition eines quadratischen Nichtrests). Es gibt p − 1/2quadratische Nichtreste modulo p . Zum Beispiel ist 2 ein quadratischer Nicht-Rest für p = 3, 5, 11, 13, ... , und 3 ist ein quadratischer Nicht-Rest für p = 5, 7, 17, ... . Falls p ≡ 3 mod 4 , also p = 3, 7, 11, 19, ... , kann man −1 ≡ p − 1 als quadratischen Nichtrest wählen , was uns erlaubt, ein sehr einfaches irreduzibles Polynom X ² +1 .

Nachdem man einen quadratischen Nichtrest r gewählt hat , sei α eine symbolische Quadratwurzel von r , also ein Symbol mit der Eigenschaft α ² = r , ebenso wie die komplexe Zahl i eine symbolische Quadratwurzel von −1 ist . Dann sind die Elemente von GF( p ² ) alle linearen Ausdrücke

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

mit a und b in GF( p ) . Die Operationen auf GF( p ² ) sind wie folgt definiert (die Operationen zwischen Elementen von GF( p ), die durch lateinische Buchstaben dargestellt werden, sind die Operationen in GF( p ) ):

${\displaystyle {\begin{ausgerichtet}-(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{ausgerichtet}}}$

GF(8) und GF(27)

Das Polynom

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

ist irreduzibel über GF(2) und GF(3) , das heißt, es ist modulo 2 und 3 irreduzibel (um dies zu zeigen, genügt es zu zeigen, dass es weder in GF(2) noch in GF(3) eine Wurzel hat ). Daraus folgt, dass die Elemente von GF(8) und GF(27) durch Ausdrücke dargestellt werden können

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

wobei a , b , c Elemente von GF(2) bzw. GF(3 ) sind und ein Symbol ist, so dass ${\displaystyle\alpha}$

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

Die Addition, die additive Umkehrung und die Multiplikation an GF(8) und GF(27) können somit wie folgt definiert werden; In den folgenden Formeln sind die Operationen zwischen Elementen von GF(2) oder GF(3) , dargestellt durch lateinische Buchstaben, die Operationen in GF(2) bzw. GF(3) :

${\displaystyle {\begin{ausgerichtet}-(a+b\alpha+c\alpha^{2})&=-a+(-b)\alpha +(-c)\alpha^{2}\qquad {\ text{(für }}\mathrm {GF} (8),{\text{diese Operation ist die Identität)}}\\(a+b\alpha +c\alpha ^{2})+(d+e\ alpha +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{ausgerichtet}}}$

GF(16)

Das Polynom

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

ist über GF(2) irreduzibel, dh modulo 2 irreduzibel . Daraus folgt, dass die Elemente von GF(16) durch Ausdrücke dargestellt werden können

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

wobei a , b , c , d entweder 0 oder 1 sind (Elemente von GF(2) ) und α ein Symbol ist, so dass

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

(d. h., α ist als Wurzel des gegebenen irreduziblen Polynoms definiert). Da die Charakteristik des GF (2) ist 2 , jedes Element seine additive Inverse in GF (16) . Die Addition und Multiplikation von GF(16) kann wie folgt definiert werden; In den folgenden Formeln sind die Operationen zwischen Elementen von GF(2) , die durch lateinische Buchstaben dargestellt werden, die Operationen in GF(2) .

${\displaystyle {\begin{ausgerichtet}(a+b\alpha+c\alpha^{2}+d\alpha^{3})+(e+f\alpha +g\alpha^{2}+h\ alpha ^{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{ausgerichtet}}}$

Multiplikative Struktur

Die Menge der von Null verschiedenen Elemente in GF( q ) ist eine abelsche Gruppe unter der Multiplikation der Ordnung q – 1 . Nach dem Satz von Lagrange existiert ein Teiler k von q – 1, so dass x ^k = 1 für jedes von Null verschiedene x in GF( q ) gilt . Da die Gleichung x ^k = 1 in jedem Körper höchstens k Lösungen hat, ist q – 1 der kleinstmögliche Wert für k . Der Struktursatz endlicher abelscher Gruppen impliziert, dass diese multiplikative Gruppe zyklisch ist , d. h. alle von Null verschiedenen Elemente sind Potenzen eines einzelnen Elements. Zusammenfassend:

Die multiplikative Gruppe der Nicht-Null - Elemente in GF ( q ) ist zyklisch, und es existiert ein Element a , derart , dass die q - 1 nicht-Null - Elemente von GF ( q ) sind a , a ² , ..., a ^{q −2} , a ^{q −1} = 1 .

Ein solches Element a wird als primitives Element bezeichnet . Sofern nicht q = 2, 3 ist , ist das primitive Element nicht eindeutig. Die Anzahl der primitiven Elemente ist φ ( q − 1) wobei φ die Eulersche Totient-Funktion ist .

Das obige Ergebnis impliziert, dass x ^q = x für jedes x in GF( q ) ist . Der besondere Fall, in dem q eine Primzahl ist, ist der kleine Satz von Fermat .

Diskreter Logarithmus

Wenn a ein primitives Element in GF( q ) ist , dann gibt es für jedes von Null verschiedene Element x in F eine eindeutige ganze Zahl n mit 0 ≤ n ≤ q − 2 mit

x = ein ⁿ .

Diese ganze Zahl n wird als diskreter Logarithmus von x zur Basis a bezeichnet .

Während a ⁿ sehr schnell berechnet werden kann, zum Beispiel unter Verwendung einer Potenzierung durch Quadrieren , gibt es keinen bekannten effizienten Algorithmus zur Berechnung der inversen Operation, des diskreten Logarithmus. Dies wurde in verschiedenen kryptografischen Protokollen verwendet , siehe Diskreter Logarithmus für Details.

Wenn die von Null verschiedenen Elemente von GF( q ) durch ihre diskreten Logarithmen dargestellt werden, sind Multiplikation und Division einfach, da sie auf Addition und Subtraktion modulo q – 1 reduziert werden . Die Addition läuft jedoch auf die Berechnung des diskreten Logarithmus von a ^m + a ^{n hinaus} . Die Identität

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

erlaubt es, dieses Problem zu lösen, indem man die Tabelle der diskreten Logarithmen von a ⁿ + 1 , genannt Zech-Logarithmen , für n = 0, ..., q − 2 konstruiert (es ist zweckmäßig, den diskreten Logarithmus von Null als − ∞ ).

Die Logarithmen von Zech sind nützlich für große Berechnungen, wie die lineare Algebra über mittelgroße Körper, d als Ordnung des Feldes.

Wurzeln der Einheit

Jedes von Null verschiedene Element eines endlichen Körpers ist eine Einheitswurzel , da x ^{q −1} = 1 für jedes von Null verschiedene Element von GF( q ) ist .

Wenn n eine positive ganze Zahl ist, ist eine n- te primitive Einheitswurzel eine Lösung der Gleichung x ⁿ = 1 , die keine Lösung der Gleichung x ^m = 1 für irgendeine positive ganze Zahl m < n ist . Wenn a eine n- te primitive Einheitswurzel in einem Körper F ist , dann enthält F alle n Einheitswurzeln, die 1, a , a ² , ..., a ^{n −1 sind} .

Der Körper GF( q ) enthält genau dann eine n- te primitive Einheitswurzel, wenn n ein Teiler von q − 1 ist ; wenn n ein Teiler von ist q - 1 , dann ist die Anzahl von primitiven n - ten Einheitswurzeln in GF ( q ) ist , φ ( n ) ( Eulersche Totientenfunktion ). Die Anzahl der n- ten Einheitswurzeln in GF( q ) ist gcd( n , q − 1) .

In einem Körper der Charakteristik p ist jede ( np ) -te Einheitswurzel auch eine n- te Einheitswurzel. Daraus folgt, dass primitive ( np ) te Einheitswurzeln niemals in einem Körper der Charakteristik p existieren .

Auf der anderen Seite, wenn n ist coprime zu p , die Wurzeln des n - ten Kreisteilungspolynom unterscheiden sich in allen Bereichen der Charakteristik p , da dieses Polynom ein Teiler von ist X ⁿ - 1 , deren Diskriminante ist ungleich Null modulo p . Daraus folgt, dass das n- te zyklotomische Polynom über GF( p ) in verschiedene irreduzible Polynome zerlegt, die alle den gleichen Grad haben, sagen wir d , und dass GF( p ^d ) der kleinste Körper der Charakteristik p ist , der die n- ten primitiven Wurzeln von enthält Einheit. ${\displaystyle n^{n}}$

Beispiel: GF(64)

Das Feld GF(64) hat mehrere interessante Eigenschaften, die kleinere Felder nicht teilen: es hat zwei Unterfelder, so dass keines im anderen enthalten ist; nicht alle Generatoren (Elemente mit minimalem Polynom vom Grad 6 über GF(2) ) sind primitive Elemente; und die primitiven Elemente sind nicht alle unter der Galois-Gruppe konjugiert .

Die Ordnung dieses Feldes ist 2 ⁶ , und die Teiler von 6 sind 1, 2, 3, 6 , die Unterfelder von GF(64) sind GF(2) , GF(2 ² ) = GF(4) , GF(2 ³ ) = GF(8) und GF(64) selbst. Wie 2 und 3 sind coprime , der Schnittpunkt von GF (4) und GF (8) in GF (64) ist das Primfeld GF (2) .

Die Vereinigung von GF(4) und GF(8) hat also 10 Elemente. Die verbleibenden 54 Elemente von GF(64) erzeugen GF(64) in dem Sinne, dass kein anderes Unterfeld irgendeines davon enthält. Daraus folgt, dass sie Wurzeln irreduzibler Polynome vom Grad 6 über GF(2) sind . Dies impliziert, dass über GF(2) genau 9 =54/6irreduzible monische Polynome vom Grad 6 . Dies kann durch Faktorisieren von X ⁶⁴ − X über GF(2) verifiziert werden .

Die Elemente von GF(64) sind primitive n- te Einheitswurzeln für einige n, die 63 teilen . Da die 3. und 7. Einheitswurzel zu GF(4) bzw. GF(8) gehören , sind die 54 Generatoren primitive n- te Einheitswurzeln für einige n in {9, 21, 63} . Die Totient-Funktion von Euler zeigt, dass es 6 primitive 9. Einheitswurzeln, 12 primitive 21. Einheitswurzeln und 36 primitive 63. Einheitswurzeln gibt. Summiert man diese Zahlen, findet man wieder 54 Elemente.

Durch Faktorisieren der zyklotomischen Polynome über GF(2) findet man:

• Die sechs primitiven 9 ten Einheitswurzeln sind Wurzeln

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

und sind alle unter der Wirkung der Galois-Gruppe konjugiert.

• Die zwölf primitiven 21. Einheitswurzeln sind Wurzeln von

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

Sie bilden unter der Wirkung der Galois-Gruppe zwei Umlaufbahnen. Da die beiden Faktoren reziprok sind, gehören eine Wurzel und ihre (multiplikative) Inverse nicht zur gleichen Umlaufbahn.

• Die 36 primitiven Elemente von GF(64) sind die Wurzeln von

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

Sie teilen sich unter der Wirkung der Galois-Gruppe in 6 Umlaufbahnen von 6 Elementen auf.

Dies zeigt, dass die beste Wahl zum Konstruieren von GF(64) darin besteht, es als GF(2)[ X ] / ( X ⁶ + X + 1) zu definieren . Tatsächlich ist dieser Generator ein primitives Element, und dieses Polynom ist das irreduzible Polynom, das die einfachste euklidische Division erzeugt.

Frobenius-Automorphismus und Galois-Theorie

In diesem Abschnitt ist p eine Primzahl und q = p ⁿ eine Potenz von p .

In GF( q ) impliziert die Identität ( x + y ) ^p = x ^p + y ^p , dass die Abbildung

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

ist ein GF ( p ) - linear endomorphism und ein Feld automorphism von GF ( q ) , die jedes Element des Unterfeldes fixiert GF ( p ) . Es wird Frobenius-Automorphismus genannt , nach Ferdinand Georg Frobenius .

Bezeichnen wir mit φ ^k die Zusammensetzung von φ mit sich selbst k mal, so gilt

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

Im vorhergehenden Abschnitt wurde gezeigt, dass φ ⁿ die Identität ist. Für 0 < k < n ist der Automorphismus φ ^k nicht die Identität, da sonst das Polynom

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

hätte mehr als p ^k Wurzeln.

Es gibt keine anderen GF( p ) -Automorphismen von GF( q ) . Mit anderen Worten, GF( p ⁿ ) hat genau n GF( p ) -Automorphismen, die

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

In Bezug auf die Galois-Theorie bedeutet dies, dass GF( p ⁿ ) eine Galois-Erweiterung von GF( p ) ist , die eine zyklische Galois-Gruppe besitzt.

Die Tatsache, dass die Frobenius-Abbildung surjektiv ist, impliziert, dass jeder endliche Körper perfekt ist .

Polynomfaktorisierung

Wenn F ein finite - Feld, ein nicht-konstant ist normiertes Polynom mit Koeffizienten in F ist irreduziblen über F , wenn es nicht das Produkt von zwei nicht-konstanten monic Polynomen mit Koeffizienten in F .

Da jeder Polynomring über einem Körper ein eindeutiger Faktorisierungsbereich ist , kann jedes mononische Polynom über einem endlichen Körper auf einzigartige Weise (bis zur Ordnung der Faktoren) in ein Produkt irreduzibler monischer Polynome zerlegt werden.

Es gibt effiziente Algorithmen zum Testen der polynomialen Irreduzibilität und zum Faktorisieren von Polynomen über einen endlichen Körper. Sie sind ein wichtiger Schritt zum Faktorisieren von Polynomen über die ganzen Zahlen oder die rationalen Zahlen . Zumindest aus diesem Grund hat jedes Computeralgebrasystem Funktionen zum Faktorisieren von Polynomen über endliche Körper oder zumindest über endliche Primkörper.

Irreduzible Polynome gegebenen Grades

Das Polynom

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

Faktoren in lineare Faktoren über einen Körper der Ordnung q . Genauer gesagt ist dieses Polynom das Produkt aller monischen Polynome vom Grad eins über einen Körper der Ordnung q .

Dies impliziert , dass, wenn q = p ⁿ , dann X ^q - X ist das Produkt aller monic irreduzible Polynome über GF ( p ) , deren Grad dividieren n . In der Tat, wenn P ein irreduzibler Faktor über GF( p ) von X ^q − X ist , teilt sein Grad n , da sein Teilungsfeld in GF( p ⁿ ) enthalten ist . Umgekehrt, wenn P ein irreduzibles normiertes Polynom vorbei ist GF ( p ) vom Grad d Dividieren n , definiert sie eine Felderweiterung vom Grad d , die in enthalten ist GF ( p ⁿ ) , und alle Wurzeln von P gehört in GF ( p ⁿ ) und sind Wurzeln von X ^q − X ; also teilt P X ^q − X . Da X ^q − X keinen Vielfachfaktor hat, ist es somit das Produkt aller irreduziblen monischen Polynome, die es teilen.

Diese Eigenschaft wird verwendet, um das Produkt der irreduziblen Faktoren jedes Polynomgrades über GF( p ) zu berechnen ; siehe Faktorisierung mit eindeutigem Grad .

Anzahl der monischen irreduziblen Polynome gegebenen Grades über einem endlichen Körper

Die Anzahl N ( q , n ) der monischen irreduziblen Polynome vom Grad n über GF( q ) ist gegeben durch

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

wobei μ die Möbius-Funktion ist . Diese Formel ist fast eine direkte Folge der obigen Eigenschaft von X ^q − X .

Durch die obige Formel wird die Anzahl der nicht reduzierbaren (nicht notwendigerweise monic) Polynome vom Grad n über GF ( q ) ist , ( q - 1) N ( Q , n ) .

Eine (etwas einfachere) untere Schranke für N ( q , n ) ist

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

Man kann leicht ableiten, dass es für jedes q und jedes n mindestens ein irreduzibles Polynom vom Grad n über GF( q ) gibt . Diese untere Schranke ist scharf für q = n = 2 .

Anwendungen

In der Kryptographie ist die Schwierigkeit des diskreten Logarithmusproblems in endlichen Körpern oder in elliptischen Kurven die Grundlage mehrerer weit verbreiteter Protokolle, wie dem Diffie-Hellman- Protokoll. Im Jahr 2014 war beispielsweise eine sichere Internetverbindung zu Wikipedia mit dem elliptischen Diffie-Hellman-Protokoll ( ECDHE ) über ein großes endliches Feld verbunden. In der Codierungstheorie werden viele Codes als Unterräume von Vektorräumen über endlichen Körpern konstruiert .

Finite Felder werden von vielen Fehlerkorrekturcodes verwendet , z. B. von Reed-Solomon-Fehlerkorrekturcode oder BCH-Code . Der endliche Körper hat fast immer die Eigenschaft 2, da Computerdaten binär gespeichert werden. Beispielsweise kann ein Datenbyte als Element von interpretiert werden . Eine Ausnahme ist der PDF417- Barcode, der . Einige CPUs haben spezielle Anweisungen, die für endliche Felder der Eigenschaft 2 nützlich sein können, im Allgemeinen Variationen des traglosen Produkts . ${\displaystyle GF(2^{8})}$${\displaystyle GF(929)}$

In der Zahlentheorie sind endliche Körper weit verbreitet , da viele Probleme über die ganzen Zahlen gelöst werden können, indem man sie modulo einer oder mehrerer Primzahlen reduziert . Zum Beispiel gehen die schnellsten bekannten Algorithmen für polynomielle Faktorisierung und lineare Algebra über den Körper der rationalen Zahlen durch Reduktion modulo eine oder mehrere Primzahlen und dann Rekonstruktion der Lösung unter Verwendung des chinesischen Restsatzes , Hensel-Lifting oder des LLL-Algorithmus vor .

Ähnlich können viele theoretische Probleme der Zahlentheorie gelöst werden, indem man ihre Reduktionen modulo einiger oder aller Primzahlen betrachtet. Siehe zum Beispiel Hasse-Prinzip . Viele neuere Entwicklungen der algebraischen Geometrie wurden durch die Notwendigkeit motiviert, die Leistungsfähigkeit dieser modularen Methoden zu erweitern. Wiles' Beweis des letzten Satzes von Fermat ist ein Beispiel für ein tiefgreifendes Ergebnis mit vielen mathematischen Werkzeugen, einschließlich endlicher Körper.

Die Weil-Vermutungen betreffen die Anzahl der Punkte auf algebraischen Varietäten über endlichen Körpern und die Theorie hat viele Anwendungen, einschließlich Exponential- und Charaktersummenschätzungen .

Finite Felder haben in der Kombinatorik eine weit verbreitete Anwendung , zwei bekannte Beispiele sind die Definition von Paley-Graphen und die damit verbundene Konstruktion von Hadamard-Matrizen . In der arithmetischen Kombinatorik werden endliche Körper und endliche Körpermodelle ausgiebig verwendet, wie zum Beispiel im Satz von Szemerédi über arithmetische Folgen.

Erweiterungen

Algebraischer Verschluss

Ein endlicher Körper F ist nicht algebraisch abgeschlossen: das Polynom

${\displaystyle f(T)=1+\prod_{\alpha\in F}(T-\alpha),}$

hat keine Wurzeln in F , da f  ( α ) = 1 für alle α in F ist .

Fixiere einen algebraischen Abschluss von . Die Abbildung , die jedes x zu x ^q sendet , wird Frobenius-Automorphismus q- ter Potenz genannt . Das Teilfeld der durch die feste n - ten Iteration der der Satz von Nullstellen des Polynoms x ^{q n} - x , die verschiedene Wurzeln hat , da ihr Derivat in ist -1 , die nie null ist. Daher hat dieses Unterfeld q ⁿ Elemente, ist also die eindeutige Kopie von in . Jede endliche Erweiterung von in ist dies für ein n , also ${\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}}.}$

Die absolute Galois-Gruppe von ist die profinite Gruppe${\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}}}.}$

Wie jede unendliche Galois-Gruppe kann sie mit der Krull-Topologie ausgestattet sein , und dann sind die eben angegebenen Isomorphismen Isomorphismen topologischer Gruppen . Das Bild von in der Gruppe ist der Generator 1 , entspricht also . Daraus folgt, dass das unendliche Ordnung hat und eine dichte Untergruppe von erzeugt , nicht die ganze Gruppe, weil das Element unendliche Ordnung hat und die dichte Untergruppe erzeugt. Man sagt, das ist ein topologischer Generator von . ${\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})}$

Quasi-algebraischer Verschluss

Obwohl endliche Körper nicht algebraisch abgeschlossen sind, sind sie quasi-algebraisch abgeschlossen , was bedeutet, dass jedes homogene Polynom über einem endlichen Körper eine nicht-triviale Nullstelle hat, deren Komponenten im Körper liegen, wenn die Anzahl seiner Variablen größer als sein Grad ist. Dies war eine Vermutung von Artin und Dickson , die von Chevalley bewiesen wurde (siehe Chevalley-Warning-Theorem ).

Wedderburns kleiner Satz

Ein Teilungsring ist eine Verallgemeinerung des Feldes. Teilungsringe werden nicht als kommutativ angenommen. Es gibt keine nichtkommutativen endlichen Teilungsringe: Der kleine Satz von Wedderburn besagt, dass alle endlichen Teilungsringe kommutativ sind, also endliche Körper. Das Ergebnis gilt auch dann, wenn wir die Assoziativität lockern und alternative Ringe nach dem Artin-Zorn-Theorem betrachten .

Siehe auch

• Quasi-endliches Feld
• Feld mit einem Element
• Finite-Feld-Arithmetik
• Endlicher Ring
• Endliche Gruppe
• Elementare abelsche Gruppe
• Hamming-Raum

Anmerkungen

Verweise

Externe Links

• Finite Felder bei der Wolfram-Forschung.