Cryptography Reference
In-Depth Information
1. Calculate syndrome
S
=(
S
1
,S
2
,S
3
,S
4
)
S
1
=
α
10
+
α
9
=
α
13
S
3
=
α
16
+
α
21
=
α
11
S
2
=
α
13
+
α
15
=
α
6
S
4
=
α
19
+
α
27
=
α
6
Polynomial
S
(
x
)
is therefore equal to:
S
(
x
)=
α
13
x
+
α
6
x
2
+
α
11
x
3
+
α
6
x
4
2. Calculate polynomials
Λ(
x
)
and
Γ(
x
)
from Euclid's algorithm (the calcula-
tions are performed in field
F
16
whose elements are given in the appendix).
j
=0
j
=1
R
−
1
(
x
)=
x
5
R
0
(
x
)=
S
(
x
)
R
0
(
x
)=
S
(
x
)
R
1
(
x
)=
α
5
x
3
+
α
13
x
2
+
α
12
x
Q
0
(
x
)=
α
9
x
+
α
14
Q
1
(
x
)=
αx
+
α
5
R
1
(
x
)=
α
5
x
3
+
α
13
x
2
+
α
12
xR
2
(
x
)=
α
14
x
2
+
α
14
x
U
1
(
x
)=
α
9
x
+
α
14
U
2
(
x
)=
α
10
x
2
+
α
3
x
+
α
We can verify that
deg(
U
2
(
x
)) = 2
is lower than or equal to
t
(
t
=2
)
and that
deg(
R
2
(
x
)) = 2
is lower than or equal to
t
. The algorithm is
therefore terminated and polynomials
Λ(
x
)
and
Γ(
x
)
respectively have the
expression:
Λ(
x
)=
U
2
(
x
)=
α
+
α
3
x
+
α
10
x
2
=
α
(1 +
α
2
x
+
α
9
x
2
)
Γ(
x
)=
R
2
(
x
)=
α
14
x
+
α
14
x
2
=
α
(
α
13
x
+
α
13
x
2
)
We can verify that the key equation for the decoding is satisfied and that
the two polynomials obtained are identical, to within one coecient
α
,to
those determined using the Berlekamp-Massey algorithm.
The roots of the polynomial
Λ(
x
)
are therefore
1
/α
3
and
1
/α
6
, and error
polynomial
e
(
x
)
is equal to:
e
(
x
)=
α
7
x
3
+
α
3
x
6
Calculating coecients
e
j
by a transform
It is possible to calculate the coecients
e
j
;
j
=0
,
1
,
1)
of error poly-
nomial
e
(
x
)
without determining the roots of the error locator polynomial
Λ(
x
)
.
To do this, we introduce the
extended syndrome
S
∗
(
x
)
defined by:
···
,
(
n
−
n
S
∗
(
x
)=Γ(
x
)
1+
x
n
Λ(
x
)
S
j
x
j
=
(4.48)
j
=1