WikiDer > Goppa-Codes

Goppa Codes

EIN binärGoppa-Code, allgemein nur als Goppa-Code bezeichnet, ist ein fehlerkorrigierender Code. Der Code ist nach dem russischen Mathematiker benannt Velerii Denisovich Goppa. Im McEliece-Kryptographie Beispielsweise werden binäre Goppa-Codes verwendet. Ein binärer Goppa-Code unterscheidet sich von a Algebraischer Goppa-Code.

Bedingungen

Es gibt mehrere Definitionen für einen Goppa-Code. Hier arbeiten wir an einer Polynomdefinition. Bevor wir das tun können, benötigen wir einige Parameter. Die folgenden Daten sind für einen Goppa-Code üblich:

Wählen ${Anzeigestil n=2^{m}}$ mit ${Anzeigestil minus {10,11,12}}$ .
Der Code wird über die . definiert Körper ${displaystyle mathbb {F} _{2^{m}}=mathbb {F} _{n}}$ . Benennen Sie die Reihe der einzelnen Elemente aus diesem Körper, ${displaystyle a_{1},a_{2},dots ,a_{n}}$ lexikographisch geordnet.
Für die Anzahl der Fehler, die durch den Code korrigiert werden können, t, wir wählen ${displaystyle 2leq tleq {frac {2^{m}-1}{m}}}$ . Vor dem ${displaystyle m=11}$ sind zum Beispiel t = 32, t = 70, oder t = 100.
Nimm jetzt ${displaystyle gin mathbb {F} _{2^{m}}[x]}$ wie ein irreduzibel monisch Polynom von Gradt.
spät ${displaystyle h=Pi _{i}(x-a_{i})in mathbb {F} _{n}[x]}$ .

In diesem Fall gilt, dass ${displaystyle h=x^{n}-xin mathbb {F} _{2^{m}}[x]}$ .

Definition

Eine Definition des Goppa-Codes ${Anzeigestil Gamma }$ , ist jetzt

{displaystyle {Gamma}={Gamma}(a_{1},a_{2},...,a_{n},g)={cin mathbb {F} _{2}^{n}:sum _{ i}c_{i}{frac {h}{x-a_{i}}}mod g=0}.}

Die Polynome ${displaystyle {frac {h}{x-a_{1}}}mod g,{frac {h}{x-a_{2}}}mod g,...,{frac {h}{x-a_{ n}}}mod g}$ , kann als Vektoren über angesehen werden ${displaystyle mathbb {F}_{2}}$ .

Sie bilden a Paritätsprüfmatrix für den Code ${Anzeigestil Gamma }$ .

Pattersons Algorithmus

1975 entwickelte Patterson einen Algorithmus, um Polynomzeitt Fehler aus dem Goppa-Code korrigieren.

Bevor der Algorithmus dargestellt werden kann, muss die Norm eines Polynoms definiert werden.

Norm eines Polynoms

Für ein Polynom ${displaystyle phi in mathbb {F} _{2^{m}}[x]}$ gilt, dass die Norm ${Anzeigestil |phi |=2^{deg(phi)}}$ , mit ${displaystyle deg(phi)}$ das Grad von ${Anzeigestil phi}$ .

Für rationale Funktionen gilt: ${displaystyle |{frac {phi }{psi }}|={frac {|phi |}{|psi |}}}$ . Beispielsweise ${displaystyle |{frac {x^{3}}{x^{5}-x}}|={frac {|x^{3}|}{|x^{5}-x|}}={frac {2^{3}}{2^{5}}}=2^{-2}}$ .

Algorithmus

Das Ziel ist zu maximieren t Fehler aus einem Goppa-Code korrigieren ${Anzeigestil Gamma }$ . Wir beginnen mit einem Wort ${displaystyle win mathbb {F} _{2}^{n}}$ , mit maximal t Fehler. Das heißt, es gibt ein Codewort ${Displaystil cca. w}$ ist so, dass im Codewort höchstens t mal eine 1 mit einer 0 vertauscht oder umgekehrt.

Berechnung ${displaystyle {sum _{i}{frac {w_{i}}{x-a_{i}}}}}$ über den Körper ${displaystyle mathbb {F} _{2^{m}}[x]/g}$ . Wenn diese Summe im Hauptteil null ist, gibt es anscheinend keine Fehler im Code. Der Algorithmus liefert dann die Ausgabe w.
Berechnen Sie die Quadratwurzel von ${displaystyle {frac {1}{sum _{i}{frac {w_{i}}{x-a_{i}}}}}-x}$ über den Körper ${displaystyle mathbb {F} _{2^{m}}[x]/g}$ .
Nennen Sie diese berechnete Wurzel so und beobachte es im Körper ${displaystyle sin mathbb {F} _{2^{m}}[x]}$ . Der Grad der so ist kleiner als t.
Die Vektoren ${Anzeigestil(e,1)}$ und ${displaystyle(g,0)}$ generieren a generate Zeitplan ${displaystyle Lsubseteq mathbb {F} _{2^{m}}[x]^{2}}$ .

Die Norm

{Anzeigestil |(alpha , eta )|}

eines Vektors

{displaystyle (alpha , eta )in mathbb {F} _{2^{m}}[x]^{2}}

ist per Definition gleich der Norm des Polynoms

{displaystyle alpha ^{2} x eta ^{2}}

.

Damit ist die Länge des Vektors

{displaystyle(g,0)}

gleicht

{Anzeigestil |(g,0)|=|g^{2}|=2^{2t}}

.

Finden mit Grundreduktion eine Basis ${displaystyle (alpha _{0}, eta _{0})}$ von Mindestlänge. Es ist kleiner oder gleich ${Displaystil 2^{t}}$ .
Berechnung ${displaystyle epsilon =alpha _{0}^{2} x eta _{0}^{2}}$
Dividiere durch den Koeffizienten der höchsten Potenz von x, so dass ${Anzeigestil Epsilon}$ wird monisch.
löst sich ${Anzeigestil Epsilon}$ in linearen Faktoren der Form ${displaystyle(x-a_{i})}$ . Dieser Wille t Faktoren.
Ausgabe c, ist der korrigierte Code w, mit einer Korrektur an den Stellen ich, wahr ${Anzeigestil Epsilon (a_{i})=0}$ .