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
n
=
2
m
{\displaystyle n=2^{m}}
m
∈
{
10
,
11
,
12
}
{\displaystyle m\in \{10,11,12\}}
De code is gedefinieerd over het lichaam
G
F
(
n
)
{\displaystyle \mathbb {GF} (n)}
a
1
,
a
2
,
…
,
a
n
{\displaystyle a_{1},a_{2},\dots ,a_{n}}
lexicografisch geordend .
Voor het aantal fouten
t
{\displaystyle t}
2
≤
t
≤
2
m
−
1
m
{\displaystyle 2\leq t\leq {\frac {2^{m}-1}{m}}}
m
=
11
{\displaystyle m=11}
t
=
32
,
t
=
70
{\displaystyle t=32,t=70}
t
=
100
{\displaystyle t=100}
Zoek een irreducibele monische polynoom
g
∈
G
F
(
2
m
)
[
x
]
{\displaystyle g\in \mathbb {GF} (2^{m})[x]}
graad
t
{\displaystyle t}
Laat
h
=
∏
i
(
x
−
a
i
)
∈
G
F
(
n
)
[
x
]
{\displaystyle h=\prod _{i}(x-a_{i})\in \mathbb {GF} (n)[x]}
In dit geval geldt dat
h
=
x
n
−
x
∈
G
F
(
2
m
)
[
x
]
{\displaystyle h=x^{n}-x\in \mathbb {GF} (2^{m})[x]}
Definitie
Een definitie van de goppa-code
Γ
{\displaystyle \Gamma }
Γ
=
Γ
(
a
1
,
a
2
,
…
,
a
n
,
g
)
=
{
c
∈
G
F
(
2
m
)
:
∑
i
c
i
h
x
−
a
i
mod
g
=
0
}
{\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
h
x
−
a
1
mod
g
,
h
x
−
a
2
mod
g
,
…
,
h
x
−
a
n
mod
g
{\displaystyle {\frac {h}{x-a_{1}}}{\bmod {g}},{\frac {h}{x-a_{2}}}{\bmod {g}},\ldots ,{\frac {h}{x-a_{n}}}{\bmod {g}}}
G
F
(
2
)
{\displaystyle \mathbb {GF} (2)}
Ze vormen een pariteitscontrole-matrix voor de code
Γ
{\displaystyle \Gamma }
Algoritme van Patterson
In 1975 heeft Patterson een algoritme ontwikkeld om in polynomiale tijd
t
{\displaystyle t}
Voordat het algoritme weergegeven kan worden, is de definitie nodig van de norm van een polynoom.
Algoritme
Het doel is om maximaal
t
{\displaystyle t}
Γ
{\displaystyle \Gamma }
w
∈
G
F
n
(
2
)
{\displaystyle w\in \mathbb {GF} ^{n}(2)}
t
{\displaystyle t}
c
≈
w
{\displaystyle c\approx w}
t
{\displaystyle t}
Bereken
∑
i
w
i
x
−
a
i
{\displaystyle {\sum _{i}{\frac {w_{i}}{x-a_{i}}}}}
G
F
(
2
m
)
[
x
]
/
(
g
)
{\displaystyle \mathbb {GF} (2^{m})[x]/(g)}
w
{\displaystyle w}
Bereken de wortel van
1
∑
i
w
i
x
−
a
i
−
x
{\displaystyle {\frac {1}{\sum _{i}{\frac {w_{i}}{x-a_{i}}}}}-x}
G
F
(
2
m
)
[
x
]
/
(
g
)
{\displaystyle \mathbb {GF} (2^{m})[x]/(g)}
Noem deze berekende wortel
s
{\displaystyle s}
s
∈
G
F
(
2
m
)
[
x
]
{\displaystyle s\in \mathbb {GF} (2^{m})[x]}
s
{\displaystyle s}
t
{\displaystyle t}
De vectoren
(
s
,
1
)
{\displaystyle (s,1)}
(
g
,
0
)
{\displaystyle (g,0)}
rooster
L
⊆
G
F
(
2
m
)
[
x
]
2
{\displaystyle L\subseteq \mathbb {GF} (2^{m})[x]^{2}}
De norm
|
(
α
,
β
)
|
{\displaystyle |(\alpha ,\beta )|}
(
α
,
β
)
∈
G
F
(
2
m
)
[
x
]
2
{\displaystyle (\alpha ,\beta )\in \mathbb {GF} (2^{m})[x]^{2}}
α
2
+
x
β
2
{\displaystyle \alpha ^{2}+x\beta ^{2}}
Zo is de lengte van de vector
(
g
,
0
)
{\displaystyle (g,0)}
|
(
g
,
0
)
|
=
|
g
2
|
=
2
2
t
{\displaystyle |(g,0)|=|g^{2}|=2^{2t}}
Vind met behulp van basisreductie een basis
(
α
0
,
β
0
)
{\displaystyle (\alpha _{0},\beta _{0})}
2
t
{\displaystyle 2^{t}}
Bereken
ϵ
=
α
0
2
+
x
β
0
2
{\displaystyle \epsilon =\alpha _{0}^{2}+x\beta _{0}^{2}}
Deel door de coëfficiënt van de hoogste macht van x, zodat
ϵ
{\displaystyle \epsilon }
Ontbindt
ϵ
{\displaystyle \epsilon }
(
x
−
a
i
)
{\displaystyle (x-a_{i})}
t
{\displaystyle t}
Output
c
{\displaystyle c}
w
{\displaystyle w}
i
{\displaystyle i}
ϵ
(
a
i
)
=
0
{\displaystyle \epsilon (a_{i})=0}
Voor een uitgebreid voorbeeld van dit algoritme wordt verwezen naar het artikel van Bernstein.
![{\displaystyle g\in \mathbb {GF} (2^{m})[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c5cac15d8f4396081af0ac899e54d9058bfb443)
![{\displaystyle h=\prod _{i}(x-a_{i})\in \mathbb {GF} (n)[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c34987586d8a88d3e994fabdec3724b3a5bf992d)
![{\displaystyle h=x^{n}-x\in \mathbb {GF} (2^{m})[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95d694f623a219c91c2489be81d9954dd6eaf2ad)
![{\displaystyle \phi \in \mathbb {GF} (2^{m})[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf2eb22a53a8619a5ec7ba87556fea9320825e9e)
![{\displaystyle \mathbb {GF} (2^{m})[x]/(g)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ff051764eeca4ca20d62567bd73980ec3b65771)
![{\displaystyle s\in \mathbb {GF} (2^{m})[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2417e9cf9f664324232ebf0563899fb16251d070)
![{\displaystyle L\subseteq \mathbb {GF} (2^{m})[x]^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/58e2830f420b8e20fa7dbb2d20dc749210e56a8d)
![{\displaystyle (\alpha ,\beta )\in \mathbb {GF} (2^{m})[x]^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cdbf1131a20f439aff4571bcd8395255a2815f9)
