Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Linear Algebra in Finite Fields (Goppa Codes)

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)

[of course it can be done by hand, but i want to be able to write the program]

PS. i am rather new to SAGE and to cryptography, i am following the MOOC from INRIA on fun-mooc

thank you

Linear Algebra in Finite Fields (Goppa Codes)

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 the answer in matrix form

the next step of course is to find a basis for the kernel. How do we do that in SAGE ?

[of course it can be done by hand, but i want to be able to write the program]

PS. i am rather new to SAGE and to cryptography, i am following the MOOC from INRIA on fun-mooc

thank you