$SPAD/src/input exampleagcode.input

Timothy Daly December 3, 2016

Abstract

Contents

2

— * —

)set break resume
)spool exampleagcode.output
)set message auto off
)clear all
-- This example is to show how to compute the generator matrix
-- of an algebraic geometric code (AG-codes, or geometric Goppa code).
-- Here we use the same curve has the example in the example1.input file,
-- that is the curve defined by
--
--       5    2 3      4
--      X  + Y Z  + Y Z  = 0
--
--
-- NOTE THAT we will use the package PAFFFF instead of PAFF.
--
-- With PAFFFF the computation are done using dynamic extension
-- over the FINITE ground field that is given to PAFFFF.
--
-- For example,
--
--           PAFFFF(K,[X,Y,Z])
--
-- will do computation in any finite extension of K when NEEDED ONLY,
-- while
--
--           PAFF(K,[X,Y,Z])
--
-- only do computation over the field K and, when
-- some extension is needed, PAFF cannot go further and stop.
--
--
-- In fact the difference between PAFF(K,[X,Y,Z]) and PAFFFF(K,[X,Y,Z])
-- is that PAFFFF(K,[X,Y,Z]) will do the computation using the domain
--
--      PseudoAlgebraicClosureOfFiniteField  (abbreviation PACOFF)
--
-- (see pseudoAlgCls.spad in the */spad directory).
--
-- Note that it is almost right to say that  PAFFFF(K,[X,Y,Z]) is  the same as
-- PAFF(PACOFF(K),[X,Y,Z]) but PAFFFF(K,[X,Y,Z]) is easier to use.
--
--
--
-- We want here to construct an AG-code over the field GF(2^4)
-- and also, we want the code to be of length equal to the number of places
-- of degree 1 of the function field of the curve. To do this we consider

-- the following
--
-- Let
--
--   F    be the function field of the curve with constant field GF(2) and
--   F4   be the function field of the curve with constant field GF(2^4)
--        (F4 is the field obtained from F by
--         taking a constant field extension)
--
-- It is clear that F is a subfield of F4, but since GF(2^3)
-- is not a subfield of GF(2^4),
-- any place of F of degre 3 will not split in F4 and in particular,
-- any place of F of degre 3 is dominated by a unique place of F4 of degre 3.
--
-- Let P be a place of degree 3 of F and Q be the unique place
-- of F4 above P (i.e. Q | P).
-- It is well known that a basis of L(nP) is a basis of L(nQ)
-- ( n being an integer ).
-- Using this fact, we can contruct an AG-code of length
-- equal to the number of places
-- of degree 1 of the function field of the curve.
--
--
-- First, let us find all the places of degree 3 of F.
-- The results from PAFFFF will be something like this:
--
--                 2       3         2   3
--        [[%D4:%D4  + 1:1] ,[%D4:%D4 :1] ]
--
-- What you have here is 2 places of degree 3
-- (the degree is given by the exponant).
-- Also, they correspond to simple points of the curve
-- defined in an extension of degree 3.
--
--S 1 of 19
K1:= PF(2)
--R
--R
--R   (1)  PrimeField(2)
--R                                                                 Type: Domain
--E 1
--S 2 of 19
R1:= DMP([X,Y,Z],K1)
--R
--R
--R   (2)  DistributedMultivariatePolynomial([X,Y,Z],PrimeField(2))
--R                                                                 Type: Domain
--E 2

--S 3 of 19
P1:= PAFFFF(K1,[X,Y,Z],BLQT)
--R
--R
--R   (3)
--R  PackageForAlgebraicFunctionFieldOverFiniteField(PrimeField(2),[X,Y,Z],BlowUpW
--R  ithQuadTrans)
--R                                                                 Type: Domain
--E 3
--S 4 of 19
C1:R1:=X**5 + Y**2*Z**3+Y*Z**4
--R
--R
--R         5    2 3      4
--R   (4)  X  + Y Z  + Y Z
--R               Type: DistributedMultivariatePolynomial([X,Y,Z],PrimeField(2))
--E 4
--S 5 of 19
setCurve(C1)$P1
--R
--R
--R         5    2 3      4
--R   (5)  X  + Y Z  + Y Z
--R               Type: DistributedMultivariatePolynomial([X,Y,Z],PrimeField(2))
--E 5
--S 6 of 19
plc3:= placesOfDegree(3)$P1
--R
--R
--R                 2   3         2       3
--R   (6)  [[%D5:%D5 :1] ,[%D5:%D5  + 1:1] ]
--R     Type: List(PlacesOverPseudoAlgebraicClosureOfFiniteField(PrimeField(2)))
--E 6
-- %D4 is an elemenent created by the domain PACOFF: it is a root of the
-- irreducible polynomial of degree 3 that is used to defined the
-- extension of degree 3 of GF(2).
-- To see the irreducible polynomial you can issue the following that will
-- retreive the first coordinate of the simple point
-- corresponding to the first place
-- of the list of places of degree 3.
-- Then we look at the defining polynomial of the element:
--S 7 of 19
a:= elt( first % , 1 )
--R

