Elements of Quotients of Univariate Polynomial Rings¶

EXAMPLES: We create a quotient of a univariate polynomial ring over $Z$ .

Sage

sage: R.<x> = ZZ[]
sage: S.<a> = R.quotient(x^3 + 3*x - 1)
sage: 2 * a^3
-6*a + 2

Python

>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> S = R.quotient(x**Integer(3) + Integer(3)*x - Integer(1), names=('a',)); (a,) = S._first_ngens(1)
>>> Integer(2) * a**Integer(3)
-6*a + 2

Sage Live

R.<x> = ZZ[]
S.<a> = R.quotient(x^3 + 3*x - 1)
2 * a^3

Next we make a univariate polynomial ring over $Z [x] / (x^{3} + 3 x - 1)$ .

Sage

sage: S1.<y> = S[]

Python

>>> from sage.all import *
>>> S1 = S['y']; (y,) = S1._first_ngens(1)

Sage Live

S1.<y> = S[]

And, we quotient out that by $y^{2} + a$ .

Sage

sage: T.<z> = S1.quotient(y^2 + a)

Python

>>> from sage.all import *
>>> T = S1.quotient(y**Integer(2) + a, names=('z',)); (z,) = T._first_ngens(1)

Sage Live

T.<z> = S1.quotient(y^2 + a)

In the quotient $z^{2}$ is $- a$ .

Sage

sage: z^2
-a

Python

>>> from sage.all import *
>>> z**Integer(2)
-a

Sage Live

z^2

And since $a^{3} = - 3 x + 1$ , we have:

Sage

sage: z^6
3*a - 1

Python

>>> from sage.all import *
>>> z**Integer(6)
3*a - 1

Sage Live

z^6

Sage

sage: R.<x> = PolynomialRing(Integers(9))
sage: S.<a> = R.quotient(x^4 + 2*x^3 + x + 2)
sage: a^100
7*a^3 + 8*a + 7

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(9)), names=('x',)); (x,) = R._first_ngens(1)
>>> S = R.quotient(x**Integer(4) + Integer(2)*x**Integer(3) + x + Integer(2), names=('a',)); (a,) = S._first_ngens(1)
>>> a**Integer(100)
7*a^3 + 8*a + 7

Sage Live

R.<x> = PolynomialRing(Integers(9))
S.<a> = R.quotient(x^4 + 2*x^3 + x + 2)
a^100

Sage

sage: R.<x> = PolynomialRing(QQ)
sage: S.<a> = R.quotient(x^3 - 2)
sage: a
a
sage: a^3
2

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> S = R.quotient(x**Integer(3) - Integer(2), names=('a',)); (a,) = S._first_ngens(1)
>>> a
a
>>> a**Integer(3)
2

Sage Live

R.<x> = PolynomialRing(QQ)
S.<a> = R.quotient(x^3 - 2)
a
a^3

For the purposes of comparison in Sage the quotient element $a^{3}$ is equal to $x^{3}$ . This is because when the comparison is performed, the right element is coerced into the parent of the left element, and $x^{3}$ coerces to $a^{3}$ .

Sage

sage: a == x
True
sage: a^3 == x^3
True
sage: x^3
x^3
sage: S(x^3)
2

Python

>>> from sage.all import *
>>> a == x
True
>>> a**Integer(3) == x**Integer(3)
True
>>> x**Integer(3)
x^3
>>> S(x**Integer(3))
2

Sage Live

a == x
a^3 == x^3
x^3
S(x^3)

AUTHORS:

William Stein

class sage.rings.polynomial.polynomial_quotient_ring_element.PolynomialQuotientRingElement(parent, polynomial, check=True)[source]¶

Bases: Polynomial_singular_repr, CommutativeRingElement

Element of a quotient of a polynomial ring.

EXAMPLES:

Sage

sage: P.<x> = QQ[]
sage: Q.<xi> = P.quo([(x^2 + 1)])
sage: xi^2
-1
sage: singular(xi)                                                              # needs sage.libs.singular
xi
sage: (singular(xi)*singular(xi)).NF('std(0)')                                  # needs sage.libs.singular
-1

Python

>>> from sage.all import *
>>> P = QQ['x']; (x,) = P._first_ngens(1)
>>> Q = P.quo([(x**Integer(2) + Integer(1))], names=('xi',)); (xi,) = Q._first_ngens(1)
>>> xi**Integer(2)
-1
>>> singular(xi)                                                              # needs sage.libs.singular
xi
>>> (singular(xi)*singular(xi)).NF('std(0)')                                  # needs sage.libs.singular
-1

