Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

asked 2017-02-06 15:59:35 +0100

Node.js gravatar image

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}$.

Not 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 am looking for something like this (the following is in SageMath)

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

Thanks in advance.

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}$.

Not 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 am looking for just want to know how SageMath does something like this (the following is in SageMath)this:

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

Thanks in advance.

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}$.

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

Thanks in advance.

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

Thanks in advance.

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

Thanks in advance.

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

Thanks in advance.

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

Thanks in advance.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59