Cryptography Reference
In-Depth Information
Für die Berechnung des Lokatorpolynoms
Λ(
x
)
EUKL
findet eine reduzierte
Form des Algorithmus auf der Basis von Polynomen Anwendung. Eingangspa-
rameter sind der Minimalabstand
d
min
und ein Syndrompolynom
S
(
x
)
.In
S
(
x
)
sind die Fehlersyndrome, berechnet im 1. Bearbeitungsschritt des Korrektural-
gorithmus, die Koe
zienten des Polynoms:
2
f
k
i
=1
S
(
x
)=
s
2
f
k
x
2
f
k
−
1
+
s
2
f
k
−
1
x
2
f
k
−
2
+
...
+
s
2
x
+
s
1
=
s
i
x
i
−
1
.
Der modifizierte EUKLID-Algorithmus für die Berechnung des Lokatorpoly-
noms
Λ(
x
)
EUKL
auf der Basis von Polynomen sieht dann wie folgt aus:
d
min
;
f
k
;
S
(
x
)
r
−
1
(
x
):=
x
d
min
−
1
;
r
0
(
x
):=
S
(
x
);
i
:= 0
w
−
1
(
x
):=0;
w
0
(
x
):=1
r
i
(
x
)
≥ f
k
i
:=
i
+1
r
i
(
x
):=
r
i
−
2
(
x
)
r
i
−
1
(
x
)
r
i
−
1
(
x
)
w
i
(
x
):=
w
i
−
2
(
x
)+
q
(
x
)
· w
i
−
1
(
x
)
Λ(
x
)
EUKL
:=
w
i
(
x
)
·
q
(
x
):=
r
i
−
2
(
x
)
Anmerkung:
w
i
(
x
)=
w
i,ν
x
ν
1
w
i,
0
;
ν
:=
+
...
+
w
i,
1
x
+
w
i,
0
w
i
(
x
)
Λ(
x
)
EUKL
;
ν
Rekonstruktionsversagen tritt auf, wenn
w
i,
0
=Λ
0
Null ist, s. a. S. 192.
Beispiel 8.5.23
Für das Beispiel 8.5.22 ist das Lokatorpolynom mit dem EUKLID-Algorithmus
zu berechnen.
Lösung:
0.
b/
A
1.
s
1
=1
,s
2
=
α
2
,s
3
=
α
4
,s
4
=
α
6
−→
∈
S
(
x
)=
α
6
x
3
+
α
4
x
2
+
α
2
x
+1
2.
Abarbeitungsprotokoll: (
d
min
=5
,f
k
=2
)
i
r
i
(
x
)
q
(
x
)
w
i
(
x
)
-1
x
4
0
0
α
6
x
3
+
α
4
x
2
+
α
2
x
+1
1
1
α
6
αx
+
α
6
αx
+
α
6
Ausgabe:
Λ(
x
)
EUKL
=(
αx
+
α
6
)
α
−
6
=1+
α
2
x
;
ν
=1
.
−→
Unter Berücksichtigung von Auslöschung mit
ρ
≥
0
,d.h.istAuslöschung
vorhanden oder nicht, kann der Algorithmus auch wie folgt notiert werden:
