Coverage for local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_quotient

Univariate Quotient Polynomial Ring in xbar over Univariate Quotient Polynomial Ring in y2 over Finite Field of size 2 with modulus y^2 + y + 1 with modulus x^3 + 1

Next we create a number field, but viewed as a quotient of a

polynomial ring over `\QQ`::

sage: R = PolynomialRing(RationalField(), 'x'); x = R.gen()

sage: S = R.quotient(x^3 + 2*x - 5, 'a')

sage: S

Univariate Quotient Polynomial Ring in a over Rational Field with modulus x^3 + 2*x - 5

sage: S.is_field()

True

sage: S.degree()

There are conversion functions for easily going back and forth

between quotients of polynomial rings over `\QQ` and

number fields::

sage: K = S.number_field(); K

Number Field in a with defining polynomial x^3 + 2*x - 5

sage: K.polynomial_quotient_ring()

Univariate Quotient Polynomial Ring in a over Rational Field with modulus x^3 + 2*x - 5

The leading coefficient must be a unit (but need not be 1).

sage: R = PolynomialRing(Integers(9), 'x'); x = R.gen()

sage: S = R.quotient(2*x^4 + 2*x^3 + x + 2, 'a')

sage: S = R.quotient(3*x^4 + 2*x^3 + x + 2, 'a')

Traceback (most recent call last):

...

TypeError: polynomial must have unit leading coefficient

Another example::

sage: R.<x> = PolynomialRing(IntegerRing())

sage: f = x^2 + 1

sage: R.quotient(f)

Univariate Quotient Polynomial Ring in xbar over Integer Ring with modulus x^2 + 1

This shows that the issue at :trac:`5482` is solved::

sage: R.<x> = PolynomialRing(QQ)

sage: f = x^2-1

sage: R.quotient_by_principal_ideal(f)

Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^2 - 1

"""

if not isinstance(ring, PolynomialRing_commutative):

raise TypeError("ring must be a polynomial ring")

if not isinstance(polynomial, polynomial_element.Polynomial):

raise TypeError("must be a polynomial")

if not polynomial.parent() == ring:

raise TypeError("polynomial must be in ring")

c = polynomial.leading_coefficient()

if not c.is_unit():

raise TypeError("polynomial must have unit leading coefficient")

if names is None:

names = tuple([x + 'bar' for x in ring.variable_names()])

else:

names = normalize_names(ring.ngens(), names)

R = ring.base_ring()

if isinstance(R, IntegralDomain):

try:

if polynomial.is_irreducible():

if isinstance(R, Field):

return PolynomialQuotientRing_field(ring, polynomial, names)

else:

return PolynomialQuotientRing_domain(ring, polynomial, names)

except NotImplementedError: # is_irreducible sometimes not implemented

pass

return PolynomialQuotientRing_generic(ring, polynomial, names)

def is_PolynomialQuotientRing(x):

return isinstance(x, PolynomialQuotientRing_generic)

class PolynomialQuotientRing_generic(CommutativeRing):

"""

Quotient of a univariate polynomial ring by an ideal.

EXAMPLES::

sage: R.<x> = PolynomialRing(Integers(8)); R

Univariate Polynomial Ring in x over Ring of integers modulo 8

sage: S.<xbar> = R.quotient(x^2 + 1); S

Univariate Quotient Polynomial Ring in xbar over Ring of integers modulo 8 with modulus x^2 + 1

We demonstrate object persistence.

sage: loads(S.dumps()) == S

True

sage: loads(xbar.dumps()) == xbar

True

We create some sample homomorphisms;

sage: R.<x> = PolynomialRing(ZZ)

sage: S = R.quo(x^2-4)

sage: f = S.hom([2])

sage: f

Ring morphism:

From: Univariate Quotient Polynomial Ring in xbar over Integer Ring with modulus x^2 - 4

To: Integer Ring

Defn: xbar |--> 2

sage: f(x)

sage: f(x^2 - 4)

sage: f(x^2)

TESTS:

By trac ticket :trac:`11900`, polynomial quotient rings use Sage's

category framework. They do so in an unusual way: During their

initialisation, they are declared to be objects in the category of

quotients of commutative algebras over a base ring. However, if it

is tested whether a quotient ring is actually a field, the

category might be refined, which also includes a change of the

class of the quotient ring and its newly created elements.

Thus, in order to document that this works fine, we go into some detail::

sage: P.<x> = QQ[]

sage: Q = P.quotient(x^2+2)

sage: Q.category()

Category of commutative no zero divisors quotients of algebras over Rational Field

We verify that the elements belong to the correct element class.

Also, we list the attributes that are provided by the element

class of the category, and store the current class of the quotient

ring::

sage: isinstance(Q.an_element(),Q.element_class)

True

sage: [s for s in dir(Q.category().element_class) if not s.startswith('_')]

['cartesian_product', 'inverse_of_unit', 'is_idempotent', 'is_one', 'is_unit', 'lift', 'powers']

sage: first_class = Q.__class__

We try to find out whether `Q` is a field. Indeed it is, and thus its category,

including its class and element class, is changed accordingly::

sage: Q in Fields()

True

sage: Q.category()

Category of commutative division no zero divisors

quotients of algebras over Rational Field

sage: first_class == Q.__class__

False

sage: [s for s in dir(Q.category().element_class) if not s.startswith('_')]

['cartesian_product',

'euclidean_degree',

'factor',

'gcd',

'inverse_of_unit',

'is_idempotent',

'is_one',

'is_unit',

'lcm',

'lift',

'powers',

'quo_rem',

'xgcd']

As one can see, the elements are now inheriting additional

methods: lcm and gcd. Even though ``Q.an_element()`` belongs to

the old and not to the new element class, it still inherits the

new methods from the category of fields, thanks to

:meth:`Element.__getattr__`::

sage: e = Q.an_element()

sage: isinstance(e, Q.element_class)

False

sage: e.gcd(e+1)

The test suite passes. However, we have to skip the test for its elements,

since `an_element` has been cached in the call above and its class does not

match the new category's element class anymore::

sage: TestSuite(Q).run(skip=['_test_elements'])

Newly created elements are fine, though, and their test suite passes::

sage: TestSuite(Q(x)).run()

sage: isinstance(Q(x), Q.element_class)

True

"""

Element = PolynomialQuotientRingElement

def __init__(self, ring, polynomial, name=None, category=None):

"""

TESTS::

sage: R.<x> = PolynomialRing(ZZ)

sage: S = R.quo(x^2-4)

sage: from sage.rings.polynomial.polynomial_quotient_ring import PolynomialQuotientRing_generic

sage: S == PolynomialQuotientRing_generic(R,x^2-4,'xbar')

True

"""

if not isinstance(ring, PolynomialRing_commutative):

raise TypeError("R must be a univariate polynomial ring.")

if not isinstance(polynomial, polynomial_element.Polynomial):

raise TypeError("f must be a Polynomial")

if polynomial.parent() != ring:

raise TypeError("f must have parent R")

self.__ring = ring

self.__polynomial = polynomial

category = CommutativeAlgebras(ring.base_ring()).Quotients().or_subcategory(category)

CommutativeRing.__init__(self, ring, names=name, category=category)

def __reduce__(self):

"""

TESTS:

Note the polynomial quotient rings are not unique parent structures::

sage: P.<x> = QQ[]

sage: R.<y> = P[]

sage: Q = R.quo([(y^2+1)])

sage: Q is loads(dumps(Q))

False

sage: Q == loads(dumps(Q))

True

"""

return PolynomialQuotientRing_generic, (self.__ring, self.__polynomial, self.variable_names())

def _element_constructor_(self, x):

"""

Convert x into this quotient ring. Anything that can be converted into

the polynomial ring can be converted into the quotient.

INPUT:

- ``x`` - object to be converted

OUTPUT: an element obtained by converting x into this ring.

EXAMPLES::

sage: R.<x> = PolynomialRing(QQ)

sage: S.<alpha> = R.quotient(x^3-3*x+1)

