Een binaire goppa-code, doorgaans alleen goppa-code genoemd, is een foutcorrigerende code. De code is genoemd naar de Russische wiskundige Velerii Denisovich Goppa. In McEliece-cryptografie wordt bijvoorbeeld gebruikgemaakt van binaire goppa-codes. Een binaire goppa-code is niet hetzelfde als een algebraïsche 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
met
.
- De code is gedefinieerd over het lichaam
. Noem de rij afzonderlijke elementen uit dat lichaam,
lexicografisch geordend.
- Voor het aantal fouten
die gecorrigeerd kunnen worden door de code, kiezen we
. Voor
is bijvoorbeeld
of
.
- Zoek een irreducibele monische polynoom
van graad
.
- Laat
.
In dit geval geldt dat
.
Een definitie van de goppa-code
, 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\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ed4e7624362ae73dc23fd2f18e798dcc4d83084)
De polynomen
, kunnen gezien worden als vectoren over
.
Ze vormen een pariteitscontrole-matrix voor de code
.
In 1975 heeft Patterson een algoritme ontwikkeld om in polynomiale tijd
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
geldt dat de norm
, met
de graad van
.
Bij rationale functies geldt
. Bijvoorbeeld
.
Het doel is om maximaal
fouten te verbeteren uit eengoppa-code
. We starten met een woord
, met maximaal
fouten. Dat betekent dat er een coodewoord
is zodat er in het codewoord hoogstens
maal een 1 met een 0 verwisseld is, of andersom.
- Bereken
over het lichaam
. Als deze som nul is in het lichaam, dan zijn er blijkbaar geen fouten in de code. Het algoritme geeft dan output
.
- Bereken de wortel van
over het lichaam
.
- Noem deze berekende wortel
en bekijk deze in het lichaam
. De graad van
is kleiner dan
.
- De vectoren
en
genereren een rooster
.
- De norm
van een vector
is per definitie gelijk aan de norm van de polynoom
.
- Zo is de lengte van de vector
gelijk aan
.
- Vind met behulp van basisreductie een basis
van minimale lengte. Deze zal kleiner of gelijk zijn aan
.
- Bereken
![{\displaystyle \epsilon =\alpha _{0}^{2}+x\beta _{0}^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f682283efaf7267bde59ac42d2cf5fa031e8848)
- Deel door de coëfficiënt van de hoogste macht van x, zodat
monisch wordt.
- Ontbindt
in lineaire factoren van de vorm
. Dit zullen
factoren zijn.
- Output
, is de gecorrigeerd code
, met een correctie op de plaatsen
, waar
.
Voor een uitgebreid voorbeeld van dit algoritme wordt verwezen naar het artikel van Bernstein.[1]