Sage Live

P.<x> = QQ[]
Q.<xi> = P.quo([(x^2 + 1)])
xi^2
singular(xi)                                                              # needs sage.libs.singular
(singular(xi)*singular(xi)).NF('std(0)')                                  # needs sage.libs.singular

charpoly(var)[source]¶

The characteristic polynomial of this element, which is by definition the characteristic polynomial of right multiplication by this element.

INPUT:

var – string; the variable name

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(QQ)
sage: S.<a> = R.quo(x^3 -389*x^2 + 2*x - 5)
sage: a.charpoly('X')                                                       # needs sage.modules
X^3 - 389*X^2 + 2*X - 5

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> S = R.quo(x**Integer(3) -Integer(389)*x**Integer(2) + Integer(2)*x - Integer(5), names=('a',)); (a,) = S._first_ngens(1)
>>> a.charpoly('X')                                                       # needs sage.modules
X^3 - 389*X^2 + 2*X - 5

Sage Live

R.<x> = PolynomialRing(QQ)
S.<a> = R.quo(x^3 -389*x^2 + 2*x - 5)
a.charpoly('X')                                                       # needs sage.modules

fcp(var='x')[source]¶

Return the factorization of the characteristic polynomial of this element.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(QQ)
sage: S.<a> = R.quotient(x^3 -389*x^2 + 2*x - 5)
sage: a.fcp('x')                                                            # needs sage.modules
x^3 - 389*x^2 + 2*x - 5
sage: S(1).fcp('y')                                                         # needs sage.modules
(y - 1)^3

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> S = R.quotient(x**Integer(3) -Integer(389)*x**Integer(2) + Integer(2)*x - Integer(5), names=('a',)); (a,) = S._first_ngens(1)
>>> a.fcp('x')                                                            # needs sage.modules
x^3 - 389*x^2 + 2*x - 5
>>> S(Integer(1)).fcp('y')                                                         # needs sage.modules
(y - 1)^3

Sage Live

R.<x> = PolynomialRing(QQ)
S.<a> = R.quotient(x^3 -389*x^2 + 2*x - 5)
a.fcp('x')                                                            # needs sage.modules
S(1).fcp('y')                                                         # needs sage.modules

field_extension(names)[source]¶

Given a polynomial with base ring a quotient ring, return a 3-tuple: a number field defined by the same polynomial, a homomorphism from its parent to the number field sending the generators to one another, and the inverse isomorphism.

INPUT:

names – name of generator of output field

OUTPUT:

field
homomorphism from self to field
homomorphism from field to self

EXAMPLES:

Sage

sage: # needs sage.rings.number_field
sage: R.<x> = PolynomialRing(QQ)
sage: S.<alpha> = R.quotient(x^3 - 2)
sage: F.<a>, f, g = alpha.field_extension()
sage: F
Number Field in a with defining polynomial x^3 - 2
sage: a = F.gen()
sage: f(alpha)
a
sage: g(a)
alpha

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> S = R.quotient(x**Integer(3) - Integer(2), names=('alpha',)); (alpha,) = S._first_ngens(1)
>>> F, f, g  = alpha.field_extension(names=('a',)); (a,) = F._first_ngens(1)
>>> F
Number Field in a with defining polynomial x^3 - 2
>>> a = F.gen()
>>> f(alpha)
a
>>> g(a)
alpha

Sage Live

# needs sage.rings.number_field
R.<x> = PolynomialRing(QQ)
S.<alpha> = R.quotient(x^3 - 2)
F.<a>, f, g = alpha.field_extension()
F
a = F.gen()
f(alpha)
g(a)

Over a finite field, the corresponding field extension is not a number field:

Sage

sage: # needs sage.rings.finite_rings
sage: R.<x> = GF(25,'b')['x']
sage: S.<a> = R.quo(x^3 + 2*x + 1)
sage: F.<b>, g, h = a.field_extension()
sage: h(b^2 + 3)
a^2 + 3
sage: g(x^2 + 2)
b^2 + 2

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> R = GF(Integer(25),'b')['x']; (x,) = R._first_ngens(1)
>>> S = R.quo(x**Integer(3) + Integer(2)*x + Integer(1), names=('a',)); (a,) = S._first_ngens(1)
>>> F, g, h  = a.field_extension(names=('b',)); (b,) = F._first_ngens(1)
>>> h(b**Integer(2) + Integer(3))
a^2 + 3
>>> g(x**Integer(2) + Integer(2))
b^2 + 2

Sage Live

