precalculations_definitions.sage

import csv
import itertools

#primepowers=[2,3,4,5,7,8,9,11,13,16,17,19,23,24,25] 
primepowers=[2,3,4,5,7,8,9,11,13,16,17,19,23]
degrees=[4]

def PrimPol_q(n,q):
    """
    n: a positive integer
    q: a prime power
    Returns two representations of a primitive monic polynomial (the 
    lexicographically smallest) of degree n over Fq.
    The output will be a pair of the polynomial, as well as its 
    list of coefficients:
             (a0+a1x+a2x^2+...+anx^n, [a0, a1, ..., an])
    For non-prime fields, this list will contain a, which is the root 
    of the default modulus of GF(q) when generated by sage
    """
    F.<a>=GF(q)
    K.<x>=F[]

    # We don't want to test poly/s with zero constant:
    for const in [i for i in F if i <> 0]: 
        for i in itertools.product(F,repeat=n-1):
            middle_of_poly=[j for j in i]          
            # "..+[1]" the leading coefficient is 1; we only need 
            # to test monic polynomials
            testpoly=[const]+middle_of_poly+[1] 
            f=K(testpoly)
            if f.is_primitive():
                return(f,testpoly)

def Representatives(m,q):
    """
    Input:  The degree m and prime power q we are working with
    Output: a list of representatives, sorted; see section 4.3
    """
    p=q.prime_factors()[0]  # The finite field modulus
    n=q.log(p)              #q=p^n
    w=int((q**m-1)/(q-1))
    Zw=set([i for i in range(w) if gcd(i,w)==1])
    Repr=[]
    while Zw:
        # Update Zw: (See Lemma 4.22)
        i=min(Zw)
        Ci=[((i*p^r) % w) for r in range(m*n)]
        Zw.difference_update(Ci) #Zw <- Zw \ Ci
        # Find a coset leader corresponding to a primitive, 
        # if it exists (see Remark 4.26)
        Ci_prim=[x for x in Ci if gcd(x,q^m-1)==1]
        if Ci_prim: # It could be empty
            Repr.append(min(Ci_prim)) 
    Repr.sort()
    return Repr

def ZerosOfSequence(m,q,i):
    """
    Input: The degree m, the prime power q and the representative i
    Output: A list of the zero positions in the first chunk of size 
            (q^m-1)/(q-1), of the lfsr corresponding to alpha^i, where 
            Fq^m=Fq(a)
    """
    F=GF(q)
    K.<x>=F[]
    f=PrimPol_q(m,q)[0] # Polynomial in K.<x>; see definitions.sage
    Fm.<alpha>=f.root_field()
    w=(q^m-1)/(q-1)
    g=(alpha^i).minpoly()
    initstate=[int(x) for x in bin(1)[2:].zfill(m)] # Create 000..001
    # See the definition of connection polynomial
    connectionpol=[-c for c in g.list()] 
    s=lfsr_sequence(connectionpol,initstate,w)
    zeropositions=[]
    for (i,j) in enumerate(s):
        if j==0:
            zeropositions.append(i)
    return zeropositions