Page 56 - ISCI’2017

Definition 3 [40]. Alternantive (n, k, d) Goppa code Г(L, G) over GF(q) consists of all vectors

c = (с1, с2, …, сn) such that
Rc(x) ≡ 0 mod G(x), (16)

where

n c
R c () x = ∑ i ,
i= 1 x α− i
G(x) is a polynomial with the coefficients from GF(q ) (Goppa polynomial), L = (α1, α2, …, αn) is a
m
subset of the elements from GF(q ) such that G(αi) ≠ 0 ∀αi∈L.
m
Using the expression (16), validation matrix of the Goppa code can be set as follows.

Polynomial x - αi in a ring of polynomials in modulus G(x) has an inverse polynomial:
() G
Gx − ( )α
(x α − i ) = − 1 − x α− i i G − 1 ()α i .

Consequently, the vector c = (с1, с2, …, сn) belongs to Goppa code Г(L, G) if and only if

() G α−
n Gx ( )
∑ c i i G α i 0
() = . (17)
1
−
i= 1 x α− i
r
m
i
If ()G x = ∑ gx , where gi ∈ GF(q ) и gr ≠ 0, then
i
i= 0
Gx ( ) = g (x r 1 − x α + r− 2 ... α ++ r 1 − ) g (x α r− 2 ... α ++ r 1 − ) ... g (x α + ) g .
() G α−
++
+
+
i
x α− i r i i r 1 − i i 2 i 1
r-1
r-2
Equating to zero according to (17) all coefficients at x , x , …, 1, obtain that the condition
cH = 0 is performed only if
T

 g G α − 1 ( ) g G − 1 (α ) ...
2
 (g + r α gG α ) 1 − 1 ( ) (g + r α gG − 1 (α ) ...
)
H =  r− 1 1 r 1 r− 1 2 r 2
 ... ... ...


... α
)
... α
 (g + α 1 g ++ 1 r− 1 gG α r ) − 1 ( ) (g + α 2 g ++ 2 r− 1 gG − 1 (α 2 ) ...
r
1
1
1
2
2
... g G − 1 (α n ) 
r
... (g r− 1 + α n gG − 1 (α n )   =
)
r
... ... 
)
... α
... (g + α n g ++ n r− 1 g r )G − 1 (α n   
2
1
g r 0 ... 0   1 1 ... 1    G α 1 0 ... 0 
−
1
( )
g g ... 0   α α ... α  0 G − 1 (α ) ... 0   
= r 1 − r   1 2 n  2    .
... ... ... ...   ... ... ... ...     ... ... ... ... 
 g 1 g 2 ... g r     α 1 r 1 − α 2 r 1 − ... α n  r 1 −   0 0 ... G − 1 (α n  )    
Matrix
56