sage: S(x)

alpha

sage: S(x^3)

3*alpha - 1

sage: S([1,2])

2*alpha + 1

sage: S([1,2,3,4,5])

18*alpha^2 + 9*alpha - 3

sage: S(S.gen()+1)

alpha + 1

sage: S(S.gen()^10+1)

90*alpha^2 - 109*alpha + 28

TESTS:

Conversion should work even if there is no coercion.

This was fixed in :trac:`8800`::

sage: P.<x> = QQ[]

sage: Q1 = P.quo([(x^2+1)^2*(x^2-3)])

sage: Q = P.quo([(x^2+1)^2])

sage: Q1.has_coerce_map_from(Q)

False

sage: Q1(Q.gen())

xbar

Here we test against several issues discussed in :trac:`8992`::

sage: P.<x> = QQ[]

sage: Q1 = P.quo([(x^2+1)^2*(x^2-3)])

sage: Q2 = P.quo([(x^2+1)^2*(x^5+3)])

sage: p = Q1.gen() + Q2.gen()

sage: p

2*xbar

sage: p.parent()

Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^4 + 2*x^2 + 1

sage: p.parent()('xbar')

xbar

Note that the result of string conversion has the correct parent, even

when the given string suggests an element of the cover ring or the base

ring::

sage: a = Q1('x'); a

xbar

sage: a.parent() is Q1

True

sage: b = Q1('1'); b

sage: b.parent() is Q1

True

Conversion may lift an element of one quotient ring to the base ring of

another quotient ring::

sage: R.<y> = P[]

sage: Q3 = R.quo([(y^2+1)])

sage: Q3(Q1.gen())

sage: Q3.has_coerce_map_from(Q1)

False

String conversion takes into account both the generators of the quotient

ring and its base ring::

sage: Q3('x*ybar^2')

-x

"""

P = parent(x)

if P is self:

return x

if not isinstance(x, six.string_types):

try:

return self.element_class(self, self.__ring(x) , check=True)

except TypeError:

xlift = getattr(x,'lift',None)

if xlift is not None: # duck typing for quotient ring elements

return self.element_class(self, self.__ring(x.lift()), check=False)

# The problem with the string representation is that it could in principle

# mix elements of self with elements of self's cover ring. We therefore

# resort to sage_eval.

# Interpretation in self has priority over interpretation in self.__ring

try:

out = sage_eval(x, GenDictWithBasering(self,self.gens_dict()))

if out.parent() is not self:

return self(out)

return out

except (TypeError, NameError):

pass

try:

return self.element_class(self, self.__ring(x), check=False)

except TypeError:

raise TypeError("unable to convert %r to an element of %s"%(x, self))

def _coerce_map_from_(self, R):

r"""

Return a coerce map from ``R``.

Anything coercing into the underlying polynomial ring coerces into this

quotient. Furthermore, for quotients `R=A[x]/(f)` and `S=B[x]/(g)` with

a coercion `R\to S` there is a coercion iff `f` divides `g`.

AUTHOR:

- Simon King (2010-12): :trac:`8800`

TESTS::

sage: P5.<x> = GF(5)[]

sage: Q = P5.quo([(x^2+1)^2])

sage: P.<x> = ZZ[]

sage: Q1 = P.quo([(x^2+1)^2*(x^2-3)])

sage: Q2 = P.quo([(x^2+1)^2*(x^5+3)])

sage: Q.has_coerce_map_from(Q1) #indirect doctest

True

sage: Q1.has_coerce_map_from(Q)

False

sage: Q1.has_coerce_map_from(Q2)

False

The following tests against a bug fixed in :trac:`8992`::

sage: P.<x> = QQ[]

sage: Q1 = P.quo([(x^2+1)^2*(x^2-3)])

sage: R.<y> = P[]

sage: Q2 = R.quo([(y^2+1)])

sage: Q2.has_coerce_map_from(Q1)

False

"""

if self.__ring.has_coerce_map_from(R):

return True

if isinstance(R, PolynomialQuotientRing_generic):

try:

if not self.__polynomial.divides(R.modulus()):

return False

except (ZeroDivisionError,ArithmeticError):

return False

from sage.all import Hom

parent = Hom(R, self, category=self.category()._meet_(R.category()))

return parent.__make_element_class__(PolynomialQuotientRing_coercion)(R, self, category=parent.homset_category())

def _is_valid_homomorphism_(self, codomain, im_gens):

try:

# We need that elements of the base ring of the polynomial

# ring map canonically into codomain.

codomain._coerce_(self.base_ring()(1))

# We also need that the polynomial modulus maps to 0.

f = self.modulus()

return codomain(f(im_gens[0])) == 0

except (TypeError, ValueError):

return False

def _coerce_impl(self, x):

"""

Return the coercion of x into this polynomial quotient ring.

The rings that coerce into the quotient ring canonically are:

- this ring

- any canonically isomorphic ring

- anything that coerces into the ring of which this is the

quotient

"""

if isinstance(x, PolynomialQuotientRingElement):

if x.parent() == self:

return self.element_class(self, self.__ring(x.lift()), check=False)

# any ring that coerces to the base ring of this polynomial ring.

return self._coerce_try(x, [self.polynomial_ring()])

############################################

## Methods to make the category framework happy...

retract = _coerce_impl

ambient = CommutativeRing.base

def lift(self, x):

"""

Return an element of the ambient ring mapping to the given argument.

EXAMPLES::

sage: P.<x> = QQ[]

sage: Q = P.quotient(x^2+2)

sage: Q.lift(Q.0^3)

-2*x

sage: Q(-2*x)

-2*xbar

sage: Q.0^3

-2*xbar

"""

return x.lift()

def __eq__(self, other):

"""

Check whether ``self`` is equal to ``other``.

EXAMPLES::

sage: Rx.<x> = PolynomialRing(QQ)

sage: Ry.<y> = PolynomialRing(QQ)

sage: Rx == Ry

False

sage: Qx = Rx.quotient(x^2+1)

sage: Qy = Ry.quotient(y^2+1)

sage: Qx == Qy

False

sage: Qx == Qx

True

sage: Qz = Rx.quotient(x^2+1)

sage: Qz == Qx

True

"""

if not isinstance(other, PolynomialQuotientRing_generic):

return False

return (self.polynomial_ring() == other.polynomial_ring() and

self.modulus() == other.modulus())

def __ne__(self, other):

"""

Check whether ``self`` is not equal to ``other``.

EXAMPLES::

sage: Rx.<x> = PolynomialRing(QQ)

sage: Ry.<y> = PolynomialRing(QQ)

sage: Rx != Ry

True

sage: Qx = Rx.quotient(x^2+1)

sage: Qy = Ry.quotient(y^2+1)

sage: Qx != Qy

True

sage: Qx != Qx

False

sage: Qz = Rx.quotient(x^2+1)

sage: Qz != Qx

False

"""

return not (self == other)

def _singular_init_(self, S=None):

"""

Represent ``self`` in the Singular interface.

TESTS::

sage: P.<x> = QQ[]

sage: Q = P.quo([(x^2+1)])

sage: singular(Q) # indirect doctest

polynomial ring, over a field, global ordering

// coefficients: QQ

// number of vars : 1

// block 1 : ordering lp

// : names xbar

// block 2 : ordering C

// quotient ring from ideal

_[1]=xbar^2+1

sage: singular(Q.gen())

xbar

"""

if S is None:

from sage.all import singular

S = singular

Rpoly = S(self.polynomial_ring())

Rpoly.set_ring()

modulus = S(self.modulus()) # should live in Rpoly

Rtmp = S(self.polynomial_ring().change_var(self.variable_name()))

Rtmp.set_ring()

self.__singular = S("ideal(fetch(%s,%s))"%(Rpoly.name(),modulus.name()),"qring")

return self.__singular

def _repr_(self):

return "Univariate Quotient Polynomial Ring in %s over %s with modulus %s"%(

self.variable_name(), self.base_ring(), self.modulus())

def construction(self):

"""

