Ask Your Question
1

Linear Algebra in Finite Fields (Goppa Codes)

asked 2016-06-25 13:18:09 +0100

fagui gravatar image

updated 2019-09-03 14:05:25 +0100

FrédéricC gravatar image

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)

edit retag flag offensive close merge delete

Comments

kcrisman gravatar imagekcrisman ( 2016-06-25 20:16:44 +0100 )edit

1 Answer

Sort by » oldest newest most voted
2

answered 2016-06-26 00:29:31 +0100

tmonteil gravatar image

updated 2016-06-26 11:14:47 +0100

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)
edit flag offensive delete link more

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 gravatar imagefagui ( 2016-06-26 03:21:56 +0100 )edit

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 gravatar imagefagui ( 2016-06-26 03:56:22 +0100 )edit

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 gravatar imagetmonteil ( 2016-06-26 11:22:13 +0100 )edit
  • 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 gravatar imagetmonteil ( 2016-06-26 11:24:43 +0100 )edit

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

fagui gravatar imagefagui ( 2016-06-26 13:12:05 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-06-25 13:18:09 +0100

Seen: 1,995 times

Last updated: Jun 26 '16