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
Search WWH ::




Custom Search