Functorial construction of ``self``

EXAMPLES::

sage: P.<t>=ZZ[]

sage: Q = P.quo(5+t^2)

sage: F, R = Q.construction()

sage: F(R) == Q

True

sage: P.<t> = GF(3)[]

sage: Q = P.quo([2+t^2])

sage: F, R = Q.construction()

sage: F(R) == Q

True

AUTHOR:

-- Simon King (2010-05)

"""

from sage.categories.pushout import QuotientFunctor

return QuotientFunctor([self.modulus()]*self.base(),self.variable_names()), self.base()

@cached_method

def base_ring(self):

r"""

Return the base ring of the polynomial ring, of which this ring is

a quotient.

EXAMPLES:

The base ring of

`\ZZ[z]/(z^3 + z^2 + z + 1)` is

`\ZZ`.

sage: R.<z> = PolynomialRing(ZZ)

sage: S.<beta> = R.quo(z^3 + z^2 + z + 1)

sage: S.base_ring()

Integer Ring

Next we make a polynomial quotient ring over `S` and ask

for its base ring.

sage: T.<t> = PolynomialRing(S)

sage: W = T.quotient(t^99 + 99)

sage: W.base_ring()

Univariate Quotient Polynomial Ring in beta over Integer Ring with modulus z^3 + z^2 + z + 1

"""

return self.__ring.base_ring()

def cardinality(self):

"""

Return the number of elements of this quotient ring.

``order`` is an alias of ``cardinality``.

EXAMPLES::

sage: R.<x> = ZZ[]

sage: R.quo(1).cardinality()

sage: R.quo(x^3-2).cardinality()

+Infinity

sage: R.quo(1).order()

sage: R.quo(x^3-2).order()

+Infinity

sage: R.<x> = GF(9,'a')[]

sage: R.quo(2*x^3+x+1).cardinality()

729

sage: GF(9,'a').extension(2*x^3+x+1).cardinality()

729

sage: R.quo(2).cardinality()

TESTS::

sage: parent(QQ['x'].quo(1).cardinality())

Integer Ring

sage: parent(QQ['x'].quo(1).order())

Integer Ring

"""

if not self.is_finite():

from sage.rings.infinity import Infinity

return Infinity

f = self.modulus()

# Two cases where the quotient is finite (see is_finite())

# 1) R[x]/(1)

if f.degree() == 0:

from sage.rings.integer_ring import ZZ

return ZZ.one()

# 2) F[x]/(f) where F is finite

else:

return self.base_ring().cardinality() ** f.degree()

order = cardinality

def is_finite(self):

"""

Return whether or not this quotient ring is finite.

EXAMPLES::

sage: R.<x> = ZZ[]

sage: R.quo(1).is_finite()

True

sage: R.quo(x^3-2).is_finite()

False

sage: R.<x> = GF(9,'a')[]

sage: R.quo(2*x^3+x+1).is_finite()

True

sage: R.quo(2).is_finite()

True

sage: P.<v> = GF(2)[]

sage: P.quotient(v^2-v).is_finite()

True

"""

f = self.modulus()

# note: the constructor assumes that the leading coefficient is a

# unit. However, this function would be very wrong if otherwise.

# As a safety measure, we check that again here.

assert f.leading_coefficient().is_unit()

return f.degree() == 0 or self.base_ring().is_finite()

def __iter__(self):

r"""

EXAMPLES::

sage: R.<x> = GF(3)[]

sage: Q = R.quo(x^3 - x^2 - x - 1)

sage: list(Q)

[0,

xbar,

xbar + 1,

xbar + 2,

2*xbar,

...

2*xbar^2 + 2*xbar + 1,

2*xbar^2 + 2*xbar + 2]

sage: len(_) == Q.cardinality() == 27

True

"""

if not self.is_finite():

raise NotImplementedError('not possible to iterate through infinite quotient')

R = self.polynomial_ring()

yield self.zero()

for i in range(self.modulus().degree()):

for p in R.polynomials(of_degree=i):

yield self(p)

def characteristic(self):

"""

Return the characteristic of this quotient ring.

This is always the same as the characteristic of the base ring.

EXAMPLES::

sage: R.<z> = PolynomialRing(ZZ)

sage: S.<a> = R.quo(z - 19)

sage: S.characteristic()

sage: R.<x> = PolynomialRing(GF(9,'a'))

sage: S = R.quotient(x^3 + 1)

sage: S.characteristic()

"""

return self.base_ring().characteristic()

def degree(self):

"""

Return the degree of this quotient ring. The degree is the degree

of the polynomial that we quotiented out by.

EXAMPLES::

sage: R.<x> = PolynomialRing(GF(3))

sage: S = R.quotient(x^2005 + 1)

sage: S.degree()

2005

"""

return self.modulus().degree()

def discriminant(self, v=None):

"""

Return the discriminant of this ring over the base ring. This is by

definition the discriminant of the polynomial that we quotiented

out by.

EXAMPLES::

sage: R.<x> = PolynomialRing(QQ)

sage: S = R.quotient(x^3 + x^2 + x + 1)

sage: S.discriminant()

-16

sage: S = R.quotient((x + 1) * (x + 1))

sage: S.discriminant()

The discriminant of the quotient polynomial ring need not equal the

discriminant of the corresponding number field, since the

discriminant of a number field is by definition the discriminant of

the ring of integers of the number field::

sage: S = R.quotient(x^2 - 8)

sage: S.number_field().discriminant()

sage: S.discriminant()

"""

return self.modulus().discriminant()

def gen(self, n=0):

"""

Return the generator of this quotient ring. This is the equivalence

class of the image of the generator of the polynomial ring.

EXAMPLES::

sage: R.<x> = PolynomialRing(QQ)

sage: S = R.quotient(x^2 - 8, 'gamma')

sage: S.gen()

gamma

"""

if n != 0:

raise IndexError("Only one generator.")

try:

return self.__gen

except AttributeError:

self.__gen = self(self.polynomial_ring().gen())

return self.__gen

def is_field(self, proof = True):

"""

Return whether or not this quotient ring is a field.

EXAMPLES::

sage: R.<z> = PolynomialRing(ZZ)

sage: S = R.quo(z^2-2)

sage: S.is_field()

False

sage: R.<x> = PolynomialRing(QQ)

sage: S = R.quotient(x^2 - 2)

sage: S.is_field()

True

If proof is ``True``, requires the ``is_irreducible`` method of the

modulus to be implemented::

sage: R1.<x> = Qp(2)[]

sage: F1 = R1.quotient_ring(x^2+x+1)

sage: R2.<x> = F1[]

sage: F2 = R2.quotient_ring(x^2+x+1)

sage: F2.is_field()

Traceback (most recent call last):

...

NotImplementedError: can not rewrite Univariate Quotient Polynomial Ring in xbar over 2-adic Field with capped relative precision 20 with modulus (1 + O(2^20))*x^2 + (1 + O(2^20))*x + (1 + O(2^20)) as an isomorphic ring

sage: F2.is_field(proof = False)

False

"""

ret = self.base_ring().is_field(proof)

try:

ret = ret and self.modulus().is_irreducible()

except NotImplementedError:

if proof: raise

else: ret = False

if ret:

from sage.categories.all import Fields

self._refine_category_(Fields())

return ret

def krull_dimension(self):

return self.base_ring().krull_dimension()

def modulus(self):

"""

Return the polynomial modulus of this quotient ring.

EXAMPLES::

sage: R.<x> = PolynomialRing(GF(3))

sage: S = R.quotient(x^2 - 2)

sage: S.modulus()

x^2 + 1

"""

return self.__polynomial

def ngens(self):

"""

Return the number of generators of this quotient ring over the base

ring. This function always returns 1.

EXAMPLES::

sage: R.<x> = PolynomialRing(QQ)

sage: S.<y> = PolynomialRing(R)

sage: T.<z> = S.quotient(y + x)

sage: T

Univariate Quotient Polynomial Ring in z over Univariate Polynomial Ring in x over Rational Field with modulus y + x

sage: T.ngens()

"""

return 1

def number_field(self):

"""

Return the number field isomorphic to this quotient polynomial

ring, if possible.

EXAMPLES::

sage: R.<x> = PolynomialRing(QQ)

sage: S.<alpha> = R.quotient(x^29 - 17*x - 1)

sage: K = S.number_field()

sage: K

Number Field in alpha with defining polynomial x^29 - 17*x - 1

sage: alpha = K.gen()

sage: alpha^29

17*alpha + 1

"""

if self.characteristic() != 0:

raise ArithmeticError("Polynomial quotient ring is not isomorphic to a number field (it has positive characteristic).")

if not isinstance(self.base_ring(), sage.rings.rational_field.RationalField):

raise NotImplementedError("Computation of number field only implemented for quotients of the polynomial ring over the rational field.")

return sage.rings.number_field.all.NumberField(self.modulus(), self.variable_name())

def polynomial_ring(self):

"""

Return the polynomial ring of which this ring is the quotient.

EXAMPLES::

sage: R.<x> = PolynomialRing(QQ)

sage: S = R.quotient(x^2-2)

sage: S.polynomial_ring()

Univariate Polynomial Ring in x over Rational Field

"""

return self.__ring

cover_ring = polynomial_ring

def random_element(self, *args, **kwds):

"""

Return a random element of this quotient ring.

INPUT:

- ``*args``, ``**kwds`` - Arguments for randomization that are passed

on to the ``random_element`` method of the polynomial ring, and from

there to the base ring

OUTPUT:

- Element of this quotient ring

EXAMPLES::

sage: F1.<a> = GF(2^7)

sage: P1.<x> = F1[]

sage: F2 = F1.extension(x^2+x+1, 'u')

sage: F2.random_element()

(a^6 + 1)*u + a^5 + a^4 + a^3 + 1

"""

return self(self.polynomial_ring().random_element( \

degree=self.degree()-1, *args, **kwds))

@cached_method

def _S_decomposition(self, S):

"""

Compute the decomposition of self into a product of number fields.

This is an internal function used by

:meth:`S_class_group`, :meth:`S_units` and :meth:`selmer_group`.

EXAMPLES::

sage: K.<a> = QuadraticField(-5)

sage: R.<x> = K[]

sage: S.<xbar> = R.quotient((x^2 + 23)*(x^2 + 31))

sage: fields, isos, iso_classes = S._S_decomposition(tuple(K.primes_above(3)))

Representatives of the number fields up to isomorphism that

occur in the decomposition::

sage: fields

[Number Field in x0 with defining polynomial x^2 + 23 over its base field,

Number Field in x1 with defining polynomial x^2 + 31 over its base field]

In this case, the isomorphisms of these representatives to the components

are the identity maps::

sage: isos

[(Ring endomorphism of Number Field in y0 with defining polynomial x^4 + 56*x^2 + 324

Defn: y0 |--> y0,

0),

(Ring endomorphism of Number Field in y1 with defining polynomial x^4 + 72*x^2 + 676

Defn: y1 |--> y1,

1)]

There are four primes above 3 in the first component and two

in the second component::

sage: len(iso_classes[0][1])

sage: len(iso_classes[1][1])

"""

from sage.rings.number_field.number_field_base import is_NumberField

K = self.base_ring()

if not is_NumberField(K) or not self.__polynomial.is_squarefree():

raise NotImplementedError

from sage.rings.ideal import is_Ideal

for p in S:

# second check due to inconsistency over QQ - see # 7596

if not (is_Ideal(p)

and (p.ring() is K or p.ring() is K.ring_of_integers())

and p.is_prime()):

raise TypeError("S must be a list of prime ideals of the base field.")

F = self.__polynomial.factor()

fields = []

isos = []

iso_classes = []

i = 0

for f, _ in F:

D = K.extension(f, 'x'+str(i))

fields.append(D)

D_abs = D.absolute_field('y'+str(i))

i += 1

seen_before = False

j = 0

for D_iso,_ in iso_classes:

if D_abs.is_isomorphic(D_iso):

seen_before = True; break

j += 1

if not seen_before:

S_abs = []

for p in S:

abs_gens = []

for g in D.ideal(p.gens()).gens(): # this line looks a bit silly, due to inconsistency over QQ - see # 7596

abs_gens.append(D_abs.structure()[1](g))

S_abs += [pp for pp,_ in D_abs.ideal(abs_gens).factor()]

iso_classes.append((D_abs,S_abs))

isos.append((D_abs.embeddings(D_abs)[0], j))

return fields, isos, iso_classes

def S_class_group(self, S, proof=True):

r"""

If self is an étale algebra `D` over a number field `K` (i.e.

a quotient of `K[x]` by a squarefree polynomial) and `S` is a

finite set of places of `K`, return a list of generators of

the `S`-class group of `D`.

NOTE:

Since the ``ideal`` function behaves differently over number

fields than over polynomial quotient rings (the quotient does

not even know its ring of integers), we return a set of pairs

``(gen, order)``, where ``gen`` is a tuple of generators of an

ideal `I` and ``order`` is the order of `I` in the `S`-class

group.

INPUT:

- ``S`` - a set of primes of the coefficient ring

- ``proof`` - if False, assume the GRH in computing the class group

OUTPUT:

A list of generators of the `S`-class group, in the form

``(gen, order)``, where ``gen`` is a tuple of elements

generating a fractional ideal `I` and ``order`` is the order

of `I` in the `S`-class group.

EXAMPLES:

A trivial algebra over `\QQ(\sqrt{-5})` has the same class group as its

base::

sage: K.<a> = QuadraticField(-5)

sage: R.<x> = K[]

sage: S.<xbar> = R.quotient(x)

sage: S.S_class_group([])

[((2, -a + 1), 2)]

When we include the prime `(2, -a+1)`, the `S`-class group

becomes trivial::

sage: S.S_class_group([K.ideal(2, -a+1)])

[]

Here is an example where the base and the extension both contribute to

the class group::

sage: K.<a> = QuadraticField(-5)

sage: K.class_group()

Class group of order 2 with structure C2 of Number Field in a with defining polynomial x^2 + 5

sage: R.<x> = K[]

sage: S.<xbar> = R.quotient(x^2 + 23)

sage: S.S_class_group([])

[((2, -a + 1, 1/2*xbar + 1/2, -1/2*a*xbar + 1/2*a + 1), 6)]

sage: S.S_class_group([K.ideal(3, a-1)])

[]

sage: S.S_class_group([K.ideal(2, a+1)])

[]

sage: S.S_class_group([K.ideal(a)])

[((2, -a + 1, 1/2*xbar + 1/2, -1/2*a*xbar + 1/2*a + 1), 6)]

Now we take an example over a nontrivial base with two factors, each

contributing to the class group::

sage: K.<a> = QuadraticField(-5)

sage: R.<x> = K[]

sage: S.<xbar> = R.quotient((x^2 + 23)*(x^2 + 31))

sage: S.S_class_group([])

[((1/4*xbar^2 + 31/4,

(-1/8*a + 1/8)*xbar^2 - 31/8*a + 31/8,

1/16*xbar^3 + 1/16*xbar^2 + 31/16*xbar + 31/16,

-1/16*a*xbar^3 + (1/16*a + 1/8)*xbar^2 - 31/16*a*xbar + 31/16*a + 31/8),

6),

((-1/4*xbar^2 - 23/4,

(1/8*a - 1/8)*xbar^2 + 23/8*a - 23/8,

-1/16*xbar^3 - 1/16*xbar^2 - 23/16*xbar - 23/16,

1/16*a*xbar^3 + (-1/16*a - 1/8)*xbar^2 + 23/16*a*xbar - 23/16*a - 23/8),

6),

((-5/4*xbar^2 - 115/4,

1/4*a*xbar^2 + 23/4*a,

-1/16*xbar^3 - 7/16*xbar^2 - 23/16*xbar - 161/16,

1/16*a*xbar^3 - 1/16*a*xbar^2 + 23/16*a*xbar - 23/16*a),

2)]

