Goppa-code

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 ${\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]}$.

Definitie

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 }$.