Linear Algebra in Finite Fields (Goppa Codes)

asked 8 years ago

fagui
187 ●10 ●18 ●24

updated 5 years ago

FrédéricC

5426 ●4 ●44 ●121

Context:

I am trying to calculate a generator matrix for Goppa codes.

We are working in GF(16), e is a generator of GF(16), and we are given the polynomial g = (x+e)*(x+e^14)

F.<e> = GF(16)
p = e.minpoly()
p
R.<x> = PolynomialRing(F)
g=(x+e)*(x+e^14)

i calculate the parity check matrix with coefficients in GF(16) as follows

H = matrix(F,2,12)
for i in range (2,14):
    f=-((g(x)-g(e^i))/(x-e^i))*(1/g(e^i))
    print("i=%s %s"%(i,f))
    ff=R(f) # coerce to polynomial with canonical injection
    H[0,i-2]=ff.list()[0]
    H[1,i-2]=ff.list()[1]

i=2 (e^3 + e^2 + e + 1)*x + e^3 + e

i=3 (e^3 + e^2)*x + e^2 + e + 1

i=4 (e^3 + e^2)*x + e^3 + e

i=5 e*x + e^3 + 1

i=6 (e^3 + e^2 + e)*x + e^3 + e^2

i=7 x

i=8 (e^3 + 1)*x + e^2 + e + 1

i=9 (e^2 + 1)*x + e^2 + 1

i=10 (e^3 + e^2 + e)*x + e^2

i=11 (e^3 + 1)*x + e^3 + e + 1

i=12 (e^3 + e^2 + e + 1)*x + e^3 + 1

i=13 e*x + e^3 + e^2

H is a 2x12 matrix in GF(16) now I am are interested in getting a 8x12 matrix corresponding to 8 equations. We get 4 equations for each row of H. i am considering a vector of size 12 of unknowns c=(c1,c2,...,12) [with possible values 0 or 1], and for each row, we will look at the equation row_i * c=0 and we group terms corresponding to 1,e,e^2,e^3 and because this is a basis of GF(16) we know that the coefficients of 1,e,e^2,e^3 are 0. I want to extract those equations.

var('c1','c2','c3','c4','c5','c6','c7','c8','c9','c10','c11','c12')
C=matrix([[c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12]])
H*C.T

[ (e^3 + e)c1 + (e^3 + e + 1)c10 + (e^3 + 1)c11 + (e^3 + e^2)c12 + (e^2 + e + 1)c2 + (e^3 + e)c3 + (e^3 + 1)c4 + (e^3 + e^2)c5 + (e^2 + e + 1)c7 + (e^2 + 1)c8 + e^2c9] [(e^3 + e^2 + e + 1)c1 + (e^3 + 1)c10 + (e^3 + e^2 + e + 1)c11 + ec12 + (e^3 + e^2)c2 + (e^3 + e^2)c3 + ec4 + (e^3 + e^2 + e)c5 + c6 + (e^3 + 1)c7 + (e^2 + 1)c8 + (e^3 + e^2 + e)c9]

for example for the first row the equation corresponding to e should be (c1+c10+c2+c3+c7 =0)

could u please tell me how to recover the equation AND to get ... (more)

Comments

See also on Stackoverflow.

kcrisman ( 8 years ago )

add a comment

answered 8 years ago

tmonteil
27483 ●32 ●205 ●519 http://wiki.sagemath.o...

updated 8 years ago

Given an element of the finite field F, you can see it as a vector over its prime subfield as follows:

sage: x = 1+e+e^3
sage: x
e^3 + e + 1
sage: vector(x)
(1, 1, 0, 1)
sage: vector(x).parent()
Vector space of dimension 4 over Finite Field of size 2

So you can "unfold" you matrix as follows;

sage: K = GF(2)
sage: M = Matrix(K,8,12)
sage: for i in range(2): 
....:    for j in range(4):
....:        for k in range(12):
....:            M[4*i+j,k] = vector(H[i,k])[j]
sage: M
[0 1 0 1 0 0 1 1 0 1 1 0]
[1 1 1 0 0 0 1 0 0 1 0 0]
[0 1 0 0 1 0 1 1 1 0 0 1]
[1 0 1 1 1 0 0 0 0 1 1 1]
[1 0 0 0 0 1 1 1 0 1 1 0]
[1 0 0 1 1 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 0]
[1 1 1 0 1 0 1 0 1 1 1 0]

You can check that the second row corresponds to your equation c1+c10+c2+c3+c7 =0 (note however that it is usually more practical and more Python-friendly, to have indices starting at 0, not 1).

Then you can get the right kernel of M as follows:

sage: M.right_kernel()
Vector space of degree 12 and dimension 4 over Finite Field of size 2
Basis matrix:
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]

EDIT

You can get the kernel as the rows of a matrix as follows:

sage: B = M.right_kernel().basis_matrix()
sage: B
[1 0 0 0 1 1 0 1 1 1 0 1]
[0 1 0 0 1 1 1 1 0 0 1 0]
[0 0 1 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 0 0 0 1 1]

Note that the vectors of the basis are rows of the matrix, so, if you want to combine them with M, since we took the right kernel, you have to take the transpose of it:

sage: B.T
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 1 1 1]
[1 1 0 1]
[0 1 1 0]
[1 1 1 0]
[1 0 1 0]
[1 0 0 0]
[0 1 0 1]
[1 0 0 1]
sage: M*B.T
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 ...

(more)

link

Comments

thank you so much !!!!

as my linear algebra is a little bit rusty:

there is not ONE basis matrix right ? the function returns ONE basis among a (finite) number of them

for example, change the 2nd row by the addition of the 1st and 2 rows...

more exactly there are 2^4 vectors in that subspace, including the null vector, which all linearly independent (save for the null vector), and there are thus choose(15,4) possible basis. correct ?

fagui ( 8 years ago )

last question: the last object is

<class
'sage.modules.free_module.FreeModule_submodule_field_with_category'>

how do i get in a matrix object the basis matrix that is given in output ?

if i define v=M.right_kernel() and do

sage: v*M.T

i get an error TypeError: each element of basis must be in the ambient vector space

fagui ( 8 years ago )

Reagrding your last question, i updated my answer. Regarding the other questions:

YES a vector space usually have more than one basis
YES there are 2^4 vectors in the subspace
NO there are not all linearly independent, for example, the first row, the second row, and the sum of the two are not linearly independent
by lack of space i answer the question about below the number of bases below.

tmonteil ( 8 years ago )

NO there are less bases than that:
- for the first vector of the basis, you can chose any nonzero vector : 2^4-1 = 2^4 - 2^0 choices
- for the second vector, you can chose any vector not colinear to the first : 2^4 - 2 = 2^4 - 2^1 choices
- for the third vector, you can chose any vector not in the plane generated by the first two vectors : 2^4 - 2^2 choices
- for the fourth vector, you can chose any vector not in the 3D-space generated by the first three vectors : 2^4 - 2^3

So, the total number of ordered bases is (2^4 - 2^3)*(2^4 - 2^2)*(2^4 - 2^2)*(2^4 - 1) = 17280, so the total number of bases is (2^4 - 2^3)*(2^4 - 2^2)*(2^4 - 2^2)*(2^4 - 1)/4! = 720.

tmonteil ( 8 years ago )

thank you very much for this refresher...it was very very helpful !!!

fagui ( 8 years ago )

see more comments

Linear Algebra in Finite Fields (Goppa Codes)

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Linear Algebra in Finite Fields (Goppa Codes) savecancel

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Linear Algebra in Finite Fields (Goppa Codes)