"""
Univariate Polynomial Rings

Sage implements sparse and dense polynomials over commutative and
non-commutative rings.  In the non-commutative case, the polynomial
variable commutes with the elements of the base ring.

AUTHOR:

- William Stein

- Kiran Kedlaya (2006-02-13): added macaulay2 option

- Martin Albrecht (2006-08-25): removed it again as it isn't needed anymore

- Simon King (2011-05): Dense and sparse polynomial rings must not be equal.

- Simon King (2011-10): Choice of categories for polynomial rings.

EXAMPLES::

    sage: z = QQ['z'].0
    sage: (z^3 + z - 1)^3
    z^9 + 3*z^7 - 3*z^6 + 3*z^5 - 6*z^4 + 4*z^3 - 3*z^2 + 3*z - 1

Saving and loading of polynomial rings works::

    sage: loads(dumps(QQ['x'])) == QQ['x']
    True
    sage: k = PolynomialRing(QQ['x'],'y'); loads(dumps(k))==k
    True
    sage: k = PolynomialRing(ZZ,'y'); loads(dumps(k)) == k
    True
    sage: k = PolynomialRing(ZZ,'y', sparse=True); loads(dumps(k))
    Sparse Univariate Polynomial Ring in y over Integer Ring

Rings with different variable names are not equal; in fact,
by :trac:`9944`, polynomial rings are equal if and only
if they are identical (which should be the  case for all parent
structures in Sage)::

    sage: QQ['y'] != QQ['x']
    True
    sage: QQ['y'] != QQ['z']
    True

We create a polynomial ring over a quaternion algebra::

    sage: A.<i,j,k> = QuaternionAlgebra(QQ, -1,-1)
    sage: R.<w> = PolynomialRing(A,sparse=True)
    sage: f = w^3 + (i+j)*w + 1
    sage: f
    w^3 + (i + j)*w + 1
    sage: f^2
    w^6 + (2*i + 2*j)*w^4 + 2*w^3 - 2*w^2 + (2*i + 2*j)*w + 1
    sage: f = w + i ; g = w + j
    sage: f * g
    w^2 + (i + j)*w + k
    sage: g * f
    w^2 + (i + j)*w - k

:trac:`9944` introduced some changes related with
coercion. Previously, a dense and a sparse polynomial ring with the
same variable name over the same base ring evaluated equal, but of
course they were not identical.Coercion maps are cached - but if a
coercion to a dense ring is requested and a coercion to a sparse ring
is returned instead (since the cache keys are equal!), all hell breaks
loose.

Therefore, the coercion between rings of sparse and dense polynomials
works as follows::

    sage: R.<x> = PolynomialRing(QQ, sparse=True)
    sage: S.<x> = QQ[]
    sage: S == R
    False
    sage: S.has_coerce_map_from(R)
    True
    sage: R.has_coerce_map_from(S)
    False
    sage: (R.0+S.0).parent()
    Univariate Polynomial Ring in x over Rational Field
    sage: (S.0+R.0).parent()
    Univariate Polynomial Ring in x over Rational Field

It may be that one has rings of dense or sparse polynomials over
different base rings. In that situation, coercion works by means of
the :func:`~sage.categories.pushout.pushout` formalism::

    sage: R.<x> = PolynomialRing(GF(5), sparse=True)
    sage: S.<x> = PolynomialRing(ZZ)
    sage: R.has_coerce_map_from(S)
    False
    sage: S.has_coerce_map_from(R)
    False
    sage: S.0 + R.0
    2*x
    sage: (S.0 + R.0).parent()
    Univariate Polynomial Ring in x over Finite Field of size 5
    sage: (S.0 + R.0).parent().is_sparse()
    False

Similarly, there is a coercion from the (non-default) NTL
implementation for univariate polynomials over the integers
to the default FLINT implementation, but not vice versa::

    sage: R.<x> = PolynomialRing(ZZ, implementation = 'NTL')
    sage: S.<x> = PolynomialRing(ZZ, implementation = 'FLINT')
    sage: (S.0+R.0).parent() is S
    True
    sage: (R.0+S.0).parent() is S
    True

TESTS::

    sage: K.<x>=FractionField(QQ['x'])
    sage: V.<z> = K[]
    sage: x+z
    z + x

Check that :trac:`5562` has been fixed::

    sage: R.<u> = PolynomialRing(RDF, 1)
    sage: v1 = vector([u])
    sage: v2 = vector([CDF(2)])
    sage: v1 * v2
    2.0*u

"""

#*****************************************************************************
#       Copyright (C) 2006 William Stein <wstein@gmail.com>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 2 of the License, or
# (at your option) any later version.
#                  http://www.gnu.org/licenses/
#*****************************************************************************

from __future__ import absolute_import, print_function

import sys
from six.moves import range

from sage.structure.element import Element

import sage.categories as categories
from sage.categories.morphism import IdentityMorphism

import sage.algebras.algebra
import sage.rings.commutative_algebra as commutative_algebra
import sage.rings.ring as ring
from sage.structure.element import is_RingElement
import sage.rings.polynomial.polynomial_element_generic as polynomial_element_generic
import sage.rings.rational_field as rational_field
from sage.rings.rational_field import QQ
from sage.rings.integer_ring import ZZ
from sage.rings.integer import Integer
from sage.rings.number_field.number_field_base import is_NumberField
from sage.libs.pari.all import pari_gen
from sage.rings.polynomial.polynomial_ring_constructor import polynomial_default_category

import sage.misc.latex as latex
from sage.misc.prandom import randint
from sage.misc.cachefunc import cached_method
from sage.misc.lazy_attribute import lazy_attribute

from sage.rings.real_mpfr import is_RealField
from sage.rings.fraction_field_element import FractionFieldElement
from sage.rings.finite_rings.element_base import FiniteRingElement

from .polynomial_element import PolynomialBaseringInjection
from .polynomial_real_mpfr_dense import PolynomialRealDense
from .polynomial_integer_dense_flint import Polynomial_integer_dense_flint
from sage.rings.polynomial.polynomial_singular_interface import PolynomialRing_singular_repr
from sage.rings.polynomial.polynomial_singular_interface import can_convert_to_singular

_CommutativeRings = categories.commutative_rings.CommutativeRings()

from . import cyclotomic

from sage.interfaces.singular import SingularElement


def is_PolynomialRing(x):
    """
    Return True if x is a *univariate* polynomial ring (and not a
    sparse multivariate polynomial ring in one variable).

    EXAMPLES::

        sage: from sage.rings.polynomial.polynomial_ring import is_PolynomialRing
        sage: from sage.rings.polynomial.multi_polynomial_ring import is_MPolynomialRing
        sage: is_PolynomialRing(2)
        False

    This polynomial ring is not univariate.

    ::

        sage: is_PolynomialRing(ZZ['x,y,z'])
        False
        sage: is_MPolynomialRing(ZZ['x,y,z'])
        True

    ::

        sage: is_PolynomialRing(ZZ['w'])
        True

    Univariate means not only in one variable, but is a specific data
    type. There is a multivariate (sparse) polynomial ring data type,
    which supports a single variable as a special case.

    ::

        sage: R.<w> = PolynomialRing(ZZ, implementation="singular"); R
        Multivariate Polynomial Ring in w over Integer Ring
        sage: is_PolynomialRing(R)
        False
        sage: type(R)
        <type 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomialRing_libsingular'>
    """
    return isinstance(x, PolynomialRing_general)


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