# needs sage.rings.finite_rings
R.<x> = GF(25,'b')['x']
S.<a> = R.quo(x^3 + 2*x + 1)
F.<b>, g, h = a.field_extension()
h(b^2 + 3)
g(x^2 + 2)

We do an example involving a relative number field:

Sage

sage: # needs sage.rings.number_field
sage: R.<x> = QQ['x']
sage: K.<a> = NumberField(x^3 - 2)
sage: S.<X> = K['X']
sage: Q.<b> = S.quo(X^3 + 2*X + 1)
sage: F, g, h = b.field_extension('c')

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> K = NumberField(x**Integer(3) - Integer(2), names=('a',)); (a,) = K._first_ngens(1)
>>> S = K['X']; (X,) = S._first_ngens(1)
>>> Q = S.quo(X**Integer(3) + Integer(2)*X + Integer(1), names=('b',)); (b,) = Q._first_ngens(1)
>>> F, g, h = b.field_extension('c')

Sage Live

# needs sage.rings.number_field
R.<x> = QQ['x']
K.<a> = NumberField(x^3 - 2)
S.<X> = K['X']
Q.<b> = S.quo(X^3 + 2*X + 1)
F, g, h = b.field_extension('c')

Another more awkward example:

Sage

sage: # needs sage.rings.number_field
sage: R.<x> = QQ['x']
sage: K.<a> = NumberField(x^3 - 2)
sage: S.<X> = K['X']
sage: f = (X+a)^3 + 2*(X+a) + 1
sage: f
X^3 + 3*a*X^2 + (3*a^2 + 2)*X + 2*a + 3
sage: Q.<z> = S.quo(f)
sage: F.<w>, g, h = z.field_extension()
sage: c = g(z)
sage: f(c)
0
sage: h(g(z))
z
sage: g(h(w))
w

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> K = NumberField(x**Integer(3) - Integer(2), names=('a',)); (a,) = K._first_ngens(1)
>>> S = K['X']; (X,) = S._first_ngens(1)
>>> f = (X+a)**Integer(3) + Integer(2)*(X+a) + Integer(1)
>>> f
X^3 + 3*a*X^2 + (3*a^2 + 2)*X + 2*a + 3
>>> Q = S.quo(f, names=('z',)); (z,) = Q._first_ngens(1)
>>> F, g, h  = z.field_extension(names=('w',)); (w,) = F._first_ngens(1)
>>> c = g(z)
>>> f(c)
0
>>> h(g(z))
z
>>> g(h(w))
w

Sage Live

# needs sage.rings.number_field
R.<x> = QQ['x']
K.<a> = NumberField(x^3 - 2)
S.<X> = K['X']
f = (X+a)^3 + 2*(X+a) + 1
f
Q.<z> = S.quo(f)
F.<w>, g, h = z.field_extension()
c = g(z)
f(c)
h(g(z))
g(h(w))

AUTHORS:

Craig Citro (2006-08-06)
William Stein (2006-08-06)

is_unit()[source]¶

Return True if self is invertible.

Warning

Only implemented when the base ring is a field.

EXAMPLES:

Sage

sage: R.<x> = QQ[]
sage: S.<y> = R.quotient(x^2 + 2*x + 1)
sage: (2*y).is_unit()
True
sage: (y + 1).is_unit()
False

Python

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> S = R.quotient(x**Integer(2) + Integer(2)*x + Integer(1), names=('y',)); (y,) = S._first_ngens(1)
>>> (Integer(2)*y).is_unit()
True
>>> (y + Integer(1)).is_unit()
False

Sage Live

R.<x> = QQ[]
S.<y> = R.quotient(x^2 + 2*x + 1)
(2*y).is_unit()
(y + 1).is_unit()

lift()[source]¶

Return lift of this polynomial quotient ring element to the unique equivalent polynomial of degree less than the modulus.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(QQ)
sage: S.<a> = R.quotient(x^3 - 2)
sage: b = a^2 - 3
sage: b
a^2 - 3
sage: b.lift()
x^2 - 3

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> S = R.quotient(x**Integer(3) - Integer(2), names=('a',)); (a,) = S._first_ngens(1)
>>> b = a**Integer(2) - Integer(3)
>>> b
a^2 - 3
>>> b.lift()
x^2 - 3

Sage Live

R.<x> = PolynomialRing(QQ)
S.<a> = R.quotient(x^3 - 2)
b = a^2 - 3
b
b.lift()

list(copy=True)[source]¶

