Ask Your Question
0

Trying to understand a Univariate Quotient Polynomial Ring over Finite Field

asked 2017-02-06 08:59:35 -0600

Node.js gravatar image

updated 2017-02-11 23:08:05 -0600

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

Thanks in advance.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2017-03-05 10:11:53 -0600

dan_fulea gravatar image

updated 2017-03-05 10:20:58 -0600

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]
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-02-06 08:59:35 -0600

Seen: 151 times

Last updated: Mar 05