By using the ideal `(a)`, we cut the part of the class group coming from

`x^2 + 31` from 12 to 2, i.e. we lose a generator of order 6 (this was

fixed in :trac:`14489`)::

sage: S.S_class_group([K.ideal(a)])

[((1/4*xbar^2 + 31/4, (-1/8*a + 1/8)*xbar^2 - 31/8*a + 31/8, 1/16*xbar^3 + 1/16*xbar^2 + 31/16*xbar + 31/16, -1/16*a*xbar^3 + (1/16*a + 1/8)*xbar^2 - 31/16*a*xbar + 31/16*a + 31/8), 6), ((-1/4*xbar^2 - 23/4, (1/8*a - 1/8)*xbar^2 + 23/8*a - 23/8, -1/16*xbar^3 - 1/16*xbar^2 - 23/16*xbar - 23/16, 1/16*a*xbar^3 + (-1/16*a - 1/8)*xbar^2 + 23/16*a*xbar - 23/16*a - 23/8), 2)]

Note that all the returned values live where we expect them to::

sage: CG = S.S_class_group([])

sage: type(CG[0][0][1])

sage: type(CG[0][1])

"""

fields, isos, iso_classes = self._S_decomposition(tuple(S))

n = len(fields)

component_S_class_groups = []

for D_iso, S_iso in iso_classes:

# compute S-class group for each distinct component

clgp_gens = D_iso._S_class_group_and_units(tuple(S_iso), proof=proof)[1]

component_S_class_groups.append(clgp_gens)

clgp_gens = []

clgp_gens_orders = []

moduli = [D.relative_polynomial() for D in fields]

for i in range(n):

phi = isos[i][0]

back_to_rel = phi.codomain().structure()[0]

for clgp_gen, gen_order in component_S_class_groups[isos[i][1]]:

ideal_gens = []

for ideal_gen in clgp_gen.gens():

rel_ideal_gen = back_to_rel(phi(ideal_gen))

prod_ideal_gen = [0]*i + [rel_ideal_gen.lift()] + [0]*(n - i - 1)

poly_ideal_gen = self(sage.arith.all.crt(prod_ideal_gen, moduli))

ideal_gens.append(poly_ideal_gen)

clgp_gens.append((tuple(ideal_gens), gen_order))

return clgp_gens

def class_group(self, proof=True):

"""

If self is a quotient ring of a polynomial ring over a number

field `K`, by a polynomial of nonzero discriminant, return a

list of generators of the class group.

NOTE:

Since the ``ideal`` function behaves differently over number

fields than over polynomial quotient rings (the quotient does

not even know its ring of integers), we return a set of pairs

``(gen, order)``, where ``gen`` is a tuple of generators of an

ideal `I` and ``order`` is the order of `I` in the class group.

INPUT:

- ``proof`` - if False, assume the GRH in computing the class group

OUTPUT:

A list of pairs ``(gen, order)``, where ``gen`` is a tuple of

elements generating a fractional ideal and ``order`` is

the order of `I` in the class group.

EXAMPLES::

sage: K.<a> = QuadraticField(-3)

sage: K.class_group()

Class group of order 1 of Number Field in a with defining polynomial x^2 + 3

sage: K.<a> = QQ['x'].quotient(x^2 + 3)

sage: K.class_group()

[]

A trivial algebra over `\QQ(\sqrt{-5})` has the same class group as its

base::

sage: K.<a> = QuadraticField(-5)

sage: R.<x> = K[]

sage: S.<xbar> = R.quotient(x)

sage: S.class_group()

[((2, -a + 1), 2)]

The same algebra constructed in a different way::

sage: K.<a> = QQ['x'].quotient(x^2 + 5)

sage: K.class_group(())

[((2, a + 1), 2)]

Here is an example where the base and the extension both contribute to

the class group::

sage: K.<a> = QuadraticField(-5)

sage: K.class_group()

Class group of order 2 with structure C2 of Number Field in a with defining polynomial x^2 + 5

sage: R.<x> = K[]

sage: S.<xbar> = R.quotient(x^2 + 23)

sage: S.class_group()

[((2, -a + 1, 1/2*xbar + 1/2, -1/2*a*xbar + 1/2*a + 1), 6)]

Here is an example of a product of number fields, both of which

contribute to the class group::

sage: R.<x> = QQ[]

sage: S.<xbar> = R.quotient((x^2 + 23)*(x^2 + 47))

sage: S.class_group()

[((1/12*xbar^2 + 47/12, 1/48*xbar^3 - 1/48*xbar^2 + 47/48*xbar - 47/48), 3), ((-1/12*xbar^2 - 23/12, -1/48*xbar^3 - 1/48*xbar^2 - 23/48*xbar - 23/48), 5)]

Now we take an example over a nontrivial base with two factors, each

contributing to the class group::

sage: K.<a> = QuadraticField(-5)

sage: R.<x> = K[]

sage: S.<xbar> = R.quotient((x^2 + 23)*(x^2 + 31))

sage: S.class_group()

[((1/4*xbar^2 + 31/4,

(-1/8*a + 1/8)*xbar^2 - 31/8*a + 31/8,

1/16*xbar^3 + 1/16*xbar^2 + 31/16*xbar + 31/16,

-1/16*a*xbar^3 + (1/16*a + 1/8)*xbar^2 - 31/16*a*xbar + 31/16*a + 31/8),

6),

((-1/4*xbar^2 - 23/4,

(1/8*a - 1/8)*xbar^2 + 23/8*a - 23/8,

-1/16*xbar^3 - 1/16*xbar^2 - 23/16*xbar - 23/16,

1/16*a*xbar^3 + (-1/16*a - 1/8)*xbar^2 + 23/16*a*xbar - 23/16*a - 23/8),

6),

((-5/4*xbar^2 - 115/4,

1/4*a*xbar^2 + 23/4*a,

-1/16*xbar^3 - 7/16*xbar^2 - 23/16*xbar - 161/16,

1/16*a*xbar^3 - 1/16*a*xbar^2 + 23/16*a*xbar - 23/16*a),

2)]

Note that all the returned values live where we expect them to::

sage: CG = S.class_group()

sage: type(CG[0][0][1])

sage: type(CG[0][1])

"""

return self.S_class_group((), proof=proof)

def S_units(self, S, proof=True):

"""

If self is an étale algebra `D` over a number field `K` (i.e.

a quotient of `K[x]` by a squarefree polynomial) and `S` is a

finite set of places of `K`, return a list of generators of

the group of `S`-units of `D`.

INPUT:

- ``S`` - a set of primes of the base field

- ``proof`` - if False, assume the GRH in computing the class group

OUTPUT:

A list of generators of the `S`-unit group, in the form

``(gen, order)``, where ``gen`` is a unit of order ``order``.

EXAMPLES::

sage: K.<a> = QuadraticField(-3)

sage: K.unit_group()

Unit group with structure C6 of Number Field in a with defining polynomial x^2 + 3

sage: K.<a> = QQ['x'].quotient(x^2 + 3)

sage: u,o = K.S_units([])[0]; u, o

(-1/2*a + 1/2, 6)

sage: u^6

sage: u^3

-1

sage: u^2

-1/2*a - 1/2

sage: K.<a> = QuadraticField(-3)

sage: y = polygen(K)

sage: L. = K['y'].quotient(y^3 + 5); L

Univariate Quotient Polynomial Ring in b over Number Field in a with defining polynomial x^2 + 3 with modulus y^3 + 5

sage: L.S_units([])

