Endliche Felder
Original: http://www.efgh.com/math/algebra/finitefields.htm von Philip J. Erdelsky
1. Grundlegende Eigenschaften
Ein endliches Feld (auch Galoisfeld genannt) ist ein Feld mit einer endlichen Anzahl von Elementen. Endliche Felder haben viele Anwendungen, insbesondere in der Kryptographie und Kommunikation.
Endliche Felder sind durch den folgenden Satz gekennzeichnet.
Satz 1.1 Für jede Primzahl p und jede positive ganze Zahl n gibt es ein und nur ein Feld mit p n Elementen, es ist das minimale Teilungsfeld von x p n – x über Zp, und das sind die einzigen endlichen Felder.
Beweis. Wir beweisen zunächst, dass jedes endliche Feld p n Elemente aufweist.
Natürlich muss ein endliches Feld eine endliche Charakteristik p aufweisen. Die Feldelemente {0, 1, 2, …., p-1} sind ein Teilfeld G isomorph zu Zp, wobei 2 als 1+1 definiert ist, 3 als 2+1 definiert ist, etc.
Das Feld selbst bildet einen Vektorraum über G, der offensichtlich eine endliche Dimension n hat. Da jedes Feldelement eindeutig als lineare Kombination von n Basisvektoren ausgedrückt werden kann, beträgt die Gesamtzahl der Feldelemente p n.
Wir beweisen nun, dass es ein endliches Feld mit p n Elementen gibt.
Beginnen Sie mit dem Feld Zp und lassen Sie N = p n. Betrachten Sie das Polynom p(x) = x N – x. Es ist relativ primär zu seiner formalen Ableitung -1, so dass es unterschiedliche Wurzeln in seinem Splitting-Feld hat.
Das Teilungsfeld hat, wie das Basisfeld, das Merkmal p. Wenn a und b Feldelemente sind, dann durch den Binomialsatz
(a+b) p = a p + p p a p-1b + (p(p-1)/2!) a p-2b 2 + ….. + b p.
Da jeder Binomialkoeffizient außer dem ersten und letzten durch p teilbar ist, reduziert sich dieser auf
(a+b) p = a p + b p.
Dann
(a+b) p 2 = ((a+b) p) p = (a p + b p) p = a p 2 + b p 2.
Die wiederholte Anwendung dieses Ergebnisses führt zu folgenden Ergebnissen
(a+b) N = a N + b N.
Wenn a und b Wurzeln von p(x) sind, dann ist a N = a und b N = b. Dann wird das obige Ergebnis zu
(a+b) N = a + b.
Daher ist die Summe der beiden Wurzeln von p(x) auch eine Wurzel von p(x).
Ebenso kann gezeigt werden, dass das Produkt aus zwei Wurzeln von p(x) auch eine Wurzel von p(x) ist.
Somit bilden die N-Wurzeln von p(x) das gesamte Spaltfeld, das bis zur Isomorphie einzigartig ist. ?
Das Galois-Feld mit p n-Elementen wird oft als GF(p n) geschrieben.
2. Multiplikative Gruppe ist zyklisch
Die ungleich Null Elemente eines Feldes bilden eine kommutative Gruppe unter Multiplikation. Für endliche Felder hat diese Gruppe eine besonders einfache Struktur.
Zuerst brauchen wir eine grundlegende Eigenschaft von Polynomen.
Kurztitel 2.1 Wenn m n teilt, dann teilt x m – 1 x n – 1.
Beweis. Lassen Sie d = n/m. Dann n = dm und die erforderliche Faktorisierung ist wie folgt:
x dm – 1 = (x m – 1) (x (d-1)m + x (d-2)m + ….) + x m + 1).
Satz 2.2 Die Gruppe der ungleich Null Elemente eines endlichen Feldes unter Multiplikation ist zyklisch.
Beweis. N soll die Anzahl der Elemente im Feld sein. Dann sind die Elemente ungleich Null die Wurzeln von x N-1 – 1, die alle unterschiedlich sind.
Wenn N = 2 ist, ist das Ergebnis offensichtlich.
In anderen Fällen soll q ein Primfaktor von N-1 sein und m die Anzahl der Male, die er bei der Primfaktorisierung von N-1 auftritt. Zur Vereinfachung in der Notation lassen Sie M = q m.
Durch die Lemma teilt x M/q – 1 x M – 1 und x M – 1 x N-1 – 1. Auch diese Polynome haben unterschiedliche Wurzeln. Es gibt also Wurzeln von x N-1 – 1, die auch Wurzeln von x M – 1 sind, aber nicht Wurzeln von x M/q – 1, die die Ordnung M haben.
Nehmen Sie nun für jeden Primfaktor von N-1 eine solche Wurzel. Durch Theorem 4.1 von Gruppen hat ihr Produkt die Ordnung N-1. Dies zeigt, dass die Gruppe zyklisch ist. ?
Ein Element g von GF(N) mit der Ordnung N-1 in der multiplikativen Gruppe wird als Generator oder primitives Element des Feldes bezeichnet.
Satz 2.3. Jeder Generator von GF(p n) ist die Wurzel eines einzigartigen monischen irreduziblen Polynoms von Grad n mit Koeffizienten in GF(p), und die anderen Wurzeln dieses Polynoms sind ebenfalls Generatoren.
Beweis. Lassen Sie g einen beliebigen Generator von GF(p n) sein. Die Leistungen 1, g, g, g 2, …. des Generators sind Vektoren in einem n-dimensionalen Vektorraum über GF(p). Daher muss 1, g, g, g 2, …. g n linear abhängig sein, d.h. g ist eine Wurzel aus einem Polynom von nicht mehr als n über GF(p).
Sei r(x) ein monisches Polynom niedrigsten Grades über GF(p), das g als Wurzel hat. Der Grad sei m. Dann kann die Identität r(g) = 0 verwendet werden, um jede beliebige Leistung von g als Linearkombination von 1, g, g, g 2, g 2, …. g m-1 mit Koeffizienten in GF(p) auszudrücken. Da g p n – 1 verschiedene Potenzen hat, zeigt ein einfaches Zählargument, dass m=n.
Das Polynom r(x) muss über GF(p) irreduzibel sein, da sonst g eine Wurzel aus mindestens einem seiner Faktoren wäre.
Betrachten wir nun zwei solcher Polynome. Sie haben einen gemeinsamen Faktor x – g, so dass sie nicht relativ primär gegenüber GF(p) oder GF(p n) sein können. Dies kann nur geschehen, wenn sie identisch sind.
Lassen Sie nun N = p n und den Faktor x N-1 – 1, dessen Wurzeln alle ungleich Null Elemente von GF(p n) sind, in seine monischen Primfaktoren über GF(p) einfließen. Da g eine Wurzel dieses Polynoms ist, muss es eine Wurzel aus einem der Faktoren sein, die mit dem Polynom r(x) identisch sein muss. Daher sind die anderen Wurzeln von r(x) auch Elemente von GF(p n).
Nun soll q ein beliebiger Teiler von N-1 sein, der kleiner als N-1 ist. Dann teilt x q – 1 x N-1 – 1, so dass, wenn x N-1 – 1 in seinen monischen Primfaktoren über GF(p) berücksichtigt wird, der Primfaktor r(x) x q – 1 teilen oder relativ primär dazu sein muss. Erstere ist unmöglich, da g keine Wurzel aus x q – 1 ist. Daher kann keine andere Wurzel aus r(x) eine Wurzel aus x q – 1 sein, und alle müssen Generatoren aus GF(p n) sein. ?
3. Fehlererkennung und -behebung
Es gibt eine interessante Anwendung der Finite-Feldtheorie auf die Kommunikation. Normalerweise ist das Feld von Merkmal 2, da die Arithmetik auf GF(2) mit digitaler Hardware leicht zu realisieren ist.
N = 2 n Angenommen, eine Nachricht ist irgendwie in einem Bitstrom kodiert, d.h. als Elemente von GF(2):
0, 0, 1, 1, 0, 1, 0, 0, 0, …, 1, 0, 0
Irgendwo auf dem Weg dorthin kann ein einziges Bit geändert werden:
0, 0, 1, 1, 0, 0, 0, 0, 0, …, 1, 0, 0
Wir wollen zusätzliche Bits senden, berechnet, um festzustellen, ob ein Bit geändert wurde (Fehlererkennung) und wenn ja, welches Bit (Fehlerkorrektur). Das geänderte Bit kann eines der zusätzlichen Bits sein.
Wir können dies durch die Verwendung des endlichen Feldes GF(N), wobei N = 2 n ist, und der modularen Arithmetik auf dem Polynomring GF(2)[x] erreichen. Beachten Sie, dass in einem Feld des Merkmals 2 kein Unterschied zwischen Addition und Subtraktion besteht.
Kodieren Sie die Nachricht in N-n-1 Bits und stellen Sie sich vor, dass sie die Koeffizienten eines Polynoms über GF(2) ist:
m(x) = b1 x N-2 + b2 x N-3 + ….. + bN-n-1 x n
Nun soll g ein Generator von GF(N) sein, der eine Wurzel des monischen, irreduziblen Polynoms r(x) über GF(2) ist.
Teilen Sie nun m(x) durch r(x), um den Rest s(x) zu erhalten.
Übertragen der Koeffizienten der Summe m(x) + s(x). Beachten Sie, dass s(x) bequem in den unbesetzten Bereich von m(x) passt.
Wenn die Koeffizienten von m(x) + s(x) empfangen werden, dividieren Sie das entsprechende Polynom durch r(x) und erhalten Sie den Rest t(x).
Wenn die Koeffizienten genau empfangen wurden, ist der Rest Null.
Wenn ein einzelnes Bit (der Koeffizient von x k) geändert wurde, dann ist das Polynom m(x) + s(x) + + x k. Der Rest ist ungleich Null, da r(x) und x k relativ prim sind.
Wir können das geänderte Bit identifizieren, wenn verschiedene Bitwechsel unterschiedliche Reste ergeben. Die Differenz der durch Fehler in x j und x k erzeugten Reste ist der Rest, der durch Division von x j + x k durch r(x) entsteht. Dies ist auch ungleich Null, denn x j + x k ist auch relativ primär zu r(x).
In einer tatsächlichen Implementierung können kleinere Änderungen vorgenommen werden, um die Effizienz der Berechnung zu verbessern.
4. Sequenz der Schieberegister
In vielen Anwendungen müssen wir einen Strom von mehr oder weniger zufälligen Zahlen erstellen. Eine Möglichkeit, dies zu tun, ist mit einer Schieberegisterfolge.
Die Sequenz x0, x1, x2, x2, …. wird erzeugt, indem die ersten n Werte angegeben und dann eine lineare Wiederholungsformel verwendet wird, um nachfolgende Werte zu berechnen:
xk+n = cn-1xk+n-1 + cn-2xk+n-2 + ….. + c0xk, k = 0, 1, 2, 2, 3, ……
Normalerweise werden die Sequenzwerte und die Koeffizienten aus dem Feld GF(2) übernommen, aber unsere Behandlung wird genauso gut gelten, wenn sie aus GF(p) für jede Primzahl p übernommen werden.
Die Berechnungen werden in der Regel durchgeführt, indem zuerst die Anfangswerte in ein n-Wert Register geladen werden:
xn-1, xn-2, xn-3, …., x0.
Bei jedem Schritt werden die Werte nach rechts verschoben. Der Wert am rechten Ende wird verworfen, und der neue Wert für das linke Ende wird mit der Wiederholungsformel berechnet. Wenn alle Werte Einzelbits von GF(2) sind, sind die Berechnungen recht einfach.
Da es nur begrenzt viele Kombinationen von Werten gibt, wird sich das Gerät irgendwann wiederholen. Wir wollen die Anzahl der Schritte maximieren, bevor dies geschieht. Die Gesamtzahl der Kombinationen ist p n, aber eine von ihnen, bei der alle Werte Null sind, ist verboten, da die Wiederholungsformel sie nicht ändern würde.
Wenn der Koeffizient c0 ungleich Null ist, wie es in praktisch allen Anwendungen der Fall ist, dann kann die Sequenz auch rückwärts laufen. Dies bedeutet, dass er bei der Wiederholung zunächst zu den Startwerten zurückkehrt.
Wir können die maximale Anzahl p n-1 von Schritten zwischen Wiederholungen erhalten, wenn wir die Koeffizienten so wählen, dass die Wurzeln des Polynoms
z n – cn-1z n-1 – cn-2z n-2 – ….. – c1z – c0
sind Generatoren des Feldes GF(p n). Lasst sie durch g1, g2, g2, …., gn gekennzeichnet sein. Beachten Sie, dass c0 ≠ 0, weil keiner der Generatoren Null ist.
Die Startwerte spielen keine Rolle, solange sie nicht alle Nullen sind.
Um dies zu beweisen, stellen wir zunächst fest, dass die Leistungen jedes Generators der Wiederholungsformel gehorchen. Angenommen, x0 = 1, x1 = gr, x2 = gr 2, x3 = gr 3, etc. Dann
gr n – cn-1gr n-1 – cn-2gr n-2 – ….. – c1gr – c0 = 0,
gr n = cn-1gr n-1 + cn-2gr n-2 + ….. + c1gr + c0,
gr k+n = cn-1gr k+n-1 + cn-2gr k+n-2 + ….. + c1gr k+1 + c0gr k.
Eine solche Sequenz würde jedoch nicht erzeugt, da die Anfangswerte gr n-1, gr n-1, gr n-1, …., gr, gr, 1 nicht alle im Basisfeld GF(p) liegen würden.
Angenommen, wir nehmen eine lineare Kombination von Leistungen von Generatoren:
xk = d1g1 k + d2g2 k + ….. + dngn k.
Die Wiederholungsformel ist noch erfüllt. Wir müssen die Koeffizienten d1, d2, …., dn so wählen, dass die Ausgangsbedingungen erfüllt sind:
d1 + d2 + d2 + ….. + dn = x0,
d1g1 + d2g2 + ….. + dngn = x1,
d1g1 2 + d2g2 2 + ….. + dngn 2 = x2,
***
d1g1 n-1 + d2g2 n-1 + ….. + dngn n-1 = xn-1.
Die Matrix dieses Systems ist die Transponierung einer quadratischen Vandermonde-Matrix, und sie ist nicht singulär, da g1, g2, …., gn alle unterschiedlich sind. Daher existiert eine einzigartige Lösung, und mindestens einer der Koeffizienten d1, d2, …., dn ist ungleich Null.
Die Sequenz beginnt sich zu wiederholen, wenn sie zu ihrer ursprünglichen Konfiguration zurückkehrt, d.h. für den kleinsten positiven Wert von k, für den:
d1g1 k + d2g2 k + ….. dngn k = d1 + d2 + d2 + ….. + dn,
d1g1 k+1 + d2g2 k+1 + ….. + dngn k+1 = d1g1 + d2g2 + ….. + dngn,
d1g1 k+2 + d2g2 k+2 + ….. + dngn k+2 = d1g1 2 + d2g2 2 + ….. + dngn 2,
***
d1g1 k+n-1 + d2g2 k+n-1 + ….. dngn k+n-1 = d1g1 n-1 + d2g2 n-1 + d2g2 n-1 + ….. + dngn n-1.
Wenn alle Begriffe auf die linke Seite verschoben und kombiniert werden, wird dies zu: