For faster navigation, this Iframe is preloading the Wikiwand page for Goppa-code.

Goppa-code

Uit Wikipedia, de vrije encyclopedie

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.

Voorwaardes

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 .

Definitie

Een definitie van de goppa-code , is nu

De polynomen , kunnen gezien worden als vectoren over .

Ze vormen een pariteitscontrole-matrix voor de code .

Algoritme van Patterson

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.

Norm van een polynoom

Voor een polynoom geldt dat de norm , met de graad van .

Bij rationale functies geldt . Bijvoorbeeld .

Algoritme

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
  • 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]

{{bottomLinkPreText}} {{bottomLinkText}}
Goppa-code
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Wikiwand 2.0 is here 🎉! We've made some exciting updates - No worries, you can always revert later on