Return list of the elements of self, of length the same as the degree of the quotient polynomial ring.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(QQ)
sage: S.<a> = R.quotient(x^3 + 2*x - 5)
sage: a^10
-134*a^2 - 35*a + 300
sage: (a^10).list()
[300, -35, -134]

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> S = R.quotient(x**Integer(3) + Integer(2)*x - Integer(5), names=('a',)); (a,) = S._first_ngens(1)
>>> a**Integer(10)
-134*a^2 - 35*a + 300
>>> (a**Integer(10)).list()
[300, -35, -134]

Sage Live

R.<x> = PolynomialRing(QQ)
S.<a> = R.quotient(x^3 + 2*x - 5)
a^10
(a^10).list()

matrix()[source]¶

The matrix of right multiplication by this element on the power basis for the quotient ring.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(QQ)
sage: S.<a> = R.quotient(x^3 + 2*x - 5)
sage: a.matrix()                                                            # needs sage.modules
[ 0  1  0]
[ 0  0  1]
[ 5 -2  0]

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> S = R.quotient(x**Integer(3) + Integer(2)*x - Integer(5), names=('a',)); (a,) = S._first_ngens(1)
>>> a.matrix()                                                            # needs sage.modules
[ 0  1  0]
[ 0  0  1]
[ 5 -2  0]

Sage Live

R.<x> = PolynomialRing(QQ)
S.<a> = R.quotient(x^3 + 2*x - 5)
a.matrix()                                                            # needs sage.modules

minpoly()[source]¶

The minimal polynomial of this element, which is by definition the minimal polynomial of the matrix() of this element.

ALGORITHM: Use minpoly_mod() if possible, otherwise compute the minimal polynomial of the matrix().

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(QQ)
sage: S.<a> = R.quotient(x^3 + 2*x - 5)
sage: (a + 123).minpoly()                                                   # needs sage.modules
x^3 - 369*x^2 + 45389*x - 1861118
sage: (a + 123).matrix().minpoly()                                          # needs sage.modules
x^3 - 369*x^2 + 45389*x - 1861118

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> S = R.quotient(x**Integer(3) + Integer(2)*x - Integer(5), names=('a',)); (a,) = S._first_ngens(1)
>>> (a + Integer(123)).minpoly()                                                   # needs sage.modules
x^3 - 369*x^2 + 45389*x - 1861118
>>> (a + Integer(123)).matrix().minpoly()                                          # needs sage.modules
x^3 - 369*x^2 + 45389*x - 1861118

Sage Live

R.<x> = PolynomialRing(QQ)
S.<a> = R.quotient(x^3 + 2*x - 5)
(a + 123).minpoly()                                                   # needs sage.modules
(a + 123).matrix().minpoly()                                          # needs sage.modules

One useful application of this function is to compute a minimal polynomial of a finite-field element over an intermediate extension, rather than the absolute minimal polynomial over the prime field:

Sage

sage: # needs sage.rings.finite_rings
sage: F2.<i> = GF((431,2), modulus=[1,0,1])
sage: F6.<u> = F2.extension(3)
sage: (u + 1).minpoly()                                                     # needs sage.modules
x^6 + 425*x^5 + 19*x^4 + 125*x^3 + 189*x^2 + 239*x + 302
sage: ext = F6.over(F2)                                                     # needs sage.modules
sage: ext(u + 1).minpoly()  # indirect doctest                              # needs sage.modules # random
x^3 + (396*i + 428)*x^2 + (80*i + 39)*x + 9*i + 178

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F2 = GF((Integer(431),Integer(2)), modulus=[Integer(1),Integer(0),Integer(1)], names=('i',)); (i,) = F2._first_ngens(1)
>>> F6 = F2.extension(Integer(3), names=('u',)); (u,) = F6._first_ngens(1)
>>> (u + Integer(1)).minpoly()                                                     # needs sage.modules
x^6 + 425*x^5 + 19*x^4 + 125*x^3 + 189*x^2 + 239*x + 302
>>> ext = F6.over(F2)                                                     # needs sage.modules
>>> ext(u + Integer(1)).minpoly()  # indirect doctest                              # needs sage.modules # random
x^3 + (396*i + 428)*x^2 + (80*i + 39)*x + 9*i + 178

Sage Live

# needs sage.rings.finite_rings
F2.<i> = GF((431,2), modulus=[1,0,1])
F6.<u> = F2.extension(3)
(u + 1).minpoly()                                                     # needs sage.modules
ext = F6.over(F2)                                                     # needs sage.modules
ext(u + 1).minpoly()  # indirect doctest                              # needs sage.modules # random

