Cryptography Reference
In-Depth Information
Developing this expression, the polynomial
σ
d
(
x
)
is again equal to:
σ
d
(
x
)=
x
t
+
σ
1
x
t−
1
+
+
σ
j
x
t−j
+
···
···
+
σ
t
where the coe
cients
σ
j
are functions of the quantities
Z
l
.
From the expression of
S
j
we can build a non-linear system of
2
t
equations.
t
e
i
Z
i
,
S
j
=
j
=1
,
2
,
···
,
2
t
i
=1
The quantities
Z
l
,l
=1
,
···
,t
being the roots of the error locator polynomial
σ
d
(
x
)
,wecanwrite:
t
σ
d
(
Z
l
)=
Z
l
+
σ
j
Z
t−j
=0
,
l
=1
,
2
,
···
,t
(4.34)
l
j
=1
Multiplying the two parts of this expression by the same term
e
l
Z
l
,we
obtain:
t
e
l
Z
t
+
q
l
σ
j
e
l
Z
t
+
q−j
l
+
=0
,
l
=1
,
2
,
···
,t
(4.35)
j
=1
Summing relations (4.35) for
l
from 1 to
t
and taking into account the defi-
nition of component
S
j
of syndrome
S
,wecanwrite:
S
t
+
q
+
σ
1
S
t
+
q−
1
+
···
+
σ
j
S
t
+
q−j
+
···
+
σ
t
S
q
=0
,
∀
q
(4.36)
For an RS code correcting one error (
t
=1
)inablockof
n
symbols, syndrome
S
has two components
S
1
and
S
2
.Coecient
σ
1
of the error locator polynomial
is determined from relation (4.36) by making
t
=1
and
q
=1
.
S
2
S
1
S
2
+
σ
1
S
1
=0
→
σ
1
=
(4.37)
In the same way, for an RS code correcting two errors (
t
=2)
in a block of
n
symbols, the syndrome has four components
S
1
,
S
2
,
S
3
,
S
4
.Usingrelation
(4.36) with
t
=2
and
q
=1
,
2
we obtain the following system with two equations:
σ
1
S
2
+
σ
2
S
1
=
S
3
σ
1
S
3
+
σ
2
S
2
=
S
4
Resolving this system of two equations enables us to determine coecients
σ
1
and
σ
2
of the error locator polynomial.
1
Δ
2
σ
1
=
[
S
1
S
4
+
S
2
S
3
]
S
2
S
4
+
S
3
(4.38)
1
Δ
2
σ
2
=