--R
--R   (7)  %D5
--R                     Type: PseudoAlgebraicClosureOfFiniteField(PrimeField(2))
--E 7
--S 8 of 19
definingPolynomial(a)
--R
--R
--R         3    2
--R   (8)  ?  + ?  + 1
--RType: SparseUnivariatePolynomial(PseudoAlgebraicClosureOfFiniteField(PrimeField(2)))
--E 8
--S 9 of 19
a**3 + a**2 + 1
--R
--R
--R   (9)  0
--R                     Type: PseudoAlgebraicClosureOfFiniteField(PrimeField(2))
--E 9
-- As you can see, %D4 is the root of an irreducible poynomial of degree 3.
--
-- Now we construct a divisor using the places of degree 3.
-- It will be 2 times the sum of the 2 places of degree 3.
--
--S 10 of 19
D:= 2 * reduce(+,(plc3 :: List DIV PLACESPS PF 2))
--R
--R
--R                   2   3             2       3
--R   (10)  2 [%D5:%D5 :1]  + 2 [%D5:%D5  + 1:1]
--R  Type: Divisor(PlacesOverPseudoAlgebraicClosureOfFiniteField(PrimeField(2)))
--E 10
-- Now we compute a basis of L(D)
--S 11 of 19
lB1:= lBasis(D)$P1
--R
--R   Trying to interpolate with forms of degree:
--R   4
--R   Denominator found
--R   Intersection Divisor of Denominator found
--R
--R   (11)
--R           4    3  2 2    3      2    2   2 2  2     3   3   4
--R   [num= [Z ,Y Z ,Y Z ,X Z ,X Y Z ,X Y Z,X Z ,X Y Z,X Z,X Y,X ],

--R          4      2         2    4
--R    den= X  + X Y Z + X Y Z  + Z ]
--IType: Record(num: List(DistributedMultivariatePolynomial([X,Y,Z],...
--E 11
-- Since we want to construct a code over GF(2^4), we defined the
-- package PAFFFF over GF(2^4) to compute all the places of degree 1
--S 12 of 19
K4:= FFCG(2,4)
--R
--R
--R   (12)  FiniteFieldCyclicGroup(2,4)
--R                                                                 Type: Domain
--E 12
--S 13 of 19
R4:= DMP([X,Y,Z],K4)
--R
--R
--R   (13)
--R   DistributedMultivariatePolynomial([X,Y,Z],FiniteFieldCyclicGroup(2,4))
--R                                                                 Type: Domain
--E 13
--S 14 of 19
P4:= PAFFFF(K4,[X,Y,Z],BLQT)
--R
--R
--R   (14)
--R  PackageForAlgebraicFunctionFieldOverFiniteField(FiniteFieldCyclicGroup(2,4),[
--R  X,Y,Z],BlowUpWithQuadTrans)
--R                                                                 Type: Domain
--E 14
--S 15 of 19
C4:R4:=C1
--R
--R
--R          5    2 3      4
--R   (15)  X  + Y Z  + Y Z
--R Type: DistributedMultivariatePolynomial([X,Y,Z],FiniteFieldCyclicGroup(2,4))
--E 15
--S 16 of 19
setCurve(C4)$P4
--R
--R
--R          5    2 3      4
--R   (16)  X  + Y Z  + Y Z

--R Type: DistributedMultivariatePolynomial([X,Y,Z],FiniteFieldCyclicGroup(2,4))
--E 16
--S 17 of 19
plc1 := placesOfDegree(1)$P4
--R
--R
--R   (17)
--R         10   1       5   1     1   4   1     1   1   1     2   8   1
--R   [[1:%A  :1] , [1:%A :1] , [%A :%A :1] , [%A :%A :1] , [%A :%A :1] ,
--R       2   2   1     3   10   1     3   5   1     4   4   1     4   1   1
--R    [%A :%A :1] , [%A :%A  :1] , [%A :%A :1] , [%A :%A :1] , [%A :%A :1] ,
--R       5   8   1     5   2   1     6   10   1     6   5   1     7   4   1
--R    [%A :%A :1] , [%A :%A :1] , [%A :%A  :1] , [%A :%A :1] , [%A :%A :1] ,
--R       7   1   1     8   8   1     8   2   1     9   10   1     9   5   1
--R    [%A :%A :1] , [%A :%A :1] , [%A :%A :1] , [%A :%A  :1] , [%A :%A :1] ,
--R       10   4   1     10   1   1     11   8   1     11   2   1     12   10   1
--R    [%A  :%A :1] , [%A  :%A :1] , [%A  :%A :1] , [%A  :%A :1] , [%A  :%A  :1] ,
--R       12   5   1     13   4   1     13   1   1     14   8   1     14   2   1
--R    [%A  :%A :1] , [%A  :%A :1] , [%A  :%A :1] , [%A  :%A :1] , [%A  :%A :1] ,
--R           1         1     1
--R    [0:0:1] , [0:1:1] , %I3 ]
--IType: List(PlacesOverPseudoAlgebraicClosureOfFiniteField(...
--E 17
-- Now, we can construct the matrix of the AG-code, which code-words consist
-- of the evaluation of function in L(D) at each places of F4 of degree 1.
-- Note that we call the function eval of the package P4: this function
-- evaluate function at a place by taking as arguments the
-- numerator and the denominator of a function and a place.
--S 18 of 19
mG:= matrix [ [ eval( f, lB1.den, pl )$P4 for pl in plc1 ] for f in lB1.num ]
--R
--R
--R   (18)
--R   [
--R              4    4    8    8    10    10    1    1    10    10    5    5
--R     [1, 1, %A , %A , %A , %A , %A  , %A  , %A , %A , %A  , %A  , %A , %A ,
--R        11    11    2    2    5    5    5    5    13    13    10    10    14
--R      %A  , %A  , %A , %A , %A , %A , %A , %A , %A  , %A  , %A  , %A  , %A  ,
--R        14    7    7
--R      %A  , %A , %A , 1, 1, 0]
--R     ,
--R
--R        10    5    8    5    1    10    5       5    2    3    12       10
--R     [%A  , %A , %A , %A , %A , %A  , %A , 1, %A , %A , %A , %A  , 1, %A  , 1,
--R        12    10    4       10    9    6    6       5       3          9
--R      %A  , %A  , %A , 1, %A  , %A , %A , %A , 1, %A , 1, %A , 1, 1, %A , 0, 1,
--R      0]

--R     ,
--R
--R        5    10    12    6    9    12       5    9    3    11    14    10
--R     [%A , %A  , %A  , %A , %A , %A  , 1, %A , %A , %A , %A  , %A  , %A  , 1,
--R        4    13    3    6    10       13    7    14    2       5    7    1
--R      %A , %A  , %A , %A , %A  , 1, %A  , %A , %A  , %A , 1, %A , %A , %A ,
--R        8    11
--R      %A , %A  , 0, 1, 0]
--R     ,
--R
--R              5    5    10    10    13    13    5    5          11    11    3
--R     [1, 1, %A , %A , %A  , %A  , %A  , %A  , %A , %A , 1, 1, %A  , %A  , %A ,
--R        3    10    10    14    14          9    9    7    7    12    12    6
--R      %A , %A  , %A  , %A  , %A  , 1, 1, %A , %A , %A , %A , %A  , %A  , %A ,
--R        6
--R      %A , 0, 0, 0]
--R     ,
--R
--R        10    5    9    6    3    12    8    3    9    6    8    2    6    1
--R     [%A  , %A , %A , %A , %A , %A  , %A , %A , %A , %A , %A , %A , %A , %A ,
--R        7    4    3    12    9    4    4    1    2    11    2    12    1    13
--R      %A , %A , %A , %A  , %A , %A , %A , %A , %A , %A  , %A , %A  , %A , %A  ,
--R        14    8
--R      %A  , %A , 0, 0, 0]
--R     ,
--R
--R        5    10    13    7    11    14    3    8    13    7    1    4    1
--R     [%A , %A  , %A  , %A , %A  , %A  , %A , %A , %A  , %A , %A , %A , %A ,
--R        6    11    5    11    14    4    9    8    2    10    13    12    2
--R      %A , %A  , %A , %A  , %A  , %A , %A , %A , %A , %A  , %A  , %A  , %A ,
--R        5    14    7    10
--R      %A , %A  , %A , %A  , 0, 0, 1]
--R     ,
--R
--R              6    6    12    12    1    1    9    9    5    5    2    2    10
--R     [1, 1, %A , %A , %A  , %A  , %A , %A , %A , %A , %A , %A , %A , %A , %A  ,
--R        10    3    3    8    8    10    10    5    5    4    4    10    10
--R      %A  , %A , %A , %A , %A , %A  , %A  , %A , %A , %A , %A , %A  , %A  ,
--R        5    5
--R      %A , %A , 0, 0, 0]
--R     ,
--R
--R        10    5    10    7    5    14    11    6    13    10    13    7    12
--R     [%A  , %A , %A  , %A , %A , %A  , %A  , %A , %A  , %A  , %A  , %A , %A  ,
--R        7    14    11    11    5    3    13    14    11    13    7    14    9
--R      %A , %A  , %A  , %A  , %A , %A , %A  , %A  , %A  , %A  , %A , %A  , %A ,
--R        14    11    13    7
--R      %A  , %A  , %A  , %A , 0, 0, 0]
--R     ,
--R

--R              7    7    14    14    4    4    13    13    10    10    8    8
--R     [1, 1, %A , %A , %A  , %A  , %A , %A , %A  , %A  , %A  , %A  , %A , %A ,
--R        2    2    11    11    2    2    5    5    1    1    1    1    8    8
--R      %A , %A , %A  , %A  , %A , %A , %A , %A , %A , %A , %A , %A , %A , %A ,
--R        4    4
--R      %A , %A , 0, 0, 0]
--R     ,
--R
--R        10    5    11    8    7    1    14    9    2    14    3    12    3
--R     [%A  , %A , %A  , %A , %A , %A , %A  , %A , %A , %A  , %A , %A  , %A ,
--R        13    6    3    4    13    12    7    9    6    9    3    11    6
--R      %A  , %A , %A , %A , %A  , %A  , %A , %A , %A , %A , %A , %A  , %A ,
--R        12    9    12    6
--R      %A  , %A , %A  , %A , 0, 0, 0]
--R     ,
--R
--R              8    8    1    1    7    7    2    2          14    14    9    9
--R     [1, 1, %A , %A , %A , %A , %A , %A , %A , %A , 1, 1, %A  , %A  , %A , %A ,
--R        4    4    11    11          12    12    13    13    6    6    3    3
--R      %A , %A , %A  , %A  , 1, 1, %A  , %A  , %A  , %A  , %A , %A , %A , %A ,
--R      0, 0, 0]
--R     ]
--R                                    Type: Matrix(FiniteFieldCyclicGroup(2,4))
--E 18
-- The preceding matrix is the generator matrix of a [n,k,d]-code over GF(2^4)
-- where
--
--  n = nb. of places of degree 1 = 33
--
--  k = dim L(D) = deg D - g + 1 = 11  ( since deg D >= 2g -1)
--
--  d >= 33 - degree D = 33 - 12 = 21
--
--
-- In fact, if one look at the row echelon form of the matrix, he will
-- find out that there is a code word of weight 21, so that code has a
-- minimum distance d = 21.  (OF COURSE this doesn't work all the time,
-- that we don't always find a word of minimal weight
-- in the row echelon form of the generator matrix).
--S 19 of 19
reduce(min, [33 - count(zero?,l) for l in listOfLists rowEchelon mG])
--R
--R
--R   (19)  21
--R                                                        Type: PositiveInteger
--E 19
)spool

)lisp (bye) ———-

11

References^{[1] nothing}

12