class PolynomialRing_general(sage.algebras.algebra.Algebra):
    """
    Univariate polynomial ring over a ring.
    """

    def __init__(self, base_ring, name=None, sparse=False, element_class=None, category=None):
        """
        EXAMPLES::

            sage: R.<x> = QQ['x']
            sage: R(-1) + R(1)
            0
            sage: (x - 2/3)*(x^2 - 8*x + 16)
            x^3 - 26/3*x^2 + 64/3*x - 32/3

            sage: category(ZZ['x'])
            Join of Category of unique factorization domains
             and Category of commutative algebras over
              (euclidean domains and infinite enumerated sets and metric spaces)
             and Category of infinite sets
            sage: category(GF(7)['x'])
            Join of Category of euclidean domains
             and Category of commutative algebras over
              (finite enumerated fields and subquotients of monoids and quotients of semigroups) and Category of infinite sets

        TESTS:

        Verify that :trac:`15232` has been resolved::

            sage: K.<x> = FunctionField(QQ)
            sage: R.<y> = K[]
            sage: TestSuite(R).run()

        Check that category for zero ring::

            sage: PolynomialRing(Zmod(1), 'x').category()
            Category of finite commutative algebras over
            (finite commutative rings and subquotients of monoids and
            quotients of semigroups and finite enumerated sets)

        Check `is_finite` inherited from category (:trac:`24432`)::

            sage: Zmod(1)['x'].is_finite()
            True

            sage: GF(7)['x'].is_finite()
            False

            sage: Zmod(1)['x']['y'].is_finite()
            True

            sage: GF(7)['x']['y'].is_finite()
            False

        """
        # We trust that, if category is given, it is useful and does not need to be joined
        # with the default category
        if category is None:
            if base_ring.is_zero():
                category = categories.rings.Rings().Finite()
            else:
                category = polynomial_default_category(base_ring.category(), 1)
        self.__is_sparse = sparse
        if element_class:
            self._polynomial_class = element_class
        else:
            if sparse:
                self._polynomial_class = polynomial_element_generic.Polynomial_generic_sparse
            else:
                from sage.rings.polynomial import polynomial_element
                self._polynomial_class = polynomial_element.Polynomial_generic_dense
        self.Element = self._polynomial_class
        self.__cyclopoly_cache = {}
        self._has_singular = False
        sage.algebras.algebra.Algebra.__init__(self, base_ring, names=name, normalize=True, category=category)
        self._populate_coercion_lists_(convert_method_name='_polynomial_')

    def __reduce__(self):
        from sage.rings.polynomial.polynomial_ring_constructor import unpickle_PolynomialRing
        args = (self.base_ring(), self.variable_names(), None, self.is_sparse())
        return unpickle_PolynomialRing, args

    def _element_constructor_(self, x=None, check=True, is_gen=False,
                              construct=False, **kwds):
        r"""
        Convert ``x`` into this univariate polynomial ring,
        possibly non-canonically.

        Conversion from power series::

            sage: R.<x> = QQ[]
            sage: R(1 + x + x^2 + O(x^3))
            x^2 + x + 1

        Stacked polynomial rings coerce into constants if possible. First,
        the univariate case::

            sage: R.<x> = QQ[]
            sage: S.<u> = R[]
            sage: S(u + 2)
            u + 2
            sage: S(x + 3)
            x + 3
            sage: S(x + 3).degree()
            0

        Second, the multivariate case::

            sage: R.<x,y> = QQ[]
            sage: S.<u> = R[]
            sage: S(x + 2*y)
            x + 2*y
            sage: S(x + 2*y).degree()
            0
            sage: S(u + 2*x)
            u + 2*x
            sage: S(u + 2*x).degree()
            1

        Foreign polynomial rings coerce into the highest ring; the point
        here is that an element of T could coerce to an element of R or an
        element of S; it is anticipated that an element of T is more likely
        to be "the right thing" and is historically consistent.

        ::

            sage: R.<x> = QQ[]
            sage: S.<u> = R[]
            sage: T.<a> = QQ[]
            sage: S(a)
            u

        Coercing in pari elements::

            sage: QQ['x'](pari('[1,2,3/5]'))
            3/5*x^2 + 2*x + 1
            sage: QQ['x'](pari('(-1/3)*x^10 + (2/3)*x - 1/5'))
            -1/3*x^10 + 2/3*x - 1/5

        Coercing strings::

            sage: QQ['y']('-y')
            -y

        TESTS:

        Python 3 range is allowed::

            sage: from six.moves import range
            sage: R = PolynomialRing(ZZ,'x')
            sage: R(range(4))
            3*x^3 + 2*x^2 + x

        This shows that the issue at :trac:`4106` is fixed::

            sage: x = var('x')
            sage: R = IntegerModRing(4)
            sage: S = R['x']
            sage: S(x)
            x

        Throw a TypeError if any of the coefficients cannot be coerced
        into the base ring (:trac:`6777`)::

            sage: RealField(300)['x']( [ 1, ComplexField(300).gen(), 0 ])
            Traceback (most recent call last):
            ...
            TypeError: unable to convert '1.00...00*I' to a real number

        Check that the bug in :trac:`11239` is fixed::

            sage: K.<a> = GF(5^2, prefix='z')
            sage: L.<b> = GF(5^4, prefix='z')
            sage: f = K['x'].gen() + a
            sage: L['x'](f)
            x + b^3 + b^2 + b + 3

        A test from :trac:`14485` ::

            sage: x = SR.var('x')
            sage: QQbar[x](x^6+x^5+x^4-x^3+x^2-x+2/5)
            x^6 + x^5 + x^4 - x^3 + x^2 - x + 2/5
        """
        C = self.element_class
        if isinstance(x, (list, tuple)):
            return C(self, x, check=check, is_gen=False, construct=construct)
        if isinstance(x, range):
            return C(self, list(x), check=check, is_gen=False,
                     construct=construct)
        if isinstance(x, Element):
            P = x.parent()
            if P is self:
                return x
            elif P is self.base_ring():
                # It *is* the base ring, hence, we should not need to check.
                # Moreover, if x is equal to zero then we usually need to
                # provide [] to the polynomial class, not [x], if we don't want
                # to check (normally, polynomials like to strip trailing zeroes).
                # However, in the padic case, we WANT that trailing
                # zeroes are not stripped, because O(5)==0, but still it must
                # not be forgotten. It should be the job of the __init__ method
                # to decide whether to strip or not to strip.
                return C(self, [x], check=False, is_gen=False,
                         construct=construct)
            elif P == self.base_ring():
                return C(self, [x], check=True, is_gen=False,
                         construct=construct)
        if isinstance(x, SingularElement) and self._has_singular:
            self._singular_().set_ring()
            try:
                return x.sage_poly(self)
            except Exception:
                raise TypeError("Unable to coerce singular object")
        elif isinstance(x , str):
            try:
                from sage.misc.parser import Parser, LookupNameMaker
                R = self.base_ring()
                p = Parser(Integer, R, LookupNameMaker({self.variable_name(): self.gen()}, R))
                return self(p.parse(x))
            except NameError:
                raise TypeError("Unable to coerce string")
        elif isinstance(x, FractionFieldElement):
            if x.denominator().is_unit():
                x = x.numerator() * x.denominator().inverse_of_unit()
            else:
                raise TypeError("denominator must be a unit")
        elif isinstance(x, pari_gen):
            if x.type() == 't_RFRAC':
                raise TypeError("denominator must be a unit")
            if x.type() != 't_POL':
                x = x.Polrev()
        elif isinstance(x, FiniteRingElement):
            try:
                return self(x.polynomial())
            except AttributeError:
                pass
        elif isinstance(x, sage.rings.power_series_ring_element.PowerSeries):
            x = x.truncate()
        return C(self, x, check, is_gen, construct=construct, **kwds)

    @classmethod
    def _implementation_names(cls, implementation, base_ring, sparse=False):
        """
        Check whether this class can handle the implementation
        ``implementation`` over the given base ring and sparseness.

        This is a simple wrapper around :meth:`_implementation_names_impl`
        which does the real work.

        .. NOTE::

            It is assumed that the ``base_ring`` argument is a base ring
            which the class can handle.

        INPUT:

        - ``implementation`` -- either a string denoting a specific
          implementation or ``None`` for the default.

        - ``base_ring`` -- the base ring for the polynomial ring.

        - ``sparse`` -- (boolean) whether the implementation is sparse.

        OUTPUT:

        - if the implementation is supported, the output is a list of
          all names (possibly including ``None``) which refer to the
          given implementation. The first element of the list is the
          canonical name. If the ``__init__`` method does not take an
          ``implementation`` keyword, then the first element must be
          ``None``.

        - if the implementation is not supported, raise a
          ``ValueError``.

        EXAMPLES::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_general
            sage: PolynomialRing_general._implementation_names(None, ZZ, True)
            [None, 'generic']
            sage: PolynomialRing_general._implementation_names("generic", ZZ, True)
            [None, 'generic']
            sage: PolynomialRing_general._implementation_names("xyzzy", ZZ, True)
            Traceback (most recent call last):
            ...
            ValueError: unknown implementation 'xyzzy' for sparse polynomial rings over Integer Ring
        """
        names = cls._implementation_names_impl(implementation, base_ring, sparse)
        if names is NotImplemented:
            raise ValueError("unknown implementation %r for %s polynomial rings over %r" %
                    (implementation, "sparse" if sparse else "dense", base_ring))
        assert isinstance(names, list)
        assert implementation in names
        return names

    @staticmethod
    def _implementation_names_impl(implementation, base_ring, sparse):
        """
        The underlying implementation of :meth:`_implementation_names`.

        The behaviour is exactly the same, except that an unknown
        implementation returns ``NotImplemented`` instead of raising
        ``ValueError``.

        EXAMPLES::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_general
            sage: PolynomialRing_general._implementation_names_impl("xyzzy", ZZ, True)
            NotImplemented
        """
        if implementation is None or implementation == "generic":
            return [None, "generic"]
        return NotImplemented

    def is_integral_domain(self, proof = True):
        """
        EXAMPLES::

            sage: ZZ['x'].is_integral_domain()
            True
            sage: Integers(8)['x'].is_integral_domain()
            False
        """
        return self.base_ring().is_integral_domain(proof)

    def is_unique_factorization_domain(self, proof = True):
        """
        EXAMPLES::

            sage: ZZ['x'].is_unique_factorization_domain()
            True
            sage: Integers(8)['x'].is_unique_factorization_domain()
            False
        """
        return self.base_ring().is_unique_factorization_domain(proof)

    def is_noetherian(self):
        return self.base_ring().is_noetherian()

    def some_elements(self):
        r"""
        Return a list of polynomials.

        This is typically used for running generic tests.

        EXAMPLES::

            sage: R.<x> = QQ[]
            sage: R.some_elements()
            [x, 0, 1, 1/2, x^2 + 2*x + 1, x^3, x^2 - 1, x^2 + 1, 2*x^2 + 2]
        """
        # the comments in the following lines describe the motivation for
        # adding these elements, they are not accurate over all rings and in
        # all contexts
        R = self.base_ring()
        # Doing things this way is a little robust against rings where
        #    2 might not convert in
        one = R.one()
        return [self.gen(),
            self.zero(), self(one), self(R.an_element()), # elements of the base ring
            self([one,2*one,one]), # a square
            self([0,0,0,one]), # a power but not a square
            self([-one,0,one]), # a reducible element
            self([one,0,one]), # an irreducible element
            self([2*one,0,2*one]), # an element with non-trivial content
        ]

    @cached_method
    def flattening_morphism(self):
        r"""
        Return the flattening morphism of this polynomial ring

        EXAMPLES::

            sage: QQ['a','b']['x'].flattening_morphism()
            Flattening morphism:
              From: Univariate Polynomial Ring in x over Multivariate Polynomial Ring in a, b over Rational Field
              To:   Multivariate Polynomial Ring in a, b, x over Rational Field

            sage: QQ['x'].flattening_morphism()
            Identity endomorphism of Univariate Polynomial Ring in x over Rational Field
        """
        from .multi_polynomial_ring import is_MPolynomialRing
        base = self.base_ring()
        if is_PolynomialRing(base) or is_MPolynomialRing(base):
            from .flatten import FlatteningMorphism
            return FlatteningMorphism(self)
        else:
            return IdentityMorphism(self)

    def construction(self):
        return categories.pushout.PolynomialFunctor(self.variable_name(), sparse=self.__is_sparse), self.base_ring()

    def completion(self, p, prec=20, extras=None):
        """
        Return the completion of self with respect to the irreducible
        polynomial p. Currently only implemented for p=self.gen(), i.e. you
        can only complete R[x] with respect to x, the result being a ring
        of power series in x. The prec variable controls the precision used
        in the power series ring.

        EXAMPLES::

            sage: P.<x>=PolynomialRing(QQ)
            sage: P
            Univariate Polynomial Ring in x over Rational Field
            sage: PP=P.completion(x)
            sage: PP
            Power Series Ring in x over Rational Field
            sage: f=1-x
            sage: PP(f)
            1 - x
            sage: 1/f
            -1/(x - 1)
            sage: 1/PP(f)
            1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12 + x^13 + x^14 + x^15 + x^16 + x^17 + x^18 + x^19 + O(x^20)
        """
        if str(p) == self._names[0]:
            from sage.rings.power_series_ring import PowerSeriesRing
            return PowerSeriesRing(self.base_ring(), name=self._names[0], default_prec=prec)
        else:
            raise TypeError("Cannot complete %s with respect to %s" % (self, p))

    def _coerce_map_from_base_ring(self):
        """
        Return a coercion map from the base ring of ``self``.

        EXAMPLES::

            sage: R.<x> = QQ[]
            sage: R.coerce_map_from(QQ)
            Polynomial base injection morphism:
              From: Rational Field
              To:   Univariate Polynomial Ring in x over Rational Field
            sage: R.coerce_map_from(ZZ)
            Composite map:
              From: Integer Ring
              To:   Univariate Polynomial Ring in x over Rational Field
              Defn:   Natural morphism:
                      From: Integer Ring
                      To:   Rational Field
                    then
                      Polynomial base injection morphism:
                      From: Rational Field
                      To:   Univariate Polynomial Ring in x over Rational Field
            sage: R.coerce_map_from(GF(7))
        """
        return PolynomialBaseringInjection(self.base_ring(), self)

    def _coerce_map_from_(self, P):
        """
        The rings that canonically coerce to this polynomial ring are:

        - this ring itself

        - any ring that canonically coerces to the base ring of this ring.

        - polynomial rings in the same variable over any base ring that
          canonically coerces to the base ring of this ring.

        - a multivariate polynomial ring P such that self's variable name
          is among the variable names of P, and the ring obtained by
          removing that variable is different from the base ring of self,
          but coerces into it. (see :trac:`813` for a discussion of this)

        Caveat: There is no coercion from a dense into a sparse
        polynomial ring. So, when adding a dense and a sparse
        polynomial, the result will be dense. See :trac:`9944`.

        EXAMPLES::

            sage: R = QQ['x']
            sage: R.has_coerce_map_from(ZZ['x'])
            True
            sage: R.has_coerce_map_from(ZZ['y'])
            False

        Here we test against the change in the coercions introduced
        in :trac:`9944`::

            sage: R.<x> = PolynomialRing(QQ, sparse=True)
            sage: S.<x> = QQ[]
            sage: (R.0+S.0).parent()
            Univariate Polynomial Ring in x over Rational Field
            sage: (S.0+R.0).parent()
            Univariate Polynomial Ring in x over Rational Field

        Here we test a feature that was implemented in :trac:`813`::

            sage: P = QQ['x','y']
            sage: Q = Frac(QQ['x'])['y']
            sage: Q.has_coerce_map_from(P)
            True
            sage: P.0+Q.0
            y + x

        In order to avoid bidirectional coercions (which are generally
        problematic), we only have a coercion from P to Q if the base
        ring of Q is more complicated than "P minus one variable"::

            sage: Q = QQ['x']['y']
            sage: P.has_coerce_map_from(Q)
            True
            sage: Q.has_coerce_map_from(P)
            False
            sage: Q.base_ring() is P.remove_var(Q.variable_name())
            True

        Over the integers, there is a coercion from the NTL and generic
        implementation to the default FLINT implementation::

            sage: R = PolynomialRing(ZZ, 't', implementation="NTL")
            sage: S = PolynomialRing(ZZ, 't', implementation="FLINT")
            sage: T = PolynomialRing(ZZ, 't', implementation="generic")
            sage: R.has_coerce_map_from(S)
            False
            sage: R.has_coerce_map_from(T)
            False
            sage: S.has_coerce_map_from(T)
            True
            sage: S.has_coerce_map_from(R)
            True
            sage: T.has_coerce_map_from(R)
            False
            sage: T.has_coerce_map_from(S)
            False
        """
        base_ring = self.base_ring()
        # handle constants that canonically coerce into self.base_ring()
        # first, if possible
        try:
            connecting = base_ring.coerce_map_from(P)
            if connecting is not None:
                return self.coerce_map_from(base_ring) * connecting
        except TypeError:
            pass

        # polynomial rings in the same variable over a base that canonically
        # coerces into self.base_ring()
        if is_PolynomialRing(P):
            if self.construction()[0] != P.construction()[0]:
                # Construction (including variable names) must be the
                # same to allow coercion
                return False
            self_sparse = self.is_sparse()
            P_sparse = P.is_sparse()
            if self_sparse and not P_sparse:
                # Coerce only sparse -> dense
                return False

            if P.base_ring() is base_ring:
                # Same base ring but different implementations.
                # Ideally, we should avoid cyclic coercions (a coercion
                # from A to B and also from B to A), but this is
                # currently hard to do:
                # see https://trac.sagemath.org/ticket/24319
                if not self_sparse and P_sparse:
                    # Always allow coercion sparse -> dense
                    pass
                elif base_ring is ZZ:
                    # Over ZZ, only allow coercion from any ZZ['x']
                    # implementation to the default FLINT implementation
                    if self.element_class is not Polynomial_integer_dense_flint:
                        return None
                # Other rings: always allow coercion
                # To be fixed in Trac #24319
            f = base_ring.coerce_map_from(P.base_ring())
            if f is None:
                return None
            from sage.rings.homset import RingHomset
            from sage.rings.polynomial.polynomial_ring_homomorphism import PolynomialRingHomomorphism_from_base
            return PolynomialRingHomomorphism_from_base(RingHomset(P, self), f)

        # Last, we consider multivariate polynomial rings:
        from sage.rings.polynomial.multi_polynomial_ring import is_MPolynomialRing
        if is_MPolynomialRing(P) and self.variable_name() in P.variable_names():
            P_ = P.remove_var(self.variable_name())
            return self.base_ring()!=P_ and self.base_ring().has_coerce_map_from(P_)

    def _magma_init_(self, magma):
        """
        Used in converting this ring to the corresponding ring in MAGMA.

        EXAMPLES::

            sage: R = QQ['y']
            sage: R._magma_init_(magma)                     # optional - magma
            'SageCreateWithNames(PolynomialRing(_sage_ref...),["y"])'
            sage: S = magma(R)                              # optional - magma
            sage: S                                         # optional - magma
            Univariate Polynomial Ring in y over Rational Field
            sage: S.1                                       # optional - magma
            y
            sage: magma(PolynomialRing(GF(7), 'x'))         # optional - magma
            Univariate Polynomial Ring in x over GF(7)
            sage: magma(PolynomialRing(GF(49,'a'), 'x'))    # optional - magma
            Univariate Polynomial Ring in x over GF(7^2)
            sage: magma(PolynomialRing(PolynomialRing(ZZ,'w'), 'x')) # optional - magma
            Univariate Polynomial Ring in x over Univariate Polynomial Ring in w over Integer Ring

        Watch out, Magma has different semantics from Sage, i.e., in Magma
        there is a unique univariate polynomial ring, and the variable name
        has no intrinsic meaning (it only impacts printing), so can't be
        reliably set because of caching.

        ::

            sage: m = Magma()            # new magma session; optional - magma
            sage: m(QQ['w'])                                # optional - magma
            Univariate Polynomial Ring in w over Rational Field
            sage: m(QQ['x'])                                # optional - magma
            Univariate Polynomial Ring in x over Rational Field
            sage: m(QQ['w'])   # same magma object, now prints as x; optional - magma
            Univariate Polynomial Ring in x over Rational Field

        A nested example over a Givaro finite field::

            sage: k.<a> = GF(9)
            sage: R.<x> = k[]
            sage: magma(a^2*x^3 + (a+1)*x + a)              # optional - magma
            a^2*x^3 + a^2*x + a
        """
        B = magma(self.base_ring())
        Bref = B._ref()
        s = 'PolynomialRing(%s)'%(Bref)
        return magma._with_names(s, self.variable_names())

    def _gap_init_(self, gap=None):
        """
        String for representing this polynomial ring in GAP.

        INPUT:

        - ``gap`` -- (optional GAP instance) used for representing the base ring

        EXAMPLES::

            sage: R.<z> = ZZ[]
            sage: gap(R)
            PolynomialRing( Integers, ["z"] )
            sage: gap(R) is gap(R)
            True
            sage: gap(z^2 + z)
            z^2+z

        A univariate polynomial ring over a multivariate polynomial
        ring over a number field::

            sage: Q.<t> = QQ[]
            sage: K.<tau> = NumberField(t^2+t+1)
            sage: P.<x,y> = K[]
            sage: S.<z> = P[]
            sage: gap(S)
            PolynomialRing( PolynomialRing( <algebraic extension over the Rationals of degree 2>, ["x", "y"] ), ["z"] )
            sage: gap(S) is gap(S)
            True
        """
        if gap is not None:
            base_ring = gap(self.base_ring()).name()
        else:
            base_ring = self.base_ring()._gap_init_()
        return 'PolynomialRing(%s, ["%s"])'%(base_ring, self.variable_name())

    def _sage_input_(self, sib, coerced):
        r"""
        Produce an expression which will reproduce this value when
        evaluated.

        EXAMPLES::

            sage: sage_input(GF(5)['x']['y'], verify=True)
            # Verified
            GF(5)['x']['y']
            sage: from sage.misc.sage_input import SageInputBuilder
            sage: ZZ['z']._sage_input_(SageInputBuilder(), False)
            {constr_parent: {subscr: {atomic:ZZ}[{atomic:'z'}]} with gens: ('z',)}
        """
        base = sib(self.base_ring())
        sie = base[self.variable_name()]
        gens_syntax = sib.empty_subscript(base)
        return sib.parent_with_gens(self, sie, self.variable_names(), 'R',
                                    gens_syntax=gens_syntax)

    def _macaulay2_init_(self, macaulay2=None):
        """
        EXAMPLES::

            sage: R = QQ['x']
            sage: macaulay2(R).describe()  # optional - macaulay2
            QQ[x, Degrees => {1}, Heft => {1}, MonomialOrder => {MonomialSize => 16},
                                                                {GRevLex => {1}    }
                                                                {Position => Up    }
            --------------------------------------------------------------------------------
            DegreeRank => 1]

        TESTS:

        Check that results are cached (:trac:`28074`)::

            sage: R = ZZ['t']
            sage: macaulay2(R) is macaulay2(R)  # optional - macaulay2
            True
        """
        if macaulay2 is None:
            from sage.interfaces.macaulay2 import macaulay2 as m2_default
            macaulay2 = m2_default
        return macaulay2._macaulay2_input_ring(self.base_ring(), self.gens())


    def _is_valid_homomorphism_(self, codomain, im_gens, base_map=None):
        """
        EXAMPLES::

            sage: R.<x> = QQ[]
            sage: R._is_valid_homomorphism_(GF(7), [5])
            False
            sage: R._is_valid_homomorphism_(Qp(7), [5])
            True
        """
        # Since poly rings are free, any image of the gen
        # determines a homomorphism
        if base_map is None:
            # If no base map is given, the only requirement is that the
            # base ring coerces into the codomain
            return codomain.has_coerce_map_from(self.base_ring())
        return True

    #    Polynomial rings should be unique parents. Hence,
    #    no need for any comparison method

    def __hash__(self):
        # should be faster than just relying on the string representation
        try:
            return self._cached_hash
        except AttributeError:
            pass
        h = self._cached_hash = hash((self.base_ring(),self.variable_name()))
        return h

    def _repr_(self):
        try:
            return self._cached_repr
        except AttributeError:
            pass
        s = "Univariate Polynomial Ring in %s over %s"%(
                self.variable_name(), self.base_ring())
        if self.is_sparse():
            s = "Sparse " + s
        self._cached_repr = s
        return s

    def _latex_(self):
        r"""
        EXAMPLES::

            sage: S.<alpha12>=ZZ[]
            sage: latex(S)
            \Bold{Z}[\alpha_{12}]
        """
        return "%s[%s]"%(latex.latex(self.base_ring()), self.latex_variable_names()[0])

    def base_extend(self, R):
        """
        Return the base extension of this polynomial ring to R.

        EXAMPLES::

            sage: R.<x> = RR[]; R
            Univariate Polynomial Ring in x over Real Field with 53 bits of precision
            sage: R.base_extend(CC)
            Univariate Polynomial Ring in x over Complex Field with 53 bits of precision
            sage: R.base_extend(QQ)
            Traceback (most recent call last):
            ...
            TypeError: no such base extension
            sage: R.change_ring(QQ)
            Univariate Polynomial Ring in x over Rational Field
        """
        from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

        if R.has_coerce_map_from(self.base_ring()):
            return PolynomialRing(R, names=self.variable_name(), sparse=self.is_sparse())
        else:
            raise TypeError("no such base extension")

    def change_ring(self, R):
        """
        Return the polynomial ring in the same variable as self over R.

        EXAMPLES::

            sage: R.<ZZZ> = RealIntervalField() []; R
            Univariate Polynomial Ring in ZZZ over Real Interval Field with 53 bits of precision
            sage: R.change_ring(GF(19^2,'b'))
            Univariate Polynomial Ring in ZZZ over Finite Field in b of size 19^2
        """
        from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

        return PolynomialRing(R, names=self.variable_name(), sparse=self.is_sparse())

    def change_var(self, var):
        r"""
        Return the polynomial ring in variable var over the same base
        ring.

        EXAMPLES::

            sage: R.<x> = ZZ[]; R
            Univariate Polynomial Ring in x over Integer Ring
            sage: R.change_var('y')
            Univariate Polynomial Ring in y over Integer Ring
        """
        from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

        return PolynomialRing(self.base_ring(), names = var, sparse=self.is_sparse())

    def extend_variables(self, added_names, order = 'degrevlex'):
        r"""
        Returns a multivariate polynomial ring with the same base ring but
        with added_names as additional variables.

        EXAMPLES::

            sage: R.<x> = ZZ[]; R
            Univariate Polynomial Ring in x over Integer Ring
            sage: R.extend_variables('y, z')
            Multivariate Polynomial Ring in x, y, z over Integer Ring
            sage: R.extend_variables(('y', 'z'))
            Multivariate Polynomial Ring in x, y, z over Integer Ring
        """
        from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

        if isinstance(added_names, str):
            added_names = added_names.split(',')
        return PolynomialRing(self.base_ring(), names = self.variable_names() + tuple(added_names), order = order)

    def variable_names_recursive(self, depth=sage.rings.infinity.infinity):
        r"""
        Return the list of variable names of this ring and its base rings,
        as if it were a single multi-variate polynomial.

        INPUT:

        - ``depth`` -- an integer or :mod:`Infinity <sage.rings.infinity>`.

        OUTPUT:

        A tuple of strings.

        EXAMPLES::

            sage: R = QQ['x']['y']['z']
            sage: R.variable_names_recursive()
            ('x', 'y', 'z')
            sage: R.variable_names_recursive(2)
            ('y', 'z')
        """
        if depth <= 0:
            return ()
        elif depth == 1:
            return self.variable_names()
        else:
            my_vars = self.variable_names()
            try:
               return self.base_ring().variable_names_recursive(depth - len(my_vars)) + my_vars
            except AttributeError:
                return my_vars

    def _mpoly_base_ring(self, variables=None):
        r"""
        Returns the base ring if this is viewed as a polynomial ring over
        ``variables``. See also
        Polynomial._mpoly_dict_recursive
        """
        if variables is None:
            variables = self.variable_names_recursive()
        variables = list(variables)
        var = self.variable_name()
        if not var in variables:
            return self
        else:
            try:
                return self.base_ring()._mpoly_base_ring(variables[:variables.index(var)])
            except AttributeError:
                return self.base_ring()

    def characteristic(self):
        """
        Return the characteristic of this polynomial ring, which is the
        same as that of its base ring.

        EXAMPLES::

            sage: R.<ZZZ> = RealIntervalField() []; R
            Univariate Polynomial Ring in ZZZ over Real Interval Field with 53 bits of precision
            sage: R.characteristic()
            0
            sage: S = R.change_ring(GF(19^2,'b')); S
            Univariate Polynomial Ring in ZZZ over Finite Field in b of size 19^2
            sage: S.characteristic()
            19
        """
        return self.base_ring().characteristic()

    def cyclotomic_polynomial(self, n):
        """
        Return the nth cyclotomic polynomial as a polynomial in this
        polynomial ring. For details of the implementation, see the
        documentation for
        :func:`sage.rings.polynomial.cyclotomic.cyclotomic_coeffs`.

        EXAMPLES::

            sage: R = ZZ['x']
            sage: R.cyclotomic_polynomial(8)
            x^4 + 1
            sage: R.cyclotomic_polynomial(12)
            x^4 - x^2 + 1
            sage: S = PolynomialRing(FiniteField(7), 'x')
            sage: S.cyclotomic_polynomial(12)
            x^4 + 6*x^2 + 1
            sage: S.cyclotomic_polynomial(1)
            x + 6

        TESTS:

        Make sure it agrees with other systems for the trivial case::

            sage: ZZ['x'].cyclotomic_polynomial(1)
            x - 1
            sage: gp('polcyclo(1)')
            x - 1
        """
        if n <= 0:
            raise ArithmeticError("n=%s must be positive"%n)
        elif n == 1:
            return self.gen() - 1
        else:
            return self(cyclotomic.cyclotomic_coeffs(n), check=True)

    @cached_method
    def gen(self, n=0):
        """
        Return the indeterminate generator of this polynomial ring.

        EXAMPLES::

            sage: R.<abc> = Integers(8)[]; R
            Univariate Polynomial Ring in abc over Ring of integers modulo 8
            sage: t = R.gen(); t
            abc
            sage: t.is_gen()
            True

        An identical generator is always returned.

        ::

            sage: t is R.gen()
            True
        """
        if n != 0:
            raise IndexError("generator n not defined")
        return self.element_class(self, [0,1], is_gen=True)

    def gens_dict(self):
        """
        Return a dictionary whose entries are ``{name:variable,...}``,
        where ``name`` stands for the variable names of this
        object (as strings) and ``variable`` stands for the corresponding
        generators (as elements of this object).

        EXAMPLES::

            sage: R.<y,x,a42> = RR[]
            sage: R.gens_dict()
            {'a42': a42, 'x': x, 'y': y}
        """
        gens = self.gens()
        names = self.variable_names()
        assert len(gens) == len(names)
        return dict(zip(names, gens))

    def parameter(self):
        """
        Return the generator of this polynomial ring.

        This is the same as ``self.gen()``.
        """
        return self.gen()

    @cached_method
    def is_exact(self):
        return self.base_ring().is_exact()

    def is_field(self, proof = True):
        """
        Return False, since polynomial rings are never fields.

        EXAMPLES::

            sage: R.<z> = Integers(2)[]; R
            Univariate Polynomial Ring in z over Ring of integers modulo 2 (using GF2X)
            sage: R.is_field()
            False
        """
        return False

    def is_sparse(self):
        """
        Return true if elements of this polynomial ring have a sparse
        representation.

        EXAMPLES::

            sage: R.<z> = Integers(8)[]; R
            Univariate Polynomial Ring in z over Ring of integers modulo 8
            sage: R.is_sparse()
            False
            sage: R.<W> = PolynomialRing(QQ, sparse=True); R
            Sparse Univariate Polynomial Ring in W over Rational Field
            sage: R.is_sparse()
            True
        """
        return self.__is_sparse

    def monomial(self, exponent):
        """
        Return the monomial with the ``exponent``.

        INPUT:

        - ``exponent`` -- nonnegative integer

        EXAMPLES::

            sage: R.<x> = PolynomialRing(ZZ)
            sage: R.monomial(5)
            x^5
            sage: e=(10,)
            sage: R.monomial(*e)
            x^10
            sage: m = R.monomial(100)
            sage: R.monomial(m.degree()) == m
            True
        """
        return self({exponent:self.base_ring().one()})

    def krull_dimension(self):
        """
        Return the Krull dimension of this polynomial ring, which is one
        more than the Krull dimension of the base ring.

        EXAMPLES::

            sage: R.<x> = QQ[]
            sage: R.krull_dimension()
            1
            sage: R.<z> = GF(9,'a')[]; R
            Univariate Polynomial Ring in z over Finite Field in a of size 3^2
            sage: R.krull_dimension()
            1
            sage: S.<t> = R[]
            sage: S.krull_dimension()
            2
            sage: for n in range(10):
            ....:  S = PolynomialRing(S,'w')
            sage: S.krull_dimension()
            12
        """
        return self.base_ring().krull_dimension() + 1

    def ngens(self):
        """
        Return the number of generators of this polynomial ring, which is 1
        since it is a univariate polynomial ring.

        EXAMPLES::

            sage: R.<z> = Integers(8)[]; R
            Univariate Polynomial Ring in z over Ring of integers modulo 8
            sage: R.ngens()
            1
        """
        return 1

    def random_element(self, degree=(-1,2), *args, **kwds):
        r"""
        Return a random polynomial of given degree or with given degree bounds.

        INPUT:

        -  ``degree`` - optional integer for fixing the degree or
           or a tuple of minimum and maximum degrees. By default set to
           ``(-1,2)``.

        -  ``*args, **kwds`` - Passed on to the ``random_element`` method for
           the base ring

        EXAMPLES::

            sage: R.<x> = ZZ[]
            sage: R.random_element(10, 5,10)
            5*x^10 + 5*x^9 + 9*x^8 + 8*x^7 + 6*x^6 + 8*x^5 + 8*x^4 + 9*x^3 + 8*x^2 + 8*x + 8
            sage: R.random_element(6)
            x^6 - 2*x^5 - 2*x^3 + 2*x^2 - 3*x
            sage: R.random_element(6)
            -x^6 + x^5 + x^2 - x
            sage: R.random_element(6)
            -5*x^6 + x^5 + 14*x^4 - x^3 + x^2 - x + 4

        If a tuple of two integers is given for the degree argument, a degree
        is first uniformly chosen, then a polynomial of that degree is given::

            sage: R.random_element(degree=(0,8))
            4*x^4 + 2*x^3 - x + 4
            sage: R.random_element(degree=(0,8))
            x + 1

        Note that the zero polynomial has degree ``-1``, so if you want to
        consider it set the minimum degree to ``-1``::

            sage: any(R.random_element(degree=(-1,2),x=-1,y=1) == R.zero() for _ in range(100))
            True

        TESTS::

            sage: R.random_element(degree=[5])
            Traceback (most recent call last):
            ...
            ValueError: degree argument must be an integer or a tuple of 2 integers (min_degree, max_degree)

            sage: R.random_element(degree=(5,4))
            Traceback (most recent call last):
            ...
            ValueError: minimum degree must be less or equal than maximum degree

        Check that :trac:`16682` is fixed::

            sage: R = PolynomialRing(GF(2), 'z')
            sage: for _ in range(100):
            ....:     d = randint(-1,20)
            ....:     P = R.random_element(degree=d)
            ....:     assert P.degree() == d, "problem with {} which has not degree {}".format(P,d)

            sage: R.random_element(degree=-2)
            Traceback (most recent call last):
            ...
            ValueError: degree should be an integer greater or equal than -1
        """
        R = self.base_ring()

        if isinstance(degree, (list, tuple)):
            if len(degree) != 2:
                raise ValueError("degree argument must be an integer or a tuple of 2 integers (min_degree, max_degree)")
            if degree[0] > degree[1]:
                raise ValueError("minimum degree must be less or equal than maximum degree")
        else:
            degree = (degree,degree)

        if degree[0] <= -2:
            raise ValueError("degree should be an integer greater or equal than -1")

        # If the coefficient range only contains 0, then
        # * if the degree range includes -1, return the zero polynomial,
        # * otherwise raise a value error
        if args == (0, 1):
            if degree[0] == -1:
                return self.zero()
            else:
                raise ValueError("No polynomial of degree >= 0 has all coefficients zero")

        # Pick a random degree
        d = randint(degree[0], degree[1])

        # If degree is -1, return the 0 polynomial
        if d == -1:
            return self.zero()

        # If degree is 0, return a random constant term
        if d == 0:
            return self(R._random_nonzero_element(*args, **kwds))

        # Pick random coefficients
        p = self([R.random_element(*args, **kwds) for _ in range(d)])

        # Add non-zero leading coefficient
        p += R._random_nonzero_element(*args, **kwds) * self.gen() ** d

        return p

    def _monics_degree( self, of_degree ):
        """
        Refer to monics() for full documentation.
        """
        base = self.base_ring()
        for coeffs in sage.misc.mrange.xmrange_iter([[base.one()]]+[base]*of_degree):
            # Each iteration returns a *new* list!
            # safe to mutate the return
            coeffs.reverse()
            yield self(coeffs)

    def _monics_max( self, max_degree ):
        """
        Refer to monics() for full documentation.
        """
        for degree in range(max_degree + 1):
            for m in self._monics_degree( degree ):
                yield m

    def _polys_degree( self, of_degree ):
        """
        Refer to polynomials() for full documentation.
        """
        base = self.base_ring()
        base0 = base.zero()
        for leading_coeff in base:
            if leading_coeff != base0:
                for lt1 in sage.misc.mrange.xmrange_iter([base]*(of_degree)):
                    # Each iteration returns a *new* list!
                    # safe to mutate the return
                    coeffs = [leading_coeff] + lt1
                    coeffs.reverse()
                    yield self(coeffs)

    def _polys_max( self, max_degree ):
        """
        Refer to polynomials() for full documentation.
        """
        base = self.base_ring()
        for coeffs in sage.misc.mrange.xmrange_iter([base]*(max_degree+1)):
            # Each iteration returns a *new* list!
            # safe to mutate the return
            coeffs.reverse()
            yield self(coeffs)

    @lazy_attribute
    def _Karatsuba_threshold(self):
        """
        Return the default Karatsuba threshold.

        EXAMPLES::

            sage: R.<x> = QQbar[]
            sage: R._Karatsuba_threshold
            8
            sage: MS = MatrixSpace(ZZ, 2, 2)
            sage: R.<x> = MS[]
            sage: R._Karatsuba_threshold
            0
        """
        base_ring = self.base_ring()
        if is_PolynomialRing(base_ring):
            return 0
        from sage.matrix.matrix_space import MatrixSpace
        if isinstance(base_ring, MatrixSpace):
            return 0
        from sage.rings.fraction_field import FractionField_generic
        if isinstance(base_ring, FractionField_generic):
            return 1 << 60
        # Generic default value
        return 8

    def karatsuba_threshold(self):
        """
        Return the Karatsuba threshold used for this ring by the method
        _mul_karatsuba to fall back to the schoolbook algorithm.

        EXAMPLES::

            sage: K = QQ['x']
            sage: K.karatsuba_threshold()
            8
            sage: K = QQ['x']['y']
            sage: K.karatsuba_threshold()
            0
        """
        return self._Karatsuba_threshold

    def set_karatsuba_threshold(self, Karatsuba_threshold):
        """
        Changes the default threshold for this ring in the method _mul_karatsuba
        to fall back to the schoolbook algorithm.

        .. warning::

           This method may have a negative performance impact in polynomial
           arithmetic. So use it at your own risk.

        EXAMPLES::

            sage: K = QQ['x']
            sage: K.karatsuba_threshold()
            8
            sage: K.set_karatsuba_threshold(0)
            sage: K.karatsuba_threshold()
            0
        """
        self._Karatsuba_threshold = int(Karatsuba_threshold)

    def polynomials( self, of_degree = None, max_degree = None ):
        """
        Return an iterator over the polynomials of specified degree.

        INPUT: Pass exactly one of:


        -  ``max_degree`` - an int; the iterator will generate
           all polynomials which have degree less than or equal to
           max_degree

        -  ``of_degree`` - an int; the iterator will generate
           all polynomials which have degree of_degree


        OUTPUT: an iterator

        EXAMPLES::

            sage: P = PolynomialRing(GF(3),'y')
            sage: for p in P.polynomials( of_degree = 2 ): print(p)
            y^2
            y^2 + 1
            y^2 + 2
            y^2 + y
            y^2 + y + 1
            y^2 + y + 2
            y^2 + 2*y
            y^2 + 2*y + 1
            y^2 + 2*y + 2
            2*y^2
            2*y^2 + 1
            2*y^2 + 2
            2*y^2 + y
            2*y^2 + y + 1
            2*y^2 + y + 2
            2*y^2 + 2*y
            2*y^2 + 2*y + 1
            2*y^2 + 2*y + 2
            sage: for p in P.polynomials( max_degree = 1 ): print(p)
            0
            1
            2
            y
            y + 1
            y + 2
            2*y
            2*y + 1
            2*y + 2
            sage: for p in P.polynomials( max_degree = 1, of_degree = 3 ): print(p)
            Traceback (most recent call last):
            ...
            ValueError: you should pass exactly one of of_degree and max_degree

        AUTHORS:

        - Joel B. Mohler
        """

        if self.base_ring().order() is sage.rings.infinity.infinity:
            raise NotImplementedError
        if of_degree is not None and max_degree is None:
            return self._polys_degree( of_degree )
        if max_degree is not None and of_degree is None:
            return self._polys_max( max_degree )
        raise ValueError("you should pass exactly one of of_degree and max_degree")

    def monics( self, of_degree = None, max_degree = None ):
        """
        Return an iterator over the monic polynomials of specified degree.

        INPUT: Pass exactly one of:


        -  ``max_degree`` - an int; the iterator will generate
           all monic polynomials which have degree less than or equal to
           max_degree

        -  ``of_degree`` - an int; the iterator will generate
           all monic polynomials which have degree of_degree


        OUTPUT: an iterator

        EXAMPLES::

            sage: P = PolynomialRing(GF(4,'a'),'y')
            sage: for p in P.monics( of_degree = 2 ): print(p)
            y^2
            y^2 + a
            y^2 + a + 1
            y^2 + 1
            y^2 + a*y
            y^2 + a*y + a
            y^2 + a*y + a + 1
            y^2 + a*y + 1
            y^2 + (a + 1)*y
            y^2 + (a + 1)*y + a
            y^2 + (a + 1)*y + a + 1
            y^2 + (a + 1)*y + 1
            y^2 + y
            y^2 + y + a
            y^2 + y + a + 1
            y^2 + y + 1
            sage: for p in P.monics( max_degree = 1 ): print(p)
            1
            y
            y + a
            y + a + 1
            y + 1
            sage: for p in P.monics( max_degree = 1, of_degree = 3 ): print(p)
            Traceback (most recent call last):
            ...
            ValueError: you should pass exactly one of of_degree and max_degree

        AUTHORS:

        - Joel B. Mohler
        """

        if self.base_ring().order() is sage.rings.infinity.infinity:
            raise NotImplementedError
        if of_degree is not None and max_degree is None:
            return self._monics_degree( of_degree )
        if max_degree is not None and of_degree is None:
            return self._monics_max( max_degree )
        raise ValueError("you should pass exactly one of of_degree and max_degree")


