Trying to understand a Univariate Quotient Polynomial Ring over Finite Field

edit

I tried to reproduce the code in a simple situation. This is the only way to debug. Some comments are added, as an advice to have a clean code in a clean framework, so that a clean debug can be started.

For short: The quotient is taken, but the rest is needed. There are problems with the insignificant zeros in T( rc ).list() .

(Note: i had some problems to submit the answer. Trying to partially send instead.)

dimension = 5         # degree of polynomials
modulus   = 3         # ** NOT A ** modulus, but the characteristic of the ring R below

# ring = x^dimension + 1
ring = [1, 0, 0, 0, 0, 1]    # bad name for a list representing a pol

# Quotient polynomial ring
R.<X> = PolynomialRing( GF(modulus) )     # Gaussian field of integers
Y.<x> = R.quotient( X^(dimension) + 1 )   # ** NOT A * Cyclotomic field

def division(N, D):
    """WHAT ARE N, D?
    Please always insert a comment and a test code.

    For instance:

    sage: division( [1,0,0,0,0,0,0], [1,0] ) --> Traceback 
    IndexError: list assignment index out of range
    sage: division( [1,0,0,0,0,0,0], [1,0,1] )
    ([0], [1])                                            # (?)
    sage: division( [1,0,0,0,0,0,0,1], [1,0,1] )
    ([0, 1, 0, 1, 0, 1, 0], [1, 1])

    Is the questioned "division" (?) wanted like that? than i suppose we divide 
    1 + 0*X + ... (only zeros) by 1 + 0*X + 1*X^2.
    """
    dD = degree(D)
    dN = degree(N)
    if dD < 0: raise ZeroDivisionError
    if dN >= dD:
        q = [0] * dN
        while dN >= dD:
            d = [0] * (dN - dD) + D
            mult = q[dN - dD] = N[-1] / d[-1]
            d = [coeff * mult for coeff in d]
            N = [abs(coeffN - coeffd) for coeffN, coeffd in izip(N, d)]
            dN = degree(N)
        r = N
    else:
        q = [0]
        r = N
    return (q, r)

def degree(poly):
    while poly and poly[-1] == 0:
        poly.pop()  # normalize
    return len(poly) - 1    

def ring_correct( poly, irreduciblePoly, modulus ):
    """The irreduciblePoly is not irreducible (and not a poly) in the call.
    """ 
    poly = division( poly, irreduciblePoly )[1]    # ??? Do you want the quotient or the rest???

    poly = map( lambda xx: xx % modulus, poly )
    # x % modulus... why this complication?
    # Why not x in GF(3) directly,
    # never use the same x again, although the namespace should be safe...

    return poly

T.<t> = PolynomialRing(ZZ, 'x')

# a = gen()
for a in ( [ 1,0,1,2,1,1 ] ,
           [ 1,0,0,2,0,2 ] ,
           [ 1,0,0,2,0,2 ] ,
           [ 2,1,0,2,0,2 ] ,
           [ 2,1,0,2,0,1 ] ,
           [ 2,1,0,2,0,1 ] ,
           [ 2,1,1,1,1,1 ] ,
           [ 2,1,0,1,2,1 ] ):
    Ya  = Y(a)
    rc  = ring_correct( a, ring, modulus )    # hard to guess what it codes
    Trc = T( rc )                             # but we make a polynomial out of it
    print ( "a = %s :: %5s ::\n\tYa =  %s :: Ya.list()  = %s\n\tTrc = %s :: Trc.list() = %s\n"
            % ( a, Ya.list() == Trc.list(), Ya, Ya.list(), Trc, Trc.list() ) )

There was one "important" error above, i replaced [ 0 ] with [ 1 ], since we want the rest, not the quotient. And we get in this deterministic context also the difference between Ya.list() and Trc.list() :

Ya  = x^4 + 2*x^3 + x^2 and Ya.list()  = [0, 0, 1, 2, 1] 
Trc = t^4 + 2*t^3 + t^2 and Trc.list() = [0, 0, 1, 2, 1]

# but

Ya  = 2*x^3 + 2 and Ya.list()  = [2, 0, 0, 2, 0]
Trc = 2*t^3 + 1 and Trc.list() = [1, 0, 0, 2]