norm()[source]¶

The norm of this element, which is the determinant of the matrix of right multiplication by this element.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(QQ)
sage: S.<a> = R.quotient(x^3 - 389*x^2 + 2*x - 5)
sage: a.norm()                                                              # needs sage.modules
5

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> S = R.quotient(x**Integer(3) - Integer(389)*x**Integer(2) + Integer(2)*x - Integer(5), names=('a',)); (a,) = S._first_ngens(1)
>>> a.norm()                                                              # needs sage.modules
5

Sage Live

R.<x> = PolynomialRing(QQ)
S.<a> = R.quotient(x^3 - 389*x^2 + 2*x - 5)
a.norm()                                                              # needs sage.modules

rational_reconstruction(*args, **kwargs)[source]¶

Compute a rational reconstruction of this polynomial quotient ring element to its cover ring.

This method is a thin convenience wrapper around Polynomial.rational_reconstruction().

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: R.<x> = GF(65537)[]
sage: m = (x^11 + 25345*x^10 + 10956*x^9 + 13873*x^8 + 23962*x^7
....:      + 17496*x^6 + 30348*x^5 + 7440*x^4 + 65438*x^3 + 7676*x^2
....:      + 54266*x + 47805)
sage: f = (20437*x^10 + 62630*x^9 + 63241*x^8 + 12820*x^7 + 42171*x^6
....:      + 63091*x^5 + 15288*x^4 + 32516*x^3 + 2181*x^2 + 45236*x + 2447)
sage: f_mod_m = R.quotient(m)(f)
sage: f_mod_m.rational_reconstruction()
(51388*x^5 + 29141*x^4 + 59341*x^3 + 7034*x^2 + 14152*x + 23746,
 x^5 + 15208*x^4 + 19504*x^3 + 20457*x^2 + 11180*x + 28352)

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> R = GF(Integer(65537))['x']; (x,) = R._first_ngens(1)
>>> m = (x**Integer(11) + Integer(25345)*x**Integer(10) + Integer(10956)*x**Integer(9) + Integer(13873)*x**Integer(8) + Integer(23962)*x**Integer(7)
...      + Integer(17496)*x**Integer(6) + Integer(30348)*x**Integer(5) + Integer(7440)*x**Integer(4) + Integer(65438)*x**Integer(3) + Integer(7676)*x**Integer(2)
...      + Integer(54266)*x + Integer(47805))
>>> f = (Integer(20437)*x**Integer(10) + Integer(62630)*x**Integer(9) + Integer(63241)*x**Integer(8) + Integer(12820)*x**Integer(7) + Integer(42171)*x**Integer(6)
...      + Integer(63091)*x**Integer(5) + Integer(15288)*x**Integer(4) + Integer(32516)*x**Integer(3) + Integer(2181)*x**Integer(2) + Integer(45236)*x + Integer(2447))
>>> f_mod_m = R.quotient(m)(f)
>>> f_mod_m.rational_reconstruction()
(51388*x^5 + 29141*x^4 + 59341*x^3 + 7034*x^2 + 14152*x + 23746,
 x^5 + 15208*x^4 + 19504*x^3 + 20457*x^2 + 11180*x + 28352)

Sage Live

# needs sage.rings.finite_rings
R.<x> = GF(65537)[]
m = (x^11 + 25345*x^10 + 10956*x^9 + 13873*x^8 + 23962*x^7
     + 17496*x^6 + 30348*x^5 + 7440*x^4 + 65438*x^3 + 7676*x^2
     + 54266*x + 47805)
f = (20437*x^10 + 62630*x^9 + 63241*x^8 + 12820*x^7 + 42171*x^6
     + 63091*x^5 + 15288*x^4 + 32516*x^3 + 2181*x^2 + 45236*x + 2447)
f_mod_m = R.quotient(m)(f)
f_mod_m.rational_reconstruction()

trace()[source]¶

The trace of this element, which is the trace of the matrix of right multiplication by this element.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(QQ)
sage: S.<a> = R.quotient(x^3 - 389*x^2 + 2*x - 5)
sage: a.trace()                                                             # needs sage.modules
389

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> S = R.quotient(x**Integer(3) - Integer(389)*x**Integer(2) + Integer(2)*x - Integer(5), names=('a',)); (a,) = S._first_ngens(1)
>>> a.trace()                                                             # needs sage.modules
389

Sage Live

R.<x> = PolynomialRing(QQ)
S.<a> = R.quotient(x^3 - 389*x^2 + 2*x - 5)
a.trace()                                                             # needs sage.modules