class PolynomialRing_commutative(PolynomialRing_general, commutative_algebra.CommutativeAlgebra):
    """
    Univariate polynomial ring over a commutative ring.
    """
    def __init__(self, base_ring, name=None, sparse=False, element_class=None, category=None):
        if base_ring not in _CommutativeRings:
            raise TypeError("Base ring %s must be a commutative ring."%repr(base_ring))
        # We trust that, if a category is given, that it is useful.
        if category is None:
            if base_ring.is_zero():
                category = categories.algebras.Algebras(base_ring.category()).Commutative().Finite()
            else:
                category = polynomial_default_category(base_ring.category(), 1)
        PolynomialRing_general.__init__(self, base_ring, name=name,
                sparse=sparse, element_class=element_class, category=category)

    def quotient_by_principal_ideal(self, f, names=None):
        """
        Return the quotient of this polynomial ring by the principal
        ideal (generated by) `f`.

        INPUT:

        - ``f`` - either a polynomial in ``self``, or a principal
          ideal of ``self``.

        EXAMPLES::

            sage: R.<x> = QQ[]
            sage: I = (x^2-1)*R
            sage: R.quotient_by_principal_ideal(I)
            Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x^2 - 1

        The same example, using the polynomial instead of the ideal,
        and customizing the variable name::

            sage: R.<x> = QQ[]
            sage: R.quotient_by_principal_ideal(x^2-1, names=('foo',))
            Univariate Quotient Polynomial Ring in foo over Rational Field with modulus x^2 - 1

        TESTS:

        Quotienting by the zero ideal returns ``self`` (:trac:`5978`)::

            sage: R = QQ['x']
            sage: R.quotient_by_principal_ideal(R.zero_ideal()) is R
            True
            sage: R.quotient_by_principal_ideal(0) is R
            True
        """
        from sage.rings.ideal import Ideal
        I = Ideal(f)
        if I.is_zero():
            return self
        f = I.gen()
        from sage.rings.polynomial.polynomial_quotient_ring import PolynomialQuotientRing
        return PolynomialQuotientRing(self, f, names)

    def weyl_algebra(self):
        """
        Return the Weyl algebra generated from ``self``.

        EXAMPLES::

            sage: R = QQ['x']
            sage: W = R.weyl_algebra(); W
            Differential Weyl algebra of polynomials in x over Rational Field
            sage: W.polynomial_ring() == R
            True
        """
        from sage.algebras.weyl_algebra import DifferentialWeylAlgebra
        return DifferentialWeylAlgebra(self)

    def _roots_univariate_polynomial(self, p, ring=None, multiplicities=True, algorithm=None, degree_bound=None):
        """
        Return the list of roots of ``p``.

        INPUT:

        - ``p`` -- the polynomial whose roots are computed
        - ``ring`` -- the ring to find roots (default is the base ring of ``p``)
        - ``multiplicities`` -- bool (default: True): if ``True``, return a list of pairs ``(root, multiplicity)``; if ``False`` return a list of roots
        - ``algorithm`` -- ignored (TODO: remove)
        - ``degree_bound``-- if not ``None``, return only roots of degree at most ``degree_bound``

        EXAMPLES::

            sage: R.<x> = QQ[]
            sage: S.<y> = R[]
            sage: p = y^3 + (-x^2 - 3)*y^2 + (2*x^3 - x^2 + 3)*y - x^4 + 2*x^2 - 1
            sage: p.roots()
            [(x^2 - 2*x + 1, 1), (x + 1, 2)]
            sage: p.roots(multiplicities=False)
            [x^2 - 2*x + 1, x + 1]
            sage: p.roots(degree_bound=1)
            [(x + 1, 2)]

        TESTS:

        Check that :trac:`23639` is fixed::

            sage: foo = QQ['x']['y'].one()
            sage: foo.roots(QQ)
            []
        """
        if ring is not None and ring is not self:
            p = p.change_ring(ring)
            if degree_bound is None:
                return p.roots(multiplicities = multiplicities, algorithm = algorithm)
            return p.roots(multiplicities = multiplicities, algorithm = algorithm, degree_bound = degree_bound)

        roots = p._roots_from_factorization(p.factor(), multiplicities)
        if degree_bound is not None:
            if multiplicities:
                roots = [(r,m) for (r,m) in roots if r.degree() <= degree_bound]
            else:
                roots = [r for r in roots if r.degree() <= degree_bound]
        return roots


