Elements of Quotients of Univariate Polynomial Rings¶
EXAMPLES: We create a quotient of a univariate polynomial ring over \(\ZZ\).
sage: R.<x> = ZZ[]
sage: S.<a> = R.quotient(x^3 + 3*x - 1)
sage: 2 * a^3
-6*a + 2
>>> 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
R.<x> = ZZ[] S.<a> = R.quotient(x^3 + 3*x - 1) 2 * a^3
Next we make a univariate polynomial ring over \(\ZZ[x]/(x^3+3x-1)\).
sage: S1.<y> = S[]
>>> from sage.all import *
>>> S1 = S['y']; (y,) = S1._first_ngens(1)
S1.<y> = S[]
And, we quotient out that by \(y^2 + a\).
sage: T.<z> = S1.quotient(y^2 + a)
>>> from sage.all import *
>>> T = S1.quotient(y**Integer(2) + a, names=('z',)); (z,) = T._first_ngens(1)
T.<z> = S1.quotient(y^2 + a)
In the quotient \(z^2\) is \(-a\).
sage: z^2
-a
>>> from sage.all import *
>>> z**Integer(2)
-a
z^2
And since \(a^3 = -3x + 1\), we have:
sage: z^6
3*a - 1
>>> from sage.all import *
>>> z**Integer(6)
3*a - 1
z^6
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
>>> 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
R.<x> = PolynomialRing(Integers(9)) S.<a> = R.quotient(x^4 + 2*x^3 + x + 2) a^100
>>> 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
R.<x> = PolynomialRing(Integers(9)) S.<a> = R.quotient(x^4 + 2*x^3 + x + 2) a^100
sage: R.<x> = PolynomialRing(QQ)
sage: S.<a> = R.quotient(x^3 - 2)
sage: a
a
sage: a^3
2
>>> 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
R.<x> = PolynomialRing(QQ) S.<a> = R.quotient(x^3 - 2) a a^3
>>> 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
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: a == x
True
sage: a^3 == x^3
True
sage: x^3
x^3
sage: S(x^3)
2
>>> from sage.all import *
>>> a == x
True
>>> a**Integer(3) == x**Integer(3)
True
>>> x**Integer(3)
x^3
>>> S(x**Integer(3))
2
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,CommutativeRingElementElement of a quotient of a polynomial ring.
EXAMPLES:
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
>>> 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
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: 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
>>> 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
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: 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
>>> 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
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
selfto fieldhomomorphism from field to
self
EXAMPLES:
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
>>> 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
# 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: # 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
>>> 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
# 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: # 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')
>>> 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')
# 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: # 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
>>> 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
# 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
Trueifselfis invertible.Warning
Only implemented when the base ring is a field.
EXAMPLES:
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
>>> 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
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: 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
>>> 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
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: 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]
>>> 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]
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: 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]
>>> 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]
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 thematrix().EXAMPLES:
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
>>> 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
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: # 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
>>> 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
# 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: R.<x> = PolynomialRing(QQ) sage: S.<a> = R.quotient(x^3 - 389*x^2 + 2*x - 5) sage: a.norm() # needs sage.modules 5
>>> 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
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: # 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)
>>> 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)
# 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: R.<x> = PolynomialRing(QQ) sage: S.<a> = R.quotient(x^3 - 389*x^2 + 2*x - 5) sage: a.trace() # needs sage.modules 389
>>> 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
R.<x> = PolynomialRing(QQ) S.<a> = R.quotient(x^3 - 389*x^2 + 2*x - 5) a.trace() # needs sage.modules