[(-1/2*a + 1/2, 6),

((-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, +Infinity),

(2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2, +Infinity)]

sage: L.S_units([K.ideal(1/2*a - 3/2)])

[((-1/6*a - 1/2)*b^2 + (1/3*a - 1)*b + 4/3*a, +Infinity),

(-1/2*a + 1/2, 6),

((-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, +Infinity),

(2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2, +Infinity)]

sage: L.S_units([K.ideal(2)])

[((1/2*a - 1/2)*b^2 + (a + 1)*b + 3, +Infinity),

((1/6*a + 1/2)*b^2 + (-1/3*a + 1)*b - 5/6*a + 1/2, +Infinity),

((1/6*a + 1/2)*b^2 + (-1/3*a + 1)*b - 5/6*a - 1/2, +Infinity),

(-1/2*a + 1/2, 6),

((-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, +Infinity),

(2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2, +Infinity)]

Note that all the returned values live where we expect them to::

sage: U = L.S_units([])

sage: type(U[0][0])

sage: type(U[0][1])

sage: type(U[1][1])

"""

fields, isos, iso_classes = self._S_decomposition(tuple(S))

n = len(fields)

component_S_units = []

for D_iso, S_iso in iso_classes:

# compute S-units for each distinct component

units = D_iso.S_units(S_iso, proof=proof)

component_S_units.append(units)

units = []

moduli = [D.relative_polynomial() for D in fields]

for i in range(n):

phi = isos[i][0]

back_to_rel = phi.codomain().structure()[0]

for unit in component_S_units[isos[i][1]]:

mul_order = unit.multiplicative_order()

rel_unit = back_to_rel(phi(unit))

prod_unit = [1]*i + [rel_unit.lift()] + [1]*(n - i - 1)

poly_unit = self(sage.arith.all.crt(prod_unit, moduli))

units.append((poly_unit, mul_order))

return units

def units(self, proof=True):

"""

If this quotient ring is over a number field K, by a polynomial of

nonzero discriminant, returns a list of generators of the units.

INPUT:

- ``proof`` - if False, assume the GRH in computing the class group

OUTPUT:

A list of generators of the unit group, in the form ``(gen, order)``,

where ``gen`` is a unit of order ``order``.

EXAMPLES::

sage: K.<a> = QuadraticField(-3)

sage: K.unit_group()

Unit group with structure C6 of Number Field in a with defining polynomial x^2 + 3

sage: K.<a> = QQ['x'].quotient(x^2 + 3)

sage: u = K.units()[0][0]; u

-1/2*a + 1/2

sage: u^6

sage: u^3

-1

sage: u^2

-1/2*a - 1/2

sage: K.<a> = QQ['x'].quotient(x^2 + 5)

sage: K.units(())

[(-1, 2)]

sage: K.<a> = QuadraticField(-3)

sage: y = polygen(K)

sage: L. = K['y'].quotient(y^3 + 5); L

Univariate Quotient Polynomial Ring in b over Number Field in a with defining polynomial x^2 + 3 with modulus y^3 + 5

sage: L.units()

[(-1/2*a + 1/2, 6),

((-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, +Infinity),

(2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2, +Infinity)]

sage: L. = K.extension(y^3 + 5)

sage: L.unit_group()

Unit group with structure C6 x Z x Z of Number Field in b with defining polynomial x^3 + 5 over its base field

sage: L.unit_group().gens() # abstract generators

(u0, u1, u2)

sage: L.unit_group().gens_values()

[1/2*a + 1/2, (-1/3*a - 1)*b^2 - 4/3*a*b - 5/6*a + 7/2, 2/3*a*b^2 + (2/3*a - 2)*b - 5/6*a - 7/2]

Note that all the returned values live where we expect them to::

sage: L. = K['y'].quotient(y^3 + 5)

sage: U = L.units()

sage: type(U[0][0])

sage: type(U[0][1])

sage: type(U[1][1])

"""

return self.S_units((), proof=proof)

def selmer_group(self, S, m, proof=True):

r"""

If self is an étale algebra `D` over a number field `K` (i.e.

a quotient of `K[x]` by a squarefree polynomial) and `S` is a

finite set of places of `K`, compute the Selmer group

`D(S,m)`. This is the subgroup of `D^*/(D^*)^m` consisting of

elements `a` such that `D(\sqrt[m]{a})/D` is unramified at all

primes of `D` lying above a place outside of `S`.

INPUT:

- ``S`` - A set of primes of the coefficient ring (which is a number field).

- ``m`` - a positive integer

- ``proof`` - if False, assume the GRH in computing the class group

OUTPUT:

A list of generators of `D(S,m)`.

EXAMPLES::

sage: K.<a> = QuadraticField(-5)

sage: R.<x> = K[]

sage: D.<T> = R.quotient(x)

sage: D.selmer_group((), 2)

[-1, 2]

sage: D.selmer_group([K.ideal(2, -a+1)], 2)

[2, -1]

sage: D.selmer_group([K.ideal(2, -a+1), K.ideal(3, a+1)], 2)

[2, a + 1, -1]

sage: D.selmer_group((K.ideal(2, -a+1),K.ideal(3, a+1)), 4)

[2, a + 1, -1]

sage: D.selmer_group([K.ideal(2, -a+1)], 3)

[2]

sage: D.selmer_group([K.ideal(2, -a+1), K.ideal(3, a+1)], 3)

[2, a + 1]

sage: D.selmer_group([K.ideal(2, -a+1), K.ideal(3, a+1), K.ideal(a)], 3)

[2, a + 1, a]

"""

fields, isos, iso_classes = self._S_decomposition(tuple(S))

n = len(fields)

component_selmer_groups = []

for D_iso, S_iso in iso_classes:

sel = D_iso.selmer_group(S_iso, m, proof=proof)

component_selmer_groups.append(sel)

gens = []

moduli = [D.relative_polynomial() for D in fields]

for i in range(n):

phi = isos[i][0]

back_to_rel = phi.codomain().structure()[0]

for gen in component_selmer_groups[isos[i][1]]:

rel_gen = back_to_rel(phi(gen))

prod_gen = [1]*i + [rel_gen.lift()] + [1]*(n - i - 1)

poly_gen = self(sage.arith.all.crt(prod_gen, moduli))

gens.append(poly_gen)

return gens

def _factor_univariate_polynomial(self, f):

r"""

Return the factorization of ``f`` over this ring.

TESTS::

sage: K = GF(2)

sage: R.<x> = K[]

sage: L.<x> = K.extension(x^2 + x + 1)

sage: R.<y> = L[]

sage: M.<y> = L.extension(y^2 + y + x)

sage: R.<T> = M[]

sage: R(y).factor() # indirect doctest

sage: (T^2 + T + x).factor() # indirect doctest

(T + y) * (T + y + 1)

sage: (y*T^2 + y*T + y*x).factor() # indirect doctest

(y) * (T + y) * (T + y + 1)

"""

from sage.structure.factorization import Factorization

if f.is_zero():

raise ValueError("factorization of 0 not defined")

unit = f.leading_coefficient()

if not unit.is_unit():

raise NotImplementedError("factorization of polynomials with non-unit leading coefficient")

unit = f.parent()(unit)

f = f.monic()

if f.degree() == 0:

return Factorization(unit=unit)

elif f.degree() == 1:

return Factorization([(f,1)], unit=unit)

else:

from_isomorphic_ring, to_isomorphic_ring, isomorphic_ring = self._isomorphic_ring()

g = f.map_coefficients(to_isomorphic_ring)

F = g.factor()

unit *= g.parent()(F.unit()).map_coefficients(from_isomorphic_ring)

return Factorization([(factor.map_coefficients(from_isomorphic_ring), e) for factor,e in F], unit=unit)

@cached_method

def _isomorphic_ring(self):

"""

Return a ring isomorphic to this ring which is not a

:class:`PolynomialQuotientRing` but of a type which offers more

functionality.

OUTPUT:

a triple ``from, to, ring`` consisting of an isomorphism from the

isomorphic ring to this ring, the inverse of that isomorphism, and the

isomorphic ring

EXAMPLES::

sage: K.<a> = GF(4)

sage: R. = K[]

sage: L. = K.extension(b^2+b+a); L

Univariate Quotient Polynomial Ring in b over Finite Field in a of size 2^2 with modulus b^2 + b + a

sage: from_M, to_M, M = L._isomorphic_ring(); M

Finite Field in z4 of size 2^4

sage: R.<c> = L[]

sage: M.<c> = L.extension(c^2+b*c+b); M

Univariate Quotient Polynomial Ring in c over Univariate Quotient Polynomial Ring in b over Finite Field in a of size 2^2 with modulus b^2 + b + a with modulus c^2 + b*c + b

sage: from_N, to_N, N = M._isomorphic_ring(); N

Finite Field in z8 of size 2^8

sage: R.<x> = QQ[]

sage: K = R.quo(x^2 + 1)

sage: from_L, to_L, L = K._isomorphic_ring()

sage: L

Number Field in xbar with defining polynomial x^2 + 1

TESTS:

Verify that this works for trivial extensions::

sage: K.<a> = GF(4)

sage: R. = K[]

sage: from_L, to_L, L = R.quo(b)._isomorphic_ring(); L

Finite Field in a of size 2^2

"""

from sage.categories.homset import Hom

from sage.categories.morphism import SetMorphism

if isinstance(self.base_ring(), PolynomialQuotientRing_generic):

# rewrite this ring over the isomorphic version of the base ring

isomorphic_base_to_base, base_to_isomorphic_base, isomorphic_base = self.base_ring()._isomorphic_ring()

modulus = self.modulus().map_coefficients(base_to_isomorphic_base)

isomorphic_quotient = modulus.parent().quo(modulus)

# we do not construct the isomorphisms yet because we want to know

# the category that our final result lives in

# recursively try to rewrite the isomorphic_quotient

isomorphic_ring_to_isomorphic_quotient, isomorphic_quotient_to_isomorphic_ring, isomorphic_ring = isomorphic_quotient._isomorphic_ring()

# the process has likely refined the category of

# isomorphic_quotient (to Fields e.g.) so we use the same category

# for self

self._refine_category_(isomorphic_quotient.category())

homspace = Hom(isomorphic_quotient, self)

from_isomorphic_quotient = homspace.__make_element_class__(SetMorphism)(homspace,

lambda f: f.lift().map_coefficients(isomorphic_base_to_base)(self.gen()))

homspace = Hom(self, isomorphic_quotient)

to_isomorphic_quotient = homspace.__make_element_class__(SetMorphism)(homspace,

lambda f: f.lift().map_coefficients(base_to_isomorphic_base)(isomorphic_quotient.gen()))

return (from_isomorphic_quotient * isomorphic_ring_to_isomorphic_quotient,

isomorphic_quotient_to_isomorphic_ring * to_isomorphic_quotient,

isomorphic_ring)

if self.modulus().degree() == 1:

# this quotient is a trivial extension of the base ring, we can just

# return the base ring

isomorphic_ring = self.base_ring()

# With this knowledge we can refine the category of self (and of the resulting morphisms.)

# However, we can not just refine self to

# isomorphic_ring.category() because that category might expect an

# interface which we can not provide (e.g. NumberFields).

# So we just check some important special cases here (note that

# integral domains is already handled elsewhere.)

from sage.categories.all import Fields

if isomorphic_ring in Fields():

self._refine_category_(Fields())

from_isomorphic_ring = isomorphic_ring.hom(self)

homspace = Hom(self, isomorphic_ring)

to_isomorphic_ring = homspace.__make_element_class__(SetMorphism)(homspace, lambda f: isomorphic_ring(f.lift()))

return from_isomorphic_ring, to_isomorphic_ring, isomorphic_ring

if self.is_finite() and self.is_field():

# for a finite field, we return the isomorphic simple extensions of

# the underlying prime field

N = self.cardinality()

from sage.rings.all import GF

isomorphic_ring = GF(N)

# the map to GF(N) maps our generator to a root of our modulus in the isomorphic_ring

base_image = self.base_ring().modulus().change_ring(isomorphic_ring).any_root()

base_to_isomorphic_ring = self.base_ring().hom([isomorphic_ring(base_image)])

modulus = self.modulus().map_coefficients(base_to_isomorphic_ring)

gen = modulus.any_root(assume_squarefree=True, degree=-1)

homspace = Hom(self, isomorphic_ring)

to_isomorphic_ring = homspace.__make_element_class__(SetMorphism)(homspace,

lambda f: f.lift().map_coefficients(base_to_isomorphic_ring)(gen))

# For the map from GF(N) we need to figure out where the primitive

# element of GF(N) goes. We write down a basis of self over GF(p),

# send it to isomorphic_ring, and solve the linear equation which

# writes the primitive element of GF(N) as a linear combination of

# that basis.

basis = [self.gen()**i*self.base_ring().gen()**j

for i in range(self.degree())

for j in range(self.base_ring().degree())]

assert(len(basis) == isomorphic_ring.degree())

from sage.matrix.constructor import matrix

A = matrix([to_isomorphic_ring(b)._vector_() for b in basis])

assert(A.is_square())

# solve x*A = (0,1,0,…,0)

x = A.solve_left(A.column_space().basis()[1])

primitive_element = sum(c*b for c,b in zip(x.list(), basis))

from_isomorphic_ring = isomorphic_ring.hom([primitive_element], check=False)

return from_isomorphic_ring, to_isomorphic_ring, isomorphic_ring

from sage.categories.all import NumberFields

if self.base_ring() in NumberFields():

try:

isomorphic_ring = self.base_ring().extension(self.modulus(), names=self.variable_names())

except ValueError:

pass # modulus is not irreducible

else:

if not isomorphic_ring in NumberFields():

raise NotImplementedError("can not handle extensions of number fields that do not produce number fields")

# refine the category of self

if not self.is_field():

assert False, "self is isomorphic to a field"

from_isomorphic_ring = isomorphic_ring.hom([self.gen()])

to_isomorphic_ring = self.hom([isomorphic_ring.gen()])

return from_isomorphic_ring, to_isomorphic_ring, isomorphic_ring

raise NotImplementedError("can not rewrite %r as an isomorphic ring"%(self,))

def _test_isomorphic_ring(self, **options):

r"""

Check that :meth:`_isomorphic_ring` works correctly.

TESTS::

sage: K.<a> = GF(4)

sage: R. = K[]

sage: L. = K.extension(b^2+b+a)

sage: L._test_isomorphic_ring()

sage: R.<c> = L[]

sage: M.<c> = L.extension(c^2+b*c+b)

sage: M._test_isomorphic_ring()

"""

tester = self._tester(**options)

try:

from_isomorphic_ring, to_isomorphic_ring, ring = self._isomorphic_ring()

except NotImplementedError:

return

tester.assertNotIsInstance(ring, PolynomialQuotientRing_generic)

from sage.categories.all import Fields, IntegralDomains

if ring.category().is_subcategory(IntegralDomains()):

category = IntegralDomains()

if ring.category().is_subcategory(Fields()):

category = Fields()

tester.assertTrue(self.category().is_subcategory(category))

tester.assertTrue(from_isomorphic_ring.category_for().is_subcategory(category))

tester.assertTrue(to_isomorphic_ring.category_for().is_subcategory(category))

for x in tester.some_elements():

y = to_isomorphic_ring(x)

tester.assertIn(y, ring)

tester.assertEqual(from_isomorphic_ring(y), x)

from sage.structure.coerce_maps import DefaultConvertMap_unique

class PolynomialQuotientRing_coercion(DefaultConvertMap_unique):

r"""

A coercion map from a :class:`PolynomialQuotientRing` to a

:class:`PolynomialQuotientRing` that restricts to the coercion map on the

underlying ring of constants.

EXAMPLES::

sage: R.<x> = ZZ[]

sage: S.<x> = QQ[]

sage: f = S.quo(x^2 + 1).coerce_map_from(R.quo(x^2 + 1)); f

Coercion map:

From: Univariate Quotient Polynomial Ring in xbar over Integer Ring with modulus x^2 + 1

To: Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^2 + 1

TESTS::

sage: from sage.rings.polynomial.polynomial_quotient_ring import PolynomialQuotientRing_coercion

sage: isinstance(f, PolynomialQuotientRing_coercion)

True

sage: TestSuite(f).run(skip=['_test_pickling'])

Pickling works but the returned value is not compare equal to the original

morphism::

sage: g = loads(dumps(f)); g

Coercion map:

From: Univariate Quotient Polynomial Ring in xbar over Integer Ring with modulus x^2 + 1

To: Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^2 + 1

sage: f == g

False

The reason for this is that pickling of the domain is currently broken, and

therefore the parent of `f` and `g` are different::

sage: loads(dumps(f.domain())) is f.domain()

False

sage: f.parent() is g.parent()

False

"""

def is_injective(self):

r"""

Return whether this coercion is injective.

EXAMPLES:

If the modulus of the domain and the codomain is the same and the

leading coefficient is a unit in the domain, then the map is injective

if the underlying map on the constants is::

sage: R.<x> = ZZ[]

sage: S.<x> = QQ[]

sage: f = S.quo(x^2 + 1).coerce_map_from(R.quo(x^2 + 1))

sage: f.is_injective()

True

"""

if (self.domain().modulus().change_ring(self.codomain().base_ring()) == self.codomain().modulus()

and self.domain().modulus().leading_coefficient().is_unit()):

if self.codomain().base_ring().coerce_map_from(self.domain().base_ring()).is_injective():

return True

else:

return self.domain().modulus().degree() == 0 # domain and codomain are the zero ring

return super(PolynomialQuotientRing_coercion, self).is_injective()

def is_surjective(self):

r"""

Return whether this coercion is surjective.

EXAMPLES:

If the underlying map on constants is surjective, then this coercion is

surjective since the modulus of the codomain divides the modulus of the

domain::

sage: R.<x> = ZZ[]

sage: f = R.quo(x).coerce_map_from(R.quo(x^2))

sage: f.is_surjective()

True

If the modulus of the domain and the codomain is the same, then the map

is surjective iff the underlying map on the constants is::

sage: A.<a> = ZqCA(9)

sage: R.<x> = A[]

sage: S.<x> = A.fraction_field()[]

sage: f = S.quo(x^2 + 2).coerce_map_from(R.quo(x^2 + 2))

sage: f.is_surjective()

False

"""

constant_map_is_surjective = self.codomain().base_ring().coerce_map_from(self.domain().base_ring()).is_surjective()

if constant_map_is_surjective:

return True

if self.domain().modulus().change_ring(self.codomain().base_ring()) == self.codomain().modulus():

return constant_map_is_surjective

return super(PolynomialQuotientRing_coercion, self).is_surjective()

def _richcmp_(self, other, op):

r"""

Compare this morphism to ``other``.

EXAMPLES::

sage: R.<x> = ZZ[]

sage: S.<x> = ZZ[]

sage: f = S.quo(x).coerce_map_from(R.quo(x^2))

sage: g = S.quo(x).coerce_map_from(R.quo(x^3))

sage: f == g

False

sage: f == f

True

"""

if type(self) != type(other):

return NotImplemented

return richcmp(self.parent(), other.parent(), op)

class PolynomialQuotientRing_domain(PolynomialQuotientRing_generic, IntegralDomain):

"""

EXAMPLES::

sage: R.<x> = PolynomialRing(ZZ)

sage: S.<xbar> = R.quotient(x^2 + 1)

sage: S

Univariate Quotient Polynomial Ring in xbar over Integer Ring with modulus x^2 + 1

sage: loads(S.dumps()) == S

True

sage: loads(xbar.dumps()) == xbar

True

"""

def __init__(self, ring, polynomial, name=None, category=None):

r"""

Initialize ``self``.

TESTS::

sage: R.<x> = PolynomialRing(ZZ)

sage: S.<xbar> = R.quotient(x^2 + 1)

sage: TestSuite(S).run()

Check that :trac:`17450` is fixed::

sage: S in IntegralDomains()

True

"""

category = CommutativeAlgebras(ring.base_ring()).Quotients().NoZeroDivisors().or_subcategory(category)

PolynomialQuotientRing_generic.__init__(self, ring, polynomial, name, category)

def __reduce__(self):

return PolynomialQuotientRing_domain, (self.polynomial_ring(),

self.modulus(), self.variable_names())

def field_extension(self, names):

r"""

Takes a polynomial quotient ring, and returns a tuple with three

elements: the NumberField defined by the same polynomial quotient

ring, a homomorphism from its parent to the NumberField sending the

generators to one another, and the inverse isomorphism.

OUTPUT:

- field

- homomorphism from self to field

- homomorphism from field to self

EXAMPLES::

sage: R.<x> = PolynomialRing(Rationals())

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

sage: F., f, g = S.field_extension()

sage: F

Number Field in b with defining polynomial x^3 - 2

sage: a = F.gen()

sage: f(alpha)

sage: g(a)

alpha

Note that the parent ring must be an integral domain::

sage: R.<x> = GF(25,'f25')['x']

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

sage: F, g, h = S.field_extension('b')

Traceback (most recent call last):

...

AttributeError: 'PolynomialQuotientRing_generic_with_category' object has no attribute 'field_extension'

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

number field::

sage: R.<x> = GF(25, 'a')['x']

sage: S.<a> = R.quo(x^3 + 2*x + 1)

sage: F, g, h = S.field_extension('b')

sage: h(F.0^2 + 3)

a^2 + 3

sage: g(x^2 + 2)

b^2 + 2

We do an example involving a relative number field::

sage: R.<x> = QQ['x']

sage: K.<a> = NumberField(x^3 - 2)

sage: S.<X> = K['X']

sage: Q. = S.quo(X^3 + 2*X + 1)

sage: Q.field_extension('b')

(Number Field in b with defining polynomial X^3 + 2*X + 1 over its base field, ...

Defn: b |--> b, Relative number field morphism:

From: Number Field in b with defining polynomial X^3 + 2*X + 1 over its base field

To: Univariate Quotient Polynomial Ring in b over Number Field in a with defining polynomial x^3 - 2 with modulus X^3 + 2*X + 1

Defn: b |--> b

a |--> a)

We slightly change the example above so it works.

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 = Q.field_extension()

sage: c = g(z)

sage: f(c)

sage: h(g(z))

sage: g(h(w))

AUTHORS:

- Craig Citro (2006-08-07)

- William Stein (2006-08-06)

"""

return self.gen().field_extension(names)

class PolynomialQuotientRing_field(PolynomialQuotientRing_domain, Field):

"""

EXAMPLES::

sage: R.<x> = PolynomialRing(QQ)

sage: S.<xbar> = R.quotient(x^2 + 1)

sage: S

Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^2 + 1

sage: loads(S.dumps()) == S

True

sage: loads(xbar.dumps()) == xbar

True

"""

def __init__(self, ring, polynomial, name=None):

PolynomialQuotientRing_domain.__init__(self, ring, polynomial, name)

def __reduce__(self):

return PolynomialQuotientRing_field, (self.polynomial_ring(),

self.modulus(), self.variable_names())

def base_field(self):

r"""

Alias for base_ring, when we're defined over a field.

"""

return self.base_ring()

def complex_embeddings(self, prec=53):

r"""

Return all homomorphisms of this ring into the approximate complex

field with precision prec.

EXAMPLES::

sage: R.<x> = QQ[]

sage: f = x^5 + x + 17

sage: k = R.quotient(f)

sage: v = k.complex_embeddings(100)

sage: [phi(k.0^2) for phi in v]

[2.9757207403766761469671194565, -2.4088994371613850098316292196 + 1.9025410530350528612407363802*I, -2.4088994371613850098316292196 - 1.9025410530350528612407363802*I, 0.92103906697304693634806949137 - 3.0755331188457794473265418086*I, 0.92103906697304693634806949137 + 3.0755331188457794473265418086*I]

"""

CC = sage.rings.complex_field.ComplexField(prec)

v = self.modulus().roots(multiplicities=False, ring=CC)

return [self.hom([a], check=False) for a in v]

Coverage for local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_quotient_ring.py : 75%

424 statements 319 run 105 missing 0 excluded