# Trying to understand a Univariate Quotient Polynomial Ring over Finite Field

This might be a silly question and I am sorry for my lack of knowledge in abstract algebra.

I am trying to understand a Univariate Quotient Polynomial Ring over Finite Field but I want to make sure I am correct. So, if we have a polynomial, for example: $p = c_1 + c_2x^1 + c_3x^2 + \dots \ c_nx^{n-1}$ where $c_{i} \in \mathbb{Z}$.

Now to bring this polynomial into Quotient Polynomial Ring over Finite Field, for example: $r = x^{1024} + 1$ as a irreducible polynomial and some prime $q$ as a modulus.

First we need to find a quotient of division of $p / r$ and then for every coefficient in $p$ we need to $\bmod q$. Am I right? or completely off track?

I just want to know how SageMath does something like this:

modulus = 12289     # some prime
R.<X> = PolynomialRing(GF(modulus))
Y.<x> = R.quotient(X^(1024) + 1)


The reason I am asking this question is because I wrote something like this to simulate above SageMath code but it returns false:

import random
from itertools import izip
from math import fabs

dimension = 25         # degree of polynomials
modulus = 40961        # modulus

# ring = x^dimension + 1
ring = [1] + [0 for _ in range(dimension - 1)] + [1]

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

def division(N, D):
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 gen():
return [random.randint(100, 200) for _ in range(2^11)]

def ring_correct(poly, irreduciblePoly, modulus):
poly = division(poly, irreduciblePoly)[0]

poly = map(lambda x: x % modulus, poly)

return poly

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

a = gen()

print Y(a).list() == T(ring_correct(a, ring, modulus)).list()


edit retag close merge delete

Sort by » oldest newest most voted

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() .

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]

more