Goppa-code

Er zijn verschillende definities te geven voor een goppa-code. Hier wordt toegewerkt naar een polynomiale definitie. Voordat we dat kunnen doen zijn er enkele parameters nodig. De volgende gegevens zijn gebruikelijk voor een goppa-code:

• Kies ${\displaystyle n=2^{m}}$  met ${\displaystyle m\in \{10,11,12\}}$ .
• De code is gedefinieerd over het lichaam ${\displaystyle \mathbb {GF} (n)}$ . Noem de rij afzonderlijke elementen uit dat lichaam, ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$  lexicografisch geordend.
• Voor het aantal fouten ${\displaystyle t}$  die gecorrigeerd kunnen worden door de code, kiezen we ${\displaystyle 2\leq t\leq {\frac {2^{m}-1}{m}}}$ . Voor ${\displaystyle m=11}$  is bijvoorbeeld ${\displaystyle t=32,t=70}$  of ${\displaystyle t=100}$ .
• Zoek een irreducibele monische polynoom ${\displaystyle g\in \mathbb {GF} (2^{m})[x]}$  van graad ${\displaystyle t}$ .
• Laat ${\displaystyle h=\prod _{i}(x-a_{i})\in \mathbb {GF} (n)[x]}$ .

In dit geval geldt dat ${\displaystyle h=x^{n}-x\in \mathbb {GF} (2^{m})[x]}$ .

Een definitie van de goppa-code ${\displaystyle \Gamma }$ , is nu

${\displaystyle {\Gamma }={\Gamma }(a_{1},a_{2},\ldots ,a_{n},g)=\{c\in \mathbb {GF} (2^{m}):\sum _{i}c_{i}{\frac {h}{x-a_{i}}}\mod g=0\}}$ 

De polynomen ${\displaystyle {\frac {h}{x-a_{1}}}{\bmod {g}},{\frac {h}{x-a_{2}}}{\bmod {g}},\ldots ,{\frac {h}{x-a_{n}}}{\bmod {g}}}$ , kunnen gezien worden als vectoren over ${\displaystyle \mathbb {GF} (2)}$ .

Ze vormen een pariteitscontrole-matrix voor de code ${\displaystyle \Gamma }$ .

In 1975 heeft Patterson een algoritme ontwikkeld om in polynomiale tijd ${\displaystyle t}$  fouten te kunnen corrigeren uit de goppa-code.

Voordat het algoritme weergegeven kan worden, is de definitie nodig van de norm van een polynoom.

Voor een polynoom ${\displaystyle \phi \in \mathbb {GF} (2^{m})[x]}$  geldt dat de norm ${\displaystyle |\phi |=2^{\deg(\phi )}}$ , met ${\displaystyle \deg(\phi )}$  de graad van ${\displaystyle \phi }$ .

Bij rationale functies geldt ${\displaystyle |{\frac {\phi }{\psi }}|={\frac {|\phi |}{|\psi |}}}$ . Bijvoorbeeld ${\displaystyle |{\frac {x^{3}}{x^{5}-x}}|={\frac {|x^{3}|}{|x^{5}-x|}}={\frac {2^{3}}{2^{5}}}=2^{-2}}$ .

Het doel is om maximaal ${\displaystyle t}$  fouten te verbeteren uit eengoppa-code ${\displaystyle \Gamma }$ . We starten met een woord ${\displaystyle w\in \mathbb {GF} ^{n}(2)}$ , met maximaal ${\displaystyle t}$  fouten. Dat betekent dat er een coodewoord ${\displaystyle c\approx w}$  is zodat er in het codewoord hoogstens ${\displaystyle t}$  maal een 1 met een 0 verwisseld is, of andersom.

• Bereken ${\displaystyle {\sum _{i}{\frac {w_{i}}{x-a_{i}}}}}$  over het lichaam ${\displaystyle \mathbb {GF} (2^{m})[x]/(g)}$ . Als deze som nul is in het lichaam, dan zijn er blijkbaar geen fouten in de code. Het algoritme geeft dan output ${\displaystyle w}$ .
• Bereken de wortel van ${\displaystyle {\frac {1}{\sum _{i}{\frac {w_{i}}{x-a_{i}}}}}-x}$  over het lichaam ${\displaystyle \mathbb {GF} (2^{m})[x]/(g)}$ .
• Noem deze berekende wortel ${\displaystyle s}$  en bekijk deze in het lichaam ${\displaystyle s\in \mathbb {GF} (2^{m})[x]}$ . De graad van ${\displaystyle s}$  is kleiner dan ${\displaystyle t}$ .
• De vectoren ${\displaystyle (s,1)}$  en ${\displaystyle (g,0)}$  genereren een rooster ${\displaystyle L\subseteq \mathbb {GF} (2^{m})[x]^{2}}$ .

De norm ${\displaystyle |(\alpha ,\beta )|}$  van een vector ${\displaystyle (\alpha ,\beta )\in \mathbb {GF} (2^{m})[x]^{2}}$  is per definitie gelijk aan de norm van de polynoom ${\displaystyle \alpha ^{2}+x\beta ^{2}}$ .

Zo is de lengte van de vector ${\displaystyle (g,0)}$  gelijk aan ${\displaystyle |(g,0)|=|g^{2}|=2^{2t}}$ .

• Vind met behulp van basisreductie een basis ${\displaystyle (\alpha _{0},\beta _{0})}$  van minimale lengte. Deze zal kleiner of gelijk zijn aan ${\displaystyle 2^{t}}$ .
• Bereken ${\displaystyle \epsilon =\alpha _{0}^{2}+x\beta _{0}^{2}}$ 
• Deel door de coëfficiënt van de hoogste macht van x, zodat ${\displaystyle \epsilon }$  monisch wordt.
• Ontbindt ${\displaystyle \epsilon }$  in lineaire factoren van de vorm ${\displaystyle (x-a_{i})}$ . Dit zullen ${\displaystyle t}$  factoren zijn.
• Output ${\displaystyle c}$ , is de gecorrigeerd code ${\displaystyle w}$ , met een correctie op de plaatsen ${\displaystyle i}$ , waar ${\displaystyle \epsilon (a_{i})=0}$ .

Voor een uitgebreid voorbeeld van dit algoritme wordt verwezen naar het artikel van Bernstein.^[1]