class PolynomialRing_integral_domain(PolynomialRing_commutative, PolynomialRing_singular_repr,
                                     ring.IntegralDomain):
    def __init__(self, base_ring, name="x", sparse=False, implementation=None,
            element_class=None, category=None):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_integral_domain as PRing
            sage: R = PRing(ZZ, 'x'); R
            Univariate Polynomial Ring in x over Integer Ring
            sage: type(R.gen())
            <type 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>

            sage: R = PRing(ZZ, 'x', implementation='NTL'); R
            Univariate Polynomial Ring in x over Integer Ring (using NTL)
            sage: type(R.gen())
            <type 'sage.rings.polynomial.polynomial_integer_dense_ntl.Polynomial_integer_dense_ntl'>
        """
        self._implementation_repr = ''
        if element_class is None:
            implementation = self._implementation_names(implementation, base_ring, sparse)[0]
            if base_ring is ZZ:
                if implementation == 'NTL':
                    from sage.rings.polynomial.polynomial_integer_dense_ntl \
                        import Polynomial_integer_dense_ntl as element_class
                    self._implementation_repr = ' (using NTL)'
                elif implementation == 'FLINT':
                    element_class = Polynomial_integer_dense_flint
        PolynomialRing_commutative.__init__(self, base_ring, name=name,
                sparse=sparse, element_class=element_class, category=category)
        self._has_singular = can_convert_to_singular(self)

    @cached_method(key=lambda self, d, q, sign, lead: (d, q, sign, tuple([x if isinstance(x, (tuple, list)) else (x, 0) for x in lead]) if isinstance(lead, (tuple, list)) else ((lead, 0))))
    def weil_polynomials(self, d, q, sign=1, lead=1):
        r"""
        Return all integer polynomials whose complex roots all have a specified absolute value.

        Such polynomials `f` satisfy a functional equation

        .. MATH::

            T^d f(q/T) = s q^{d/2} f(T)

        where `d` is the degree of `f`, `s` is a sign and `q^{1/2}` is the absolute value
        of the roots of `f`.

        INPUT:

        - ``d`` -- integer, the degree of the polynomials

        - ``q`` -- integer, the square of the complex absolute value of the roots

        - ``sign`` -- integer (default `1`), the sign `s` of the functional equation

        - ``lead`` -- integer, list of integers or list of pairs of integers (default `1`),
            constraints on the leading few coefficients of the generated polynomials.
            If pairs `(a, b)` of integers are given, they are treated as a constraint
            of the form `\equiv a \pmod{b}`; the moduli must be in decreasing order by
            divisibility, and the modulus of the leading coefficient must be 0.

        .. SEEALSO::

            More documentation and additional options are available using the iterator
            :class:`sage.rings.polynomial.weil.weil_polynomials.WeilPolynomials`
            directly. In addition, polynomials have a method `is_weil_polynomial` to
            test whether or not the given polynomial is a Weil polynomial.

        EXAMPLES::

            sage: R.<T> = ZZ[]
            sage: L = R.weil_polynomials(4, 2)
            sage: len(L)
            35
            sage: L[9]
            T^4 + T^3 + 2*T^2 + 2*T + 4
            sage: all(p.is_weil_polynomial() for p in L)
            True

        Setting multiple leading coefficients:

            sage: R.<T> = QQ[]
            sage: l = R.weil_polynomials(4,2,lead=((1,0),(2,4),(1,2)))
            sage: l
            [T^4 + 2*T^3 + 5*T^2 + 4*T + 4,
            T^4 + 2*T^3 + 3*T^2 + 4*T + 4,
            T^4 - 2*T^3 + 5*T^2 - 4*T + 4,
            T^4 - 2*T^3 + 3*T^2 - 4*T + 4]

        We do not require Weil polynomials to be monic. This example generates Weil
        polynomials associated to K3 surfaces over `GF(2)` of Picard number at least 12::

            sage: R.<T> = QQ[]
            sage: l = R.weil_polynomials(10,1,lead=2)
            sage: len(l)
            4865
            sage: l[len(l)//2]
            2*T^10 + T^8 + T^6 + T^4 + T^2 + 2

        TESTS:

        We check that products of Weil polynomials are also listed as Weil polynomials::

            sage: all((f * g) in R.weil_polynomials(6, q) for q in [3,4] for f in R.weil_polynomials(2, q) for g in R.weil_polynomials(4, q))
            True

        We check that irreducible Weil polynomials of degree 6 are CM::

            sage: simples = [f for f in R.weil_polynomials(6, 3) if f.is_irreducible()]
            sage: len(simples)
            348
            sage: reals = [R([f[3+i] + sum((-3)^j * (i+2*j)/(i+j) * binomial(i+j,j) * f[3+i+2*j] for j in range(1,(3+i)//2+1)) for i in range(4)]) for f in simples]

        Check that every polynomial in this list has 3 real roots between `-2 \sqrt{3}` and `2 \sqrt{3}`::

            sage: roots = [f.roots(RR, multiplicities=False) for f in reals]
            sage: all(len(L) == 3 and all(x^2 <= 12 for x in L) for L in roots)
            True

        Finally, check that the original polynomials are reconstructed as CM polynomials::

            sage: all(f == T^3*r(T + 3/T) for (f, r) in zip(simples, reals))
            True

        A simple check (not sufficient)::

            sage: all(f.number_of_real_roots() == 0 for f in simples)
            True
        """
        R = self.base_ring()
        if not (R is ZZ or R is QQ):
            raise ValueError("Weil polynomials have integer coefficients")
        from sage.rings.polynomial.weil.weil_polynomials import WeilPolynomials
        return list(WeilPolynomials(d, q, sign, lead, polring=self))

    @staticmethod
    def _implementation_names_impl(implementation, base_ring, sparse):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_integral_domain
            sage: PolynomialRing_integral_domain._implementation_names_impl(None, ZZ, False)
            ['FLINT', None]
            sage: PolynomialRing_integral_domain._implementation_names_impl(None, ZZ, True)
            [None, 'generic']
            sage: PolynomialRing_integral_domain._implementation_names_impl(None, QQ, False)
            [None, 'generic']
            sage: PolynomialRing_integral_domain._implementation_names_impl(None, QQ, True)
            [None, 'generic']
        """
        if base_ring is ZZ and not sparse:
            defaults = ["FLINT", None]
            if implementation in defaults:
                return defaults
            elif implementation in ["NTL", "generic"]:
                return [implementation]
        elif implementation is None or implementation == "generic":
            return [None, "generic"]
        return NotImplemented

    def _repr_(self):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_integral_domain as PRing
            sage: R = PRing(ZZ, 'x', implementation='NTL'); R
            Univariate Polynomial Ring in x over Integer Ring (using NTL)
        """
        s = PolynomialRing_commutative._repr_(self)
        return s + self._implementation_repr


class PolynomialRing_field(PolynomialRing_integral_domain,
                           ring.PrincipalIdealDomain):
    def __init__(self, base_ring, name="x", sparse=False, element_class=None, category=None):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_field as PRing
            sage: R = PRing(QQ, 'x'); R
            Univariate Polynomial Ring in x over Rational Field
            sage: type(R.gen())
            <type 'sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint'>
            sage: R = PRing(QQ, 'x', sparse=True); R
            Sparse Univariate Polynomial Ring in x over Rational Field
            sage: type(R.gen())
            <class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_field_with_category.element_class'>
            sage: R = PRing(CC, 'x'); R
            Univariate Polynomial Ring in x over Complex Field with 53 bits of precision
            sage: type(R.gen())
            <class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_field_with_category.element_class'>

        Demonstrate that :trac:`8762` is fixed::

            sage: R.<x> = PolynomialRing(GF(next_prime(10^20)), sparse=True)
            sage: x^(10^20) # this should be fast
            x^100000000000000000000
        """
        import sage.rings.complex_arb

        if not element_class:
            if sparse:
                element_class = polynomial_element_generic.Polynomial_generic_sparse_field
            elif isinstance(base_ring, rational_field.RationalField):
                from sage.rings.polynomial.polynomial_rational_flint import Polynomial_rational_flint
                element_class = Polynomial_rational_flint
            elif is_NumberField(base_ring):
                if base_ring.is_absolute():
                    from sage.rings.polynomial.polynomial_number_field import Polynomial_absolute_number_field_dense
                    element_class = Polynomial_absolute_number_field_dense
                else:
                    from sage.rings.polynomial.polynomial_number_field import Polynomial_relative_number_field_dense
                    element_class = Polynomial_relative_number_field_dense
            elif is_RealField(base_ring):
                element_class = PolynomialRealDense
            elif isinstance(base_ring, sage.rings.complex_arb.ComplexBallField):
                from sage.rings.polynomial.polynomial_complex_arb import Polynomial_complex_arb
                element_class = Polynomial_complex_arb
            else:
                element_class = polynomial_element_generic.Polynomial_generic_dense_field

        PolynomialRing_integral_domain.__init__(self, base_ring, name=name, sparse=sparse, element_class=element_class, category=category)

    def _ideal_class_(self, n=0):
        """
        Returns the class representing ideals in univariate polynomial rings over fields.

        EXAMPLES::

            sage: R.<t> = GF(5)[]
            sage: R._ideal_class_()
            <class 'sage.rings.polynomial.ideal.Ideal_1poly_field'>
        """
        from sage.rings.polynomial.ideal import Ideal_1poly_field
        return Ideal_1poly_field

    def divided_difference(self, points, full_table=False):
        r"""
        Return the Newton divided-difference coefficients of the
        Lagrange interpolation polynomial through ``points``.

        INPUT:

        - ``points`` -- a list of pairs `(x_0, y_0), (x_1, y_1),
          \dots, (x_n, y_n)` of elements of the base ring of ``self``,
          where `x_i - x_j` is invertible for `i \neq j`.  This method
          converts the `x_i` and `y_i` into the base ring of `self`.

        - ``full_table`` -- boolean (default: ``False``): If ``True``,
          return the full divided-difference table.  If ``False``,
          only return entries along the main diagonal; these are the
          Newton divided-difference coefficients `F_{i,i}`.

        OUTPUT:

        The Newton divided-difference coefficients of the `n`-th
        Lagrange interpolation polynomial `P_n(x)` that passes through
        the points in ``points`` (see :meth:`lagrange_polynomial`).
        These are the coefficients `F_{0,0}, F_{1,1}, \dots, `F_{n,n}`
        in the base ring of ``self`` such that

        .. MATH::

            P_n(x) = \sum_{i=0}^n F_{i,i} \prod_{j=0}^{i-1} (x - x_j)

        EXAMPLES:

        Only return the divided-difference coefficients `F_{i,i}`.
        This example is taken from Example 1, page 121 of [BF2005]_::

            sage: points = [(1.0, 0.7651977), (1.3, 0.6200860), (1.6, 0.4554022), (1.9, 0.2818186), (2.2, 0.1103623)]
            sage: R = PolynomialRing(RR, "x")
            sage: R.divided_difference(points)
            [0.765197700000000,
            -0.483705666666666,
            -0.108733888888889,
            0.0658783950617283,
            0.00182510288066044]

        Now return the full divided-difference table::

            sage: points = [(1.0, 0.7651977), (1.3, 0.6200860), (1.6, 0.4554022), (1.9, 0.2818186), (2.2, 0.1103623)]
            sage: R = PolynomialRing(RR, "x")
            sage: R.divided_difference(points, full_table=True)
            [[0.765197700000000],
            [0.620086000000000, -0.483705666666666],
            [0.455402200000000, -0.548946000000000, -0.108733888888889],
            [0.281818600000000,
            -0.578612000000000,
            -0.0494433333333339,
            0.0658783950617283],
            [0.110362300000000,
            -0.571520999999999,
            0.0118183333333349,
            0.0680685185185209,
            0.00182510288066044]]

        The following example is taken from Example 4.12, page 225 of
        [MF1999]_::

            sage: points = [(1, -3), (2, 0), (3, 15), (4, 48), (5, 105), (6, 192)]
            sage: R = PolynomialRing(QQ, "x")
            sage: R.divided_difference(points)
            [-3, 3, 6, 1, 0, 0]
            sage: R.divided_difference(points, full_table=True)
            [[-3],
            [0, 3],
            [15, 15, 6],
            [48, 33, 9, 1],
            [105, 57, 12, 1, 0],
            [192, 87, 15, 1, 0, 0]]
        """
        to_base_ring = self.base_ring()
        points = [tuple(to_base_ring(c) for c in p) for p in points]
        n = len(points)
        F = [[points[i][1]] for i in range(n)]
        for i in range(1, n):
            for j in range(1, i+1):
                numer = F[i][j-1] - F[i-1][j-1]
                denom = points[i][0] - points[i-j][0]
                F[i].append(numer / denom)
        if full_table:
            return F
        else:
            return [F[i][i] for i in range(n)]

    def lagrange_polynomial(self, points, algorithm="divided_difference", previous_row=None):
        r"""
        Return the Lagrange interpolation polynomial through the
        given points.

        INPUT:

        - ``points`` -- a list of pairs `(x_0, y_0), (x_1, y_1),
          \dots, (x_n, y_n)` of elements of the base ring of ``self``,
          where `x_i - x_j` is invertible for `i \neq j`.  This method
          converts the `x_i` and `y_i` into the base ring of `self`.

        - ``algorithm`` -- (default: ``'divided_difference'``): one of
          the following:

          - ``'divided_difference'``: use the method of divided
            differences.

          - ``algorithm='neville'``: adapt Neville's method as
            described on page 144 of [BF2005]_ to recursively generate
            the Lagrange interpolation polynomial.  Neville's method
            generates a table of approximating polynomials, where the
            last row of that table contains the `n`-th Lagrange
            interpolation polynomial.  The adaptation implemented by
            this method is to only generate the last row of this
            table, instead of the full table itself.  Generating the
            full table can be memory inefficient.

        - ``previous_row`` -- (default: ``None``): This option is only
          relevant if used with ``algorithm='neville'``.  If provided,
          this should be the last row of the table resulting from a
          previous use of Neville's method.  If such a row is passed,
          then ``points`` should consist of both previous and new
          interpolating points.  Neville's method will then use that
          last row and the interpolating points to generate a new row
          containing an interpolation polynomial for the new points.

        OUTPUT:

        The Lagrange interpolation polynomial through the points
        `(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)`.  This is the
        unique polynomial `P_n` of degree at most `n` in ``self``
        satisfying `P_n(x_i) = y_i` for `0 \le i \le n`.

        EXAMPLES:

        By default, we use the method of divided differences::

            sage: R = PolynomialRing(QQ, 'x')
            sage: f = R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)]); f
            -23/84*x^3 - 11/84*x^2 + 13/7*x + 1
            sage: f(0)
            1
            sage: f(2)
            2
            sage: f(3)
            -2
            sage: f(-4)
            9
            sage: R = PolynomialRing(GF(2**3,'a'), 'x')
            sage: a = R.base_ring().gen()
            sage: f = R.lagrange_polynomial([(a^2+a,a),(a,1),(a^2,a^2+a+1)]); f
            a^2*x^2 + a^2*x + a^2
            sage: f(a^2+a)
            a
            sage: f(a)
            1
            sage: f(a^2)
            a^2 + a + 1

        Now use a memory efficient version of Neville's method::

            sage: R = PolynomialRing(QQ, 'x')
            sage: R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)], algorithm="neville")
            [9,
            -11/7*x + 19/7,
            -17/42*x^2 - 83/42*x + 53/7,
            -23/84*x^3 - 11/84*x^2 + 13/7*x + 1]
            sage: R = PolynomialRing(GF(2**3,'a'), 'x')
            sage: a = R.base_ring().gen()
            sage: R.lagrange_polynomial([(a^2+a,a),(a,1),(a^2,a^2+a+1)], algorithm="neville")
            [a^2 + a + 1, x + a + 1, a^2*x^2 + a^2*x + a^2]

        Repeated use of Neville's method to get better Lagrange
        interpolation polynomials::

            sage: R = PolynomialRing(QQ, 'x')
            sage: p = R.lagrange_polynomial([(0,1),(2,2)], algorithm="neville")
            sage: R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)], algorithm="neville", previous_row=p)[-1]
            -23/84*x^3 - 11/84*x^2 + 13/7*x + 1
            sage: R = PolynomialRing(GF(2**3,'a'), 'x')
            sage: a = R.base_ring().gen()
            sage: p = R.lagrange_polynomial([(a^2+a,a),(a,1)], algorithm="neville")
            sage: R.lagrange_polynomial([(a^2+a,a),(a,1),(a^2,a^2+a+1)], algorithm="neville", previous_row=p)[-1]
            a^2*x^2 + a^2*x + a^2

        TESTS:

        The value for ``algorithm`` must be either
        ``'divided_difference'`` (default), or ``'neville'``::

            sage: R = PolynomialRing(QQ, "x")
            sage: R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)], algorithm="abc")
            Traceback (most recent call last):
            ...
            ValueError: algorithm must be one of 'divided_difference' or 'neville'
            sage: R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)], algorithm="divided difference")
            Traceback (most recent call last):
            ...
            ValueError: algorithm must be one of 'divided_difference' or 'neville'
            sage: R.lagrange_polynomial([(0,1),(2,2),(3,-2),(-4,9)], algorithm="")
            Traceback (most recent call last):
            ...
            ValueError: algorithm must be one of 'divided_difference' or 'neville'

        Make sure that :trac:`10304` is fixed.  The return value
        should always be an element of ``self`` in the case of
        ``divided_difference``, or a list of elements of ``self`` in
        the case of ``neville``::

            sage: R = PolynomialRing(QQ, "x")
            sage: R.lagrange_polynomial([]).parent() == R
            True
            sage: R.lagrange_polynomial([(2, 3)]).parent() == R
            True
            sage: row = R.lagrange_polynomial([], algorithm='neville')
            sage: all(poly.parent() == R for poly in row)
            True
            sage: row = R.lagrange_polynomial([(2, 3)], algorithm='neville')
            sage: all(poly.parent() == R for poly in row)
            True

        Check that base fields of positive characteristic are treated
        correctly (see :trac:`9787`)::

            sage: R.<x> = GF(101)[]
            sage: R.lagrange_polynomial([[1, 0], [2, 0]])
            0
            sage: R.lagrange_polynomial([[1, 0], [2, 0], [3, 0]])
            0
        """
        # Perhaps we should be slightly stricter on the input and use
        # self.base_ring().coerce here and in the divided_difference()
        # method above.  However, this breaks an example in
        # sage.tests.french_book.nonlinear_doctest where the base ring
        # is CC, but the function values lie in the symbolic ring.
        to_base_ring = self.base_ring()
        points = [[to_base_ring(u) for u in x] for x in points]
        var = self.gen()

        # use the method of divided-difference
        if algorithm == "divided_difference":
            # Evaluate in nested form, similar to Horner's method. This is
            # more efficient than evaluation using the definition of
            # Lagrange interpolation polynomial by means of divided
            # difference.
            n = len(points)
            if n == 0:
                return self.zero()

            F = self.divided_difference(points)
            P = self.coerce(F[n-1])
            for i in range(n-2, -1, -1):
                P *= (var - points[i][0])
                P += F[i]
            return P

            # Evaluate using the definition of Lagrange interpolation
            # polynomial by means of divided difference. This is slow
            # compared to that above, which is in nested form.
#             P = 0
#             for i in range(n):
#                 prod = 1
#                 for j in range(i):
#                     prod *= (var - points[j][0])
#                 P += (F[i] * prod)
#             return P

        # using Neville's method for recursively generating the
        # Lagrange interpolation polynomial
        elif algorithm == "neville":
            if previous_row is None:
                previous_row = []
            N = len(points)
            M = len(previous_row)
            # During the computation, P keeps track of the previous row,
            # and Q keeps track of the current row
            P = previous_row + [None] * (N - M) # use results of previous computation if available
            Q = [None] * N
            for i in range(M, N):
                Q[0] = self.coerce(points[i][1])  # start populating the current row
                for j in range(1, 1 + i):
                    numer = (var - points[i - j][0]) * Q[j - 1] - (var - points[i][0]) * P[j - 1]
                    denom = points[i][0] - points[i - j][0]
                    Q[j] = numer / denom
                P, Q = Q, P # the current row is complete, reuse the old P to hold the next row
            return P # return the last row in the Neville table

#        # use the definition of Lagrange interpolation polynomial
#        elif algorithm == "definition":
#            def Pj(j):
#                denom = 1
#                divis = 1
#                for i in range(len(points)):
#                    if i!=j:
#                        denom *= (var          - points[i][0])
#                        divis *= (points[j][0] - points[i][0])
#            return denom/divis
#
#            P = 0
#            for j in range(len(points)):
#                P += Pj(j)*points[j][1]
#            return P

        else:
            raise ValueError("algorithm must be one of 'divided_difference' or 'neville'")

    @cached_method
    def fraction_field(self):
        """
        Returns the fraction field of self.

        EXAMPLES::

            sage: R.<t> = GF(5)[]
            sage: R.fraction_field()
            Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 5

        TESTS:

        Check that :trac:`25449` has been resolved::

            sage: k = GF(25453)
            sage: F.<x> = FunctionField(k)
            sage: R.<t> = k[]
            sage: t(x)
            x

            sage: k = GF(55667)
            sage: F.<x> = FunctionField(k)
            sage: R.<t> = k[]
            sage: t(x)
            x

        """
        R = self.base_ring()
        p = R.characteristic()
        if p != 0 and R.is_prime_field():
            from sage.rings.fraction_field_FpT import FpT
            if 2 < p and p < FpT.INTEGER_LIMIT:
                return FpT(self)
        from sage.rings.fraction_field import FractionField_1poly_field
        return FractionField_1poly_field(self)


class PolynomialRing_dense_finite_field(PolynomialRing_field):
    """
    Univariate polynomial ring over a finite field.

    EXAMPLES::

        sage: R = PolynomialRing(GF(27, 'a'), 'x')
        sage: type(R)
        <class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_finite_field_with_category'>
    """
    def __init__(self, base_ring, name="x", element_class=None, implementation=None):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_dense_finite_field
            sage: R = PolynomialRing_dense_finite_field(GF(5), implementation='generic')
            sage: type(R(0))
            <class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_finite_field_with_category.element_class'>

            sage: S = PolynomialRing_dense_finite_field(GF(25, 'a'), implementation='NTL')
            sage: type(S(0))
            <type 'sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX'>

            sage: S = PolynomialRing_dense_finite_field(GF(64), implementation='superfast')
            Traceback (most recent call last):
            ...
            ValueError: unknown implementation 'superfast' for dense polynomial rings over Finite Field in z6 of size 2^6
        """
        implementation = self._implementation_names(implementation, base_ring)[0]
        if implementation == "NTL":
            from sage.libs.ntl.ntl_ZZ_pEContext import ntl_ZZ_pEContext
            from sage.libs.ntl.ntl_ZZ_pX import ntl_ZZ_pX
            from sage.rings.polynomial.polynomial_zz_pex import Polynomial_ZZ_pEX

            p = base_ring.characteristic()
            self._modulus = ntl_ZZ_pEContext(ntl_ZZ_pX(list(base_ring.modulus()), p))
            element_class = Polynomial_ZZ_pEX
        PolynomialRing_field.__init__(self, base_ring, sparse=False, name=name,
                                      element_class=element_class)

    @staticmethod
    def _implementation_names_impl(implementation, base_ring, sparse):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_dense_finite_field
            sage: PolynomialRing_dense_finite_field._implementation_names_impl("NTL", GF(4), False)
            ['NTL', None]
            sage: PolynomialRing_dense_finite_field._implementation_names_impl(None, GF(4), False)
            ['NTL', None]
            sage: PolynomialRing_dense_finite_field._implementation_names_impl("generic", GF(4), False)
            ['generic']
            sage: PolynomialRing_dense_finite_field._implementation_names_impl("FLINT", GF(4), False)
            NotImplemented
            sage: PolynomialRing_dense_finite_field._implementation_names_impl(None, GF(4), True)
            NotImplemented
        """
        if sparse:
            return NotImplemented
        defaults = ["NTL", None]
        if implementation in defaults:
            return defaults
        elif implementation == "generic":
            return [implementation]
        return NotImplemented

    def irreducible_element(self, n, algorithm=None):
        """
        Construct a monic irreducible polynomial of degree `n`.

        INPUT:

        - ``n`` -- integer: degree of the polynomial to construct

        - ``algorithm`` -- string: algorithm to use, or ``None``

          - ``'random'``: try random polynomials until an irreducible
            one is found.

          - ``'first_lexicographic'``: try polynomials in
            lexicographic order until an irreducible one is found.

        OUTPUT:

        A monic irreducible polynomial of degree `n` in ``self``.

        EXAMPLES::

            sage: GF(5^3, 'a')['x'].irreducible_element(2)
            x^2 + 3*a^2 + a + 2
            sage: GF(19)['x'].irreducible_element(21, algorithm="first_lexicographic")
            x^21 + x + 5
            sage: GF(5**2, 'a')['x'].irreducible_element(17, algorithm="first_lexicographic")
            x^17 + a*x + 4*a + 3

        AUTHORS:

        - Peter Bruin (June 2013)
        - Jean-Pierre Flori (May 2014)
        """
        if n < 1:
            raise ValueError("degree must be at least 1")

        if algorithm is None:
            algorithm = "random"

        if algorithm == "random":
            while True:
                f = self.gen()**n + self.random_element(degree=(0, n - 1))
                if f.is_irreducible():
                    return f
        elif algorithm == "first_lexicographic":
            for g in self.polynomials(max_degree=n-1):
                f = self.gen()**n + g
                if f.is_irreducible():
                    return f
        else:
            raise ValueError("no such algorithm for finding an irreducible polynomial: %s" % algorithm)

    def _roth_ruckenstein(self, p, degree_bound, precision):
        r"""
        Return all polynomials which are a solution to the, possibly modular,
        root-finding problem.

        This is the core of Roth-Ruckenstein's algorithm where all conversions,
        checks and parent-extraction have been done.

        INPUT:

        - ``p`` -- a nonzero polynomial over ``F[x][y]``. The polynomial ``p``
          should be first truncated to ``precision``

        - ``degree_bound`` -- a bound on the degree of the roots of ``p`` that
          the algorithm computes

        - ``precision`` -- if given, roots are computed modulo `x^d` where `d` is
          ``precision`` (see below)

        OUTPUT:

        The list of roots of ``p`` of degree at most ``degree_bound``:

        - If `precision = None` actual roots are computed, i.e. all `f \in F[x]`
          such that `p(f) = 0`.

        - If ``precision = k`` for some integer ``k``, then all `f \in \F[x]` such
          that `Q(f) \equiv 0 \mod x^k` are computed. This set is infinite, thus it
          represented as a list of pairs in `F[x] \times \ZZ_+`, where
          `(f, d)` denotes that `Q(f + x^d h) \equiv 0 \mod x^k` for any `h \in
          F[[x]]`.

        EXAMPLES::

            sage: F = GF(17)
            sage: Px.<x> = F[]
            sage: Pxy.<y> = Px[]
            sage: p = (y - (x**2 + x + 1)) * (y**2 - x + 1) * (y - (x**3 + 4*x + 16))
            sage: Px._roth_ruckenstein(p, 3, None)
            [x^3 + 4*x + 16, x^2 + x + 1]
            sage: Px._roth_ruckenstein(p, 2, None)
            [x^2 + x + 1]
            sage: Px._roth_ruckenstein(p, 1, 2)
            [(4*x + 16, 2), (2*x + 13, 2), (15*x + 4, 2), (x + 1, 2)]
        """
        def roth_rec(p, lam, k, g):
            r"""
            Recursive core method for Roth-Ruckenstein algorithm.

            INPUT:

            - ``p`` -- the current value of the polynomial
            - ``lam`` -- is the power of x whose coefficient is being computed
            - ``k`` -- the remaining precision to handle (if ``precision`` is given)
            - ``g`` -- the root being computed
            """
            if precision and k <= 0:
                solutions.append((g, lam))
                return
            val = min(c.valuation() for c in p)
            if precision:
                k = k - val
            T = p.map_coefficients(lambda c:c.shift(-val))
            Ty = T.map_coefficients(lambda c:c[0]).change_ring(F)
            if Ty.is_zero() or (precision and k <= 0):
                if precision:
                    solutions.append((g, lam))
                else:
                    solutions.append(g)
                return
            roots = Ty.roots(multiplicities=False)
            for gamma in roots:
                g_new = g + gamma*x**lam
                if lam < degree_bound:
                    Tg = T(x*y + gamma)
                    roth_rec(Tg , lam+1, k, g_new)
                else:
                    if precision:
                        solutions.append((g_new, lam+1))
                    elif p(gamma).is_zero():
                        solutions.append(g_new)
            return

        x = self.gen()
        y = p.parent().gen()
        F = self.base_ring()
        solutions = []
        g = self.zero()

        roth_rec(p, 0, precision, g)
        return solutions

    def _alekhnovich(self, p, degree_bound, precision=None, dc_threshold=None):
        r"""
        Use Alekhnovich's Divide & Conquer variant of Roth-Ruckenstein's
        rootfinding algorithm to find roots modulo-up-to-some-precision of a `Q \in
        F[x][y]` where `F` is a finite field. Supports a mixed strategy with
        Roth-Ruckenstein applied at lowest precision.

        INPUT:

        - ``p`` -- a nonzero polynomial over ``F[x][y]``. The polynomial ``p``
          should be first truncated to ``precision``

        - ``degree_bound`` -- a bound on the degree of the roots of ``p`` that
          the algorithm computes

        - ``precision`` -- if given, roots are computed modulo `x^d` where `d` is
          ``precision`` (see below)

        - ``dc_threshold`` -- if given, the algorithm calls :meth:`_roth_ruckenetein`
          to compute roots of degree at most ``dc_threshold``

        OUTPUT:

        The list of roots of ``p`` of degree at most ``degree_bound``:

        - If `precision = None` actual roots are computed, i.e. all `f \in F[x]`
          such that `p(f) = 0`.

        - If ``precision = k`` for some integer ``k``, then all `f \in \F[x]` such
          that `Q(f) \equiv 0 \mod x^k` are computed. This set is infinite, thus it
          represented as a list of pairs in `F[x] \times \ZZ_+`, where
          `(f, d)` denotes that `Q(f + x^d h) \equiv 0 \mod x^k` for any `h \in
          F[[x]]`.

        .. NOTE::

            Non-exhaustive testing tends to indicate that ``dc_threhold = None`` is,
            surprisingly, the best strategy. (See the example section.)

        EXAMPLES::

            sage: R.<x> = GF(17)[]
            sage: S.<y> = R[]
            sage: p = (y - 2*x^2 - 3*x - 14) * (y - 3*x + 2) * (y - 1)
            sage: R._alekhnovich(p, 2)
            [3*x + 15, 2*x^2 + 3*x + 14, 1]
            sage: R._alekhnovich(p, 1)
            [3*x + 15, 1]
            sage: R._alekhnovich(p, 1, precision = 2)
            [(3*x + 15, 2), (3*x + 14, 2), (1, 2)]

        Example of benchmark to check that `dc_threshold = None` is better::

            sage: p = prod(y - R.random_element(20) for _ in range(10)) * S.random_element(10,10) # not tested
            sage: %timeit _alekhnovich(R, p, 20, dc_threshold = None) # not tested
            1 loop, best of 3: 418 ms per loop
            sage: %timeit _alekhnovich(R, p, 20, dc_threshold = 1) # not tested
            1 loop, best of 3: 416 ms per loop
            sage: %timeit _alekhnovich(R, p, 20, dc_threshold = 2) # not tested
            1 loop, best of 3: 418 ms per loop
            sage: %timeit _alekhnovich(R, p, 20, dc_threshold = 3) # not tested
            1 loop, best of 3: 454 ms per loop
            sage: %timeit _alekhnovich(R, p, 20, dc_threshold = 4) # not tested
            1 loop, best of 3: 519 ms per loop

        AUTHORS:

        - Johan Rosenkilde (2015) -- Original implementation
        - Bruno Grenet (August 2016) -- Incorporation into SageMath and polishing
        """
        def alekh_rec(p, k, degree_bound, lvl):
            r"""
            Recursive core method for Alekhnovich algorithm."

            INPUT:

            - ``p`` -- the current value of the polynomial
            - ``k`` -- the number of coefficients left to be computed
            - ``degree_bound`` -- the current degree bound
            - ``lvl`` -- the level in the recursion tree
            """
            if k<=0:
                return [ (self.zero(),0) ]
            elif degree_bound < 0:
                # The only possible root of (current) p, if any, is y = 0
                if p(0).is_zero() or p(0).valuation() >= k:
                    return [ (self.zero(),0) ]
                else:
                    return []
            elif k == 1 or degree_bound == 0:
                #Either one coefficient left to be computed, or p has only one coefficient
                py = self([c[0] for c in p.list()])  # py = p(x=0, y)
                if py.is_zero():
                    return [ (self.zero(), 0) ]
                roots = py.roots(multiplicities=False)
                return [ (self(r),1) for r in roots ]
            elif k < dc_threshold:
                # Run Roth-Ruckenstein
                return self._roth_ruckenstein(p, degree_bound=degree_bound, precision=k)
            else:
                p = p.map_coefficients(lambda c:c.truncate(k))
                half_roots = alekh_rec(p, k//2, degree_bound, lvl+1)
                whole_roots = []
                for (hi, di) in half_roots:
                    QhatT = p(hi + y*x**di)
                    if not QhatT:
                        whole_roots.append((hi,di))
                    else:
                        val = min(c.valuation() for c in QhatT)
                        Qhat = QhatT.map_coefficients(lambda c:c.shift(-val))
                        sec_half = alekh_rec(Qhat, k-val, degree_bound - di, lvl+1)
                        whole_roots.extend([ (hi + hij.shift(di), di+dij) for (hij, dij) in sec_half ])
                return whole_roots

        x = self.gen()
        y = p.parent().gen()

        # If precision is not given, find actual roots. To be sure, precision then
        # needs to be more than wdeg{1,degree_bound}(Q) since a root might have degree degree_bound.
        if precision is None:
            k = 1 + max( p[i].degree() + degree_bound*i for i in range(1+p.degree()))
        else:
            k = precision

        mod_roots = alekh_rec(p, k, degree_bound, 0)

        if precision is None:
            roots = []
            for hi,_ in mod_roots:
                if p(hi).is_zero():
                    roots.append(hi)
            return roots
        else:
            return mod_roots

    def _roots_univariate_polynomial(self, p, ring=None, multiplicities=False, algorithm=None, degree_bound=None):
        """
        Return the list of roots of ``p``.

        INPUT:

        - ``p`` -- the polynomial whose roots are computed
        - ``ring`` -- the ring to find roots (default is the base ring of ``p``)
        - ``multiplicities`` -- bool (default: True): currently, roots are only
          computed without their multiplicities.
        - ``algorithm`` -- the algorithm to use: either ``"Alekhnovich"`` (default)
          or ``"Roth-Ruckenstein"``
        - ``degree_bound``-- if not ``None``, return only roots of degree at
          most ``degree_bound``

        EXAMPLES::

            sage: R.<x> = GF(13)[]
            sage: S.<y> = R[]
            sage: p = y^2 + (12*x^2 + x + 11)*y + x^3 + 12*x^2 + 12*x + 1
            sage: p.roots(multiplicities=False)
            [x^2 + 11*x + 1, x + 1]
            sage: p.roots(multiplicities=False, degree_bound=1)
            [x + 1]
            sage: p.roots(multiplicities=False, algorithm="Roth-Ruckenstein")
            [x^2 + 11*x + 1, x + 1]

        TESTS:

        Check that :trac:`23639` is fixed::

            sage: R = GF(3)['x']['y']
            sage: R.one().roots(multiplicities=False)
            []
            sage: R.zero().roots(multiplicities=False)
            Traceback (most recent call last):
            ...
            ArithmeticError: roots of 0 are not defined
        """
        if multiplicities:
            raise NotImplementedError("Use multiplicities=False")

        if degree_bound is None:
            l = p.degree()
            if l < 0:
                raise ArithmeticError("roots of 0 are not defined")
            if l == 0:
                return []
            dl = p[l].degree()
            degree_bound = max((p[i].degree() - dl)//(l - i) for i in range(l) if p[i])

        if algorithm is None:
            algorithm = "Alekhnovich"

        if algorithm == "Roth-Ruckenstein":
            return self._roth_ruckenstein(p, degree_bound, None)

        elif algorithm == "Alekhnovich":
            return self._alekhnovich(p, degree_bound)

        else:
            raise ValueError("unknown algorithm '{}'".format(algorithm))


class PolynomialRing_cdvr(PolynomialRing_integral_domain):
    r"""
    A class for polynomial ring over complete discrete valuation rings
    """
    def __init__(self, base_ring, name=None, sparse=False, element_class=None, category=None):
        r"""
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_cdvr

            sage: S.<x> = ZZ[]
            sage: isinstance(S, PolynomialRing_cdvr)
            False

            sage: S.<x> = Zp(5)[]
            sage: isinstance(S, PolynomialRing_cdvr)
            True
        """
        if element_class is None:
            if sparse:
                from sage.rings.polynomial.polynomial_element_generic import Polynomial_generic_sparse_cdvr
                element_class = Polynomial_generic_sparse_cdvr
            else:
                from sage.rings.polynomial.polynomial_element_generic import Polynomial_generic_dense_cdvr
                element_class = Polynomial_generic_dense_cdvr
        PolynomialRing_integral_domain.__init__(self, base_ring, name, sparse, element_class=element_class, category=category)


class PolynomialRing_cdvf(PolynomialRing_cdvr, PolynomialRing_field):
    """
    A class for polynomial ring over complete discrete valuation fields
    """
    def __init__(self, base_ring, name=None, sparse=False, element_class=None, category=None):
        r"""
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_cdvf

            sage: S.<x> = QQ[]
            sage: isinstance(S, PolynomialRing_cdvf)
            False

            sage: S.<x> = Qp(5)[]
            sage: isinstance(S, PolynomialRing_cdvf)
            True
        """
        if element_class is None:
            if sparse:
                from sage.rings.polynomial.polynomial_element_generic import Polynomial_generic_sparse_cdvf
                element_class = Polynomial_generic_sparse_cdvf
            else:
                from sage.rings.polynomial.polynomial_element_generic import Polynomial_generic_dense_cdvf
                element_class = Polynomial_generic_dense_cdvf
        PolynomialRing_field.__init__(self, base_ring, name, sparse, element_class=element_class, category=category)


class PolynomialRing_dense_padic_ring_generic(PolynomialRing_cdvr):
    r"""
    A class for dense polynomial ring over padic rings
    """
    def __init__(self, base_ring, name=None, element_class=None, category=None):
        PolynomialRing_cdvr.__init__(self, base_ring, sparse=False, name=name, element_class=element_class, category=category)

    @staticmethod
    def _implementation_names_impl(implementation, base_ring, sparse):
        """
        Only support ``implementation=None`` and ``sparse=False``.

        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_dense_padic_ring_generic
            sage: PolynomialRing_dense_padic_ring_generic._implementation_names_impl(None, Zp(2), False)
            [None]
            sage: PolynomialRing_dense_padic_ring_generic._implementation_names_impl(None, Zp(2), True)
            NotImplemented
            sage: PolynomialRing_dense_padic_ring_generic._implementation_names_impl("generic", Zp(2), False)
            NotImplemented
        """
        if implementation is None and not sparse:
            return [None]  # Not a "generic" implementation
        return NotImplemented


class PolynomialRing_dense_padic_field_generic(PolynomialRing_cdvf):
    r"""
    A class for dense polynomial ring over padic fields
    """
    def __init__(self, base_ring, name=None, element_class=None, category=None):
        PolynomialRing_cdvf.__init__(self, base_ring, sparse=False, name=name, element_class=element_class, category=category)

    @staticmethod
    def _implementation_names_impl(implementation, base_ring, sparse):
        """
        Only support ``implementation=None`` and ``sparse=False``.

        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_dense_padic_field_generic
            sage: PolynomialRing_dense_padic_field_generic._implementation_names_impl(None, Qp(2), False)
            [None]
            sage: PolynomialRing_dense_padic_field_generic._implementation_names_impl(None, Qp(2), True)
            NotImplemented
            sage: PolynomialRing_dense_padic_field_generic._implementation_names_impl("generic", Qp(2), False)
            NotImplemented
        """
        if implementation is None and not sparse:
            return [None]  # Not a "generic" implementation
        return NotImplemented


class PolynomialRing_dense_padic_ring_capped_relative(PolynomialRing_dense_padic_ring_generic):
    def __init__(self, base_ring, name=None, element_class=None, category=None):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_dense_padic_ring_capped_relative as PRing
            sage: R = PRing(Zp(13), name='t'); R
            Univariate Polynomial Ring in t over 13-adic Ring with capped relative precision 20
            sage: type(R.gen())
            <class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_padic_ring_capped_relative_with_category.element_class'>
        """
        if element_class is None:
            from sage.rings.polynomial.padics.\
                    polynomial_padic_capped_relative_dense import \
                    Polynomial_padic_capped_relative_dense
            element_class = Polynomial_padic_capped_relative_dense
        PolynomialRing_dense_padic_ring_generic.__init__(self, base_ring,
                name=name, element_class=element_class, category=category)


class PolynomialRing_dense_padic_ring_capped_absolute(PolynomialRing_dense_padic_ring_generic):
    def __init__(self, base_ring, name=None, element_class=None, category=None):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_dense_padic_ring_capped_absolute as PRing
            sage: R = PRing(Zp(13, type='capped-abs'), name='t'); R
            Univariate Polynomial Ring in t over 13-adic Ring with capped absolute precision 20
            sage: type(R.gen())
            <class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_padic_ring_capped_absolute_with_category.element_class'>
        """
        if element_class is None:
            from sage.rings.polynomial.padics.polynomial_padic_flat import \
                    Polynomial_padic_flat
            element_class = Polynomial_padic_flat
        PolynomialRing_dense_padic_ring_generic.__init__(self, base_ring,
                name=name, element_class=element_class, category=category)


class PolynomialRing_dense_padic_ring_fixed_mod(PolynomialRing_dense_padic_ring_generic):
    def __init__(self, base_ring, name=None, element_class=None, category=None):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_dense_padic_ring_fixed_mod as PRing
            sage: R = PRing(Zp(13, type='fixed-mod'), name='t'); R
            Univariate Polynomial Ring in t over 13-adic Ring of fixed modulus 13^20

            sage: type(R.gen())
            <class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_padic_ring_fixed_mod_with_category.element_class'>
        """
        if element_class is None:
            from sage.rings.polynomial.padics.polynomial_padic_flat import \
                    Polynomial_padic_flat
            element_class = Polynomial_padic_flat
        PolynomialRing_dense_padic_ring_generic.__init__(self, base_ring,
                name=name, element_class=element_class, category=category)


class PolynomialRing_dense_padic_field_capped_relative(PolynomialRing_dense_padic_field_generic):
    def __init__(self, base_ring, name=None, element_class=None, category=None):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_dense_padic_field_capped_relative as PRing
            sage: R = PRing(Qp(13), name='t'); R
            Univariate Polynomial Ring in t over 13-adic Field with capped relative precision 20
            sage: type(R.gen())
            <class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_padic_field_capped_relative_with_category.element_class'>
        """
        if element_class is None:
            from sage.rings.polynomial.padics.\
                    polynomial_padic_capped_relative_dense import \
                    Polynomial_padic_capped_relative_dense
            element_class = Polynomial_padic_capped_relative_dense
        PolynomialRing_dense_padic_field_generic.__init__(self, base_ring,
                name=name, element_class=element_class, category=category)


class PolynomialRing_dense_mod_n(PolynomialRing_commutative):
    def __init__(self, base_ring, name=None, element_class=None,
            implementation=None, category=None):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_dense_mod_n as PRing
            sage: R = PRing(Zmod(15), 'x'); R
            Univariate Polynomial Ring in x over Ring of integers modulo 15
            sage: type(R.gen())
            <type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>

            sage: R = PRing(Zmod(15), 'x', implementation='NTL'); R
            Univariate Polynomial Ring in x over Ring of integers modulo 15 (using NTL)
            sage: type(R.gen())
            <type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modn_ntl_zz'>

            sage: R = PRing(Zmod(2**63*3), 'x', implementation='NTL'); R
            Univariate Polynomial Ring in x over Ring of integers modulo 27670116110564327424 (using NTL)
            sage: type(R.gen())
            <type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modn_ntl_ZZ'>

            sage: R = PRing(Zmod(2**63*3), 'x', implementation='FLINT')
            Traceback (most recent call last):
            ...
            ValueError: FLINT does not support modulus 27670116110564327424

            sage: R = PRing(Zmod(2**63*3), 'x'); R
            Univariate Polynomial Ring in x over Ring of integers modulo 27670116110564327424 (using NTL)
            sage: type(R.gen())
            <type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modn_ntl_ZZ'>
        """
        if element_class is None:
            implementation = self._implementation_names(implementation, base_ring)[0]
            if implementation == "FLINT":
                from .polynomial_zmod_flint import \
                        Polynomial_zmod_flint as element_class
                self._implementation_repr = ''
            elif implementation == "NTL":
                modulus = base_ring.order()
                from . import polynomial_modn_dense_ntl as modn_dense_ntl
                if modulus < ZZ(modn_dense_ntl.zz_p_max):
                    element_class = modn_dense_ntl.Polynomial_dense_modn_ntl_zz
                else:
                    element_class = modn_dense_ntl.Polynomial_dense_modn_ntl_ZZ
                self._implementation_repr = ' (using NTL)'
        PolynomialRing_commutative.__init__(self, base_ring, name=name,
                element_class=element_class, category=category)

    @staticmethod
    def _implementation_names_impl(implementation, base_ring, sparse):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_dense_mod_n
            sage: PolynomialRing_dense_mod_n._implementation_names_impl("FLINT", IntegerModRing(10), False)
            ['FLINT', None]
            sage: PolynomialRing_dense_mod_n._implementation_names_impl("NTL", IntegerModRing(10), False)
            ['NTL']
            sage: PolynomialRing_dense_mod_n._implementation_names_impl(None, IntegerModRing(10), False)
            ['FLINT', None]
            sage: PolynomialRing_dense_mod_n._implementation_names_impl("generic", IntegerModRing(10), False)
            NotImplemented
            sage: PolynomialRing_dense_mod_n._implementation_names_impl("FLINT", IntegerModRing(10^30), False)
            Traceback (most recent call last):
            ...
            ValueError: FLINT does not support modulus 1000000000000000000000000000000
            sage: PolynomialRing_dense_mod_n._implementation_names_impl("NTL", IntegerModRing(10^30), False)
            ['NTL', None]
            sage: PolynomialRing_dense_mod_n._implementation_names_impl(None, IntegerModRing(10^30), False)
            ['NTL', None]
            sage: PolynomialRing_dense_mod_n._implementation_names_impl("generic", IntegerModRing(10^30), False)
            NotImplemented
            sage: PolynomialRing_dense_mod_n._implementation_names_impl(None, IntegerModRing(10^30), True)
            NotImplemented
        """
        if sparse:
            return NotImplemented
        modulus = base_ring.order()
        if modulus <= sys.maxsize:
            defaults = ["FLINT", None]
        elif implementation == "FLINT":
            raise ValueError("FLINT does not support modulus %s" % modulus)
        else:
            defaults = ["NTL", None]
        if implementation in defaults:
            return defaults
        elif implementation == "NTL":
            return [implementation]
        return NotImplemented

    @cached_method
    def modulus(self):
        """
        EXAMPLES::

            sage: R.<x> = Zmod(15)[]
            sage: R.modulus()
            15
        """
        return self.base_ring().characteristic()

    def _repr_(self):
        """
        TESTS::

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_integral_domain as PRing
            sage: R = PRing(ZZ, 'x', implementation='NTL'); R
            Univariate Polynomial Ring in x over Integer Ring (using NTL)
        """
        s = PolynomialRing_commutative._repr_(self)
        return s + self._implementation_repr

    def residue_field(self, ideal, names=None):
        """
        Return the residue finite field at the given ideal.

        EXAMPLES::

            sage: R.<t> = GF(2)[]
            sage: k.<a> = R.residue_field(t^3+t+1); k
            Residue field in a of Principal ideal (t^3 + t + 1) of Univariate Polynomial Ring in t over Finite Field of size 2 (using GF2X)
            sage: k.list()
            [0, a, a^2, a + 1, a^2 + a, a^2 + a + 1, a^2 + 1, 1]
            sage: R.residue_field(t)
            Residue field of Principal ideal (t) of Univariate Polynomial Ring in t over Finite Field of size 2 (using GF2X)
            sage: P = R.irreducible_element(8) * R
            sage: P
            Principal ideal (t^8 + t^4 + t^3 + t^2 + 1) of Univariate Polynomial Ring in t over Finite Field of size 2 (using GF2X)
            sage: k.<a> = R.residue_field(P); k
            Residue field in a of Principal ideal (t^8 + t^4 + t^3 + t^2 + 1) of Univariate Polynomial Ring in t over Finite Field of size 2 (using GF2X)
            sage: k.cardinality()
            256

        Non-maximal ideals are not accepted::

            sage: R.residue_field(t^2 + 1)
            Traceback (most recent call last):
            ...
            ArithmeticError: ideal is not maximal
            sage: R.residue_field(0)
            Traceback (most recent call last):
            ...
            ArithmeticError: ideal is not maximal
            sage: R.residue_field(1)
            Traceback (most recent call last):
            ...
            ArithmeticError: ideal is not maximal
        """
        ideal = self.ideal(ideal)
        if not ideal.is_maximal():
            raise ArithmeticError("ideal is not maximal")
        return ideal.residue_field(names)


class PolynomialRing_dense_mod_p(PolynomialRing_dense_finite_field,
                                 PolynomialRing_dense_mod_n,
                                 PolynomialRing_singular_repr):
    def __init__(self, base_ring, name="x", implementation=None, category=None):
        """
        TESTS::

            sage: P = GF(2)['x']; P
            Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)
            sage: type(P.gen())
            <type 'sage.rings.polynomial.polynomial_gf2x.Polynomial_GF2X'>

            sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_dense_mod_p
            sage: P = PolynomialRing_dense_mod_p(GF(5), 'x'); P
            Univariate Polynomial Ring in x over Finite Field of size 5
            sage: type(P.gen())
            <type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>

            sage: P = PolynomialRing_dense_mod_p(GF(5), 'x', implementation='NTL'); P
            Univariate Polynomial Ring in x over Finite Field of size 5 (using NTL)
            sage: type(P.gen())
            <type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_p'>

            sage: P = PolynomialRing_dense_mod_p(GF(9223372036854775837), 'x')
            sage: P
            Univariate Polynomial Ring in x over Finite Field of size 9223372036854775837 (using NTL)
            sage: type(P.gen())
            <type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_p'>

        This caching bug was fixed in :trac:`24264`::

            sage: p = 2^64 + 13
            sage: A = GF(p^2)
            sage: B = GF(p^3)
            sage: R = A.modulus().parent()
            sage: S = B.modulus().parent()
            sage: R is S
            True
        """
        implementation = self._implementation_names(implementation, base_ring)[0]
        if implementation == "FLINT":
            from .polynomial_zmod_flint import \
                    Polynomial_zmod_flint as element_class
            self._implementation_repr = ''
        elif implementation == "NTL":
            from .polynomial_modn_dense_ntl import \
                    Polynomial_dense_mod_p as element_class
            self._implementation_repr = ' (using NTL)'
        elif implementation == "GF2X":
            from .polynomial_gf2x import \
                    Polynomial_GF2X as element_class
            self._implementation_repr = ' (using GF2X)'
        PolynomialRing_dense_mod_n.__init__(self, base_ring, name=name,
                element_class=element_class, category=category)

        self._has_singular = can_convert_to_singular(self)

    @staticmethod
    def _implementation_names_impl(implementation, base_ring, sparse):
        """
        TESTS::

            sage: PolynomialRing(GF(2), 'x', implementation="GF2X")
            Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)
            sage: PolynomialRing(GF(2), 'x', implementation="NTL")
            Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)
            sage: PolynomialRing(GF(2), 'x', implementation=None)
            Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)
            sage: PolynomialRing(GF(2), 'x', implementation="FLINT")
            Univariate Polynomial Ring in x over Finite Field of size 2
            sage: PolynomialRing(GF(3), 'x', implementation="GF2X")
            Traceback (most recent call last):
            ...
            ValueError: GF2X only supports modulus 2
        """
        if sparse:
            return NotImplemented
        modulus = base_ring.characteristic()
        if modulus == 2:
            defaults = ["GF2X", "NTL", None]
        elif implementation == "GF2X":
            raise ValueError("GF2X only supports modulus 2")
        elif modulus <= sys.maxsize:
            defaults = ["FLINT", None]
        elif implementation == "FLINT":
            raise ValueError("FLINT does not support modulus %s" % modulus)
        else:
            defaults = ["NTL", None]
        if implementation in defaults:
            return defaults
        elif implementation in ["NTL", "FLINT"]:
            return [implementation]
        return NotImplemented

    def irreducible_element(self, n, algorithm=None):
        """
        Construct a monic irreducible polynomial of degree `n`.

        INPUT:

        - ``n`` -- integer: the degree of the polynomial to construct

        - ``algorithm`` -- string: algorithm to use, or ``None``.
          Currently available options are:

          - ``'adleman-lenstra'``: a variant of the Adleman--Lenstra
              algorithm as implemented in PARI.

          - ``'conway'``: look up the Conway polynomial of degree `n`
            over the field of `p` elements in the database; raise a
            ``RuntimeError`` if it is not found.

          - ``'ffprimroot'``: use the ``ffprimroot()`` function from
            PARI.

          - ``'first_lexicographic'``: return the lexicographically
            smallest irreducible polynomial of degree `n`.

          - ``'minimal_weight'``: return an irreducible polynomial of
            degree `n` with minimal number of non-zero coefficients.
            Only implemented for `p = 2`.

          - ``'primitive'``: return a polynomial `f` such that a root of
            `f` generates the multiplicative group of the finite field
            extension defined by `f`. This uses the Conway polynomial if
            possible, otherwise it uses ``ffprimroot``.

          - ``'random'``: try random polynomials until an irreducible
            one is found.

          If ``algorithm`` is ``None``, use `x - 1` in degree 1. In
          degree > 1, the Conway polynomial is used if it is found in
          the database.  Otherwise, the algorithm ``minimal_weight``
          is used if `p = 2`, and the algorithm ``adleman-lenstra`` if
          `p > 2`.

        OUTPUT:

        A monic irreducible polynomial of degree `n` in ``self``.

        EXAMPLES::

            sage: GF(5)['x'].irreducible_element(2)
            x^2 + 4*x + 2
            sage: GF(5)['x'].irreducible_element(2, algorithm="adleman-lenstra")
            x^2 + x + 1
            sage: GF(5)['x'].irreducible_element(2, algorithm="primitive")
            x^2 + 4*x + 2
            sage: GF(5)['x'].irreducible_element(32, algorithm="first_lexicographic")
            x^32 + 2
            sage: GF(5)['x'].irreducible_element(32, algorithm="conway")
            Traceback (most recent call last):
            ...
            RuntimeError: requested Conway polynomial not in database.
            sage: GF(5)['x'].irreducible_element(32, algorithm="primitive")
            x^32 + ...

        In characteristic 2::

            sage: GF(2)['x'].irreducible_element(33)
            x^33 + x^13 + x^12 + x^11 + x^10 + x^8 + x^6 + x^3 + 1
            sage: GF(2)['x'].irreducible_element(33, algorithm="minimal_weight")
            x^33 + x^10 + 1

        In degree 1::

            sage: GF(97)['x'].irreducible_element(1)
            x + 96
            sage: GF(97)['x'].irreducible_element(1, algorithm="conway")
            x + 92
            sage: GF(97)['x'].irreducible_element(1, algorithm="adleman-lenstra")
            x

        AUTHORS:

        - Peter Bruin (June 2013)

        - Jeroen Demeyer (September 2014): add "ffprimroot" algorithm,
          see :trac:`8373`.
        """
        from sage.libs.pari.all import pari
        from sage.rings.finite_rings.conway_polynomials import (conway_polynomial,
                                                                exists_conway_polynomial)
        from .polynomial_gf2x import (GF2X_BuildIrred_list,
                                     GF2X_BuildSparseIrred_list,
                                     GF2X_BuildRandomIrred_list)

        p = self.characteristic()
        n = int(n)
        if n < 1:
            raise ValueError("degree must be at least 1")

        if algorithm is None:
            if n == 1:
                return self((-1,1))  # Polynomial x - 1
            elif exists_conway_polynomial(p, n):
                algorithm = "conway"
            elif p == 2:
                algorithm = "minimal_weight"
            else:
                algorithm = "adleman-lenstra"
        elif algorithm == "primitive":
            if exists_conway_polynomial(p, n):
                algorithm = "conway"
            else:
                algorithm = "ffprimroot"

        if algorithm == "adleman-lenstra":
            return self(pari(p).ffinit(n))
        elif algorithm == "conway":
            return self(conway_polynomial(p, n))
        elif algorithm == "first_lexicographic":
            if p == 2:
                return self(GF2X_BuildIrred_list(n))
            else:
                # Fallback to PolynomialRing_dense_finite_field.irreducible_element
                pass
        elif algorithm == "ffprimroot":
            return self(pari(p).ffinit(n).ffgen().ffprimroot().charpoly())
        elif algorithm == "minimal_weight":
            if p == 2:
                return self(GF2X_BuildSparseIrred_list(n))
            else:
                raise NotImplementedError("'minimal_weight' option only implemented for p = 2")
        elif algorithm == "random":
            if p == 2:
                return self(GF2X_BuildRandomIrred_list(n))
            else:
                pass

        # No suitable algorithm found, try algorithms from the base class.
        return PolynomialRing_dense_finite_field.irreducible_element(self, n, algorithm)

def polygen(ring_or_element, name="x"):
    """
    Return a polynomial indeterminate.

    INPUT:

    - polygen(base_ring, name="x")

    - polygen(ring_element, name="x")

    If the first input is a ring, return a polynomial generator over
    that ring. If it is a ring element, return a polynomial generator
    over the parent of the element.

    EXAMPLES::

        sage: z = polygen(QQ,'z')
        sage: z^3 + z +1
        z^3 + z + 1
        sage: parent(z)
        Univariate Polynomial Ring in z over Rational Field

    .. note::

       If you give a list or comma separated string to polygen, you'll
       get a tuple of indeterminates, exactly as if you called
       polygens.
    """
    if is_RingElement(ring_or_element):
        base_ring = ring_or_element.parent()
    elif ring.is_Ring(ring_or_element):
        base_ring = ring_or_element
    else:
        raise TypeError("input must be a ring or ring element")
    from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

    t = PolynomialRing(base_ring, name)
    if t.ngens() > 1:
        return t.gens()
    return t.gen()

def polygens(base_ring, names="x", *args):
    """
    Return indeterminates over the given base ring with the given
    names.

    EXAMPLES::

        sage: x,y,z = polygens(QQ,'x,y,z')
        sage: (x+y+z)^2
        x^2 + 2*x*y + y^2 + 2*x*z + 2*y*z + z^2
        sage: parent(x)
        Multivariate Polynomial Ring in x, y, z over Rational Field
        sage: t = polygens(QQ,['x','yz','abc'])
        sage: t
        (x, yz, abc)

    The number of generators can be passed as a third argument::

        sage: polygens(QQ, 'x', 4)
        (x0, x1, x2, x3)
    """
    from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
    return PolynomialRing(base_ring, names, *args).gens()
