text: r"""
  Ideals of commutative rings
  
  Sage provides functionality for computing with ideals. One can create
  an ideal in any commutative or non-commutative ring `R` by giving a
  list of generators, using the notation ``R.ideal([a,b,...])``. The case
  of non-commutative rings is implemented in
  :mod:`~sage.rings.noncommutative_ideals`.
  
  A more convenient notation may be ``R*[a,b,...]`` or ``[a,b,...]*R``.
  If `R` is non-commutative, the former creates a left and the latter
  a right ideal, and ``R*[a,b,...]*R`` creates a two-sided ideal.
  """
  #*****************************************************************************
  #       Copyright (C) 2005 William Stein <wstein@gmail.com>
  #
  #  Distributed under the terms of the GNU General Public License (GPL)
  #
  #    This code is distributed in the hope that it will be useful,
  #    but WITHOUT ANY WARRANTY; without even the implied warranty of
  #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  #    General Public License for more details.
  #
  #  The full text of the GPL is available at:
  #
  #                  http://www.gnu.org/licenses/
  #*****************************************************************************
  
  from types import GeneratorType
  
  import sage.rings.ring
  from sage.structure.element import MonoidElement
  from sage.structure.richcmp import rich_to_bool, richcmp
  from sage.structure.sequence import Sequence
  
  def Ideal(*args, **kwds):
      r"""
      Create the ideal in ring with given generators.
  
      There are some shorthand notations for creating an ideal, in
      addition to using the :func:`Ideal` function:
  
      -  ``R.ideal(gens, coerce=True)``
      -  ``gens*R``
      -  ``R*gens``
  
      INPUT:
  
      -  ``R`` - A ring (optional; if not given, will try to infer it from
         ``gens``)
  
      -  ``gens`` - list of elements generating the ideal
  
      -  ``coerce`` - bool (optional, default: ``True``);
         whether ``gens`` need to be coerced into the ring.
  
  
      OUTPUT: The ideal of ring generated by ``gens``.
  
      EXAMPLES::
  
          sage: R.<x> = ZZ[]
          sage: I = R.ideal([4 + 3*x + x^2, 1 + x^2])
          sage: I
          Ideal (x^2 + 3*x + 4, x^2 + 1) of Univariate Polynomial Ring in x over Integer Ring
          sage: Ideal(R, [4 + 3*x + x^2, 1 + x^2])
          Ideal (x^2 + 3*x + 4, x^2 + 1) of Univariate Polynomial Ring in x over Integer Ring
          sage: Ideal((4 + 3*x + x^2, 1 + x^2))
          Ideal (x^2 + 3*x + 4, x^2 + 1) of Univariate Polynomial Ring in x over Integer Ring
  
      ::
  
          sage: ideal(x^2-2*x+1, x^2-1)
          Ideal (x^2 - 2*x + 1, x^2 - 1) of Univariate Polynomial Ring in x over Integer Ring
          sage: ideal([x^2-2*x+1, x^2-1])
          Ideal (x^2 - 2*x + 1, x^2 - 1) of Univariate Polynomial Ring in x over Integer Ring
          sage: l = [x^2-2*x+1, x^2-1]
          sage: ideal(f^2 for f in l)
          Ideal (x^4 - 4*x^3 + 6*x^2 - 4*x + 1, x^4 - 2*x^2 + 1) of
          Univariate Polynomial Ring in x over Integer Ring
  
      This example illustrates how Sage finds a common ambient ring for
      the ideal, even though 1 is in the integers (in this case).
  
      ::
  
          sage: R.<t> = ZZ['t']
          sage: i = ideal(1,t,t^2)
          sage: i
          Ideal (1, t, t^2) of Univariate Polynomial Ring in t over Integer Ring
          sage: ideal(1/2,t,t^2)
          Principal ideal (1) of Univariate Polynomial Ring in t over Rational Field
  
      This shows that the issues at :trac:`1104` are resolved::
  
          sage: Ideal(3, 5)
          Principal ideal (1) of Integer Ring
          sage: Ideal(ZZ, 3, 5)
          Principal ideal (1) of Integer Ring
          sage: Ideal(2, 4, 6)
          Principal ideal (2) of Integer Ring
  
      You have to provide enough information that Sage can figure out
      which ring to put the ideal in.
  
      ::
  
          sage: I = Ideal([])
          Traceback (most recent call last):
          ...
          ValueError: unable to determine which ring to embed the ideal in
  
          sage: I = Ideal()
          Traceback (most recent call last):
          ...
          ValueError: need at least one argument
  
      Note that some rings use different ideal implementations than the standard,
      even if they are PIDs.::
  
          sage: R.<x> = GF(5)[]
          sage: I = R*(x^2+3)
          sage: type(I)
          <class 'sage.rings.polynomial.ideal.Ideal_1poly_field'>
  
      You can also pass in a specific ideal type::
  
          sage: from sage.rings.ideal import Ideal_pid
          sage: I = Ideal(x^2+3,ideal_class=Ideal_pid)
          sage: type(I)
          <class 'sage.rings.ideal.Ideal_pid'>
  
      TESTS::
  
          sage: R.<x> = ZZ[]
          sage: I = R.ideal([4 + 3*x + x^2, 1 + x^2])
          sage: I == loads(dumps(I))
          True
  
      ::
  
          sage: I = Ideal(R, [4 + 3*x + x^2, 1 + x^2])
          sage: I == loads(dumps(I))
          True
  
      ::
  
          sage: I = Ideal((4 + 3*x + x^2, 1 + x^2))
          sage: I == loads(dumps(I))
          True
  
      This shows that the issue at :trac:`5477` is fixed::
  
          sage: R.<x> = QQ[]
          sage: I = R.ideal([x + x^2])
          sage: J = R.ideal([2*x + 2*x^2])
          sage: J
          Principal ideal (x^2 + x) of Univariate Polynomial Ring in x over Rational Field
          sage: S = R.quotient_ring(I)
          sage: U = R.quotient_ring(J)
          sage: I == J
          True
          sage: S == U
          True
      """
      if len(args) == 0:
          raise ValueError("need at least one argument")
      if len(args) == 1 and args[0] == []:
          raise ValueError("unable to determine which ring to embed the ideal in")
  
      first = args[0]
  
      inferred_field = False
      if not isinstance(first, sage.rings.ring.Ring):
          if isinstance(first, Ideal_generic) and len(args) == 1:
              R = first.ring()
              gens = first.gens()
          else:
              if isinstance(first, (list, tuple, GeneratorType)) and len(args) == 1:
                  gens = first
              else:
                  gens = args
              gens = Sequence(gens)
              R = gens.universe()
              inferred_field = isinstance(R, sage.rings.ring.Field)
      else:
          R = first
          gens = args[1:]
  
      if not isinstance(R, sage.rings.ring.CommutativeRing):
          raise TypeError("R must be a commutative ring")
  
      I = R.ideal(*gens, **kwds)
  
      if inferred_field and not isinstance(I, Ideal_fractional):  # trac 32320
          import warnings
          warnings.warn(f'Constructing an ideal in {R}, which is a field.'
                        ' Did you intend to take numerators first?'
                        ' This warning can be muted by passing the base ring to Ideal() explicitly.')
  
      return I
  
  def is_Ideal(x):
      r"""
      Return ``True`` if object is an ideal of a ring.
  
      EXAMPLES:
  
      A simple example involving the ring of integers. Note
      that Sage does not interpret rings objects themselves as ideals.
      However, one can still explicitly construct these ideals::
  
          sage: from sage.rings.ideal import is_Ideal
          sage: R = ZZ
          sage: is_Ideal(R)
          False
          sage: 1*R; is_Ideal(1*R)
          Principal ideal (1) of Integer Ring
          True
          sage: 0*R; is_Ideal(0*R)
          Principal ideal (0) of Integer Ring
          True
  
      Sage recognizes ideals of polynomial rings as well::
  
          sage: R = PolynomialRing(QQ, 'x'); x = R.gen()
          sage: I = R.ideal(x^2 + 1); I
          Principal ideal (x^2 + 1) of Univariate Polynomial Ring in x over Rational Field
          sage: is_Ideal(I)
          True
          sage: is_Ideal((x^2 + 1)*R)
          True
      """
      return isinstance(x, Ideal_generic)
  
  
  class Ideal_generic(MonoidElement):
      """
      An ideal.
  
      See :func:`Ideal()`.
      """
      def __init__(self, ring, gens, coerce=True):
          """
          Initialize this ideal.
  
          INPUT:
  
          - ``ring`` -- A ring
  
          - ``gens`` -- The generators for this ideal
  
          - ``coerce`` -- (default: ``True``) If ``gens`` needs to be coerced
            into ``ring``.
  
          EXAMPLES::
  
              sage: R.<x> = ZZ[]
              sage: R.ideal([4 + 3*x + x^2, 1 + x^2])
              Ideal (x^2 + 3*x + 4, x^2 + 1) of Univariate Polynomial Ring in x over Integer Ring
          """
          self.__ring = ring
          if not isinstance(gens, (list, tuple)):
              gens = [gens]
          if coerce:
              gens = [ring(x) for x in gens]
  
          gens = tuple(gens)
          if len(gens) == 0:
              gens = (ring.zero(),)
          self.__gens = gens
          MonoidElement.__init__(self, ring.ideal_monoid())
  
      def _repr_short(self):
          """
          Represent the list of generators.
  
          EXAMPLES::
  
              sage: P.<a,b,c> = QQ[]
              sage: P*[a^2,a*b+c,c^3]
              Ideal (a^2, a*b + c, c^3) of Multivariate Polynomial Ring in a, b, c over Rational Field
              sage: (P*[a^2,a*b+c,c^3])._repr_short()
              '(a^2, a*b + c, c^3)'
  
          If the string representation of a generator contains a line break,
          the generators are not represented from left to right but from
          top to bottom. This is the case, e.g., for matrices::
  
              sage: MS = MatrixSpace(QQ,2,2)
              sage: MS*[MS.1,2]
              Left Ideal
              (
                [0 1]
                [0 0],
              <BLANKLINE>
                [2 0]
                [0 2]
              )
               of Full MatrixSpace of 2 by 2 dense matrices over Rational Field
  
  
          """
          L = []
          has_return = False
          for x in self.gens():
              s = repr(x)
              if '\n' in s:
                  has_return = True
                  s = s.replace('\n','\n  ')
              L.append(s)
          if has_return:
              return '\n(\n  %s\n)\n'%(',\n\n  '.join(L))
          return '(%s)'%(', '.join(L))
  
      def __repr__(self):
          """
          Return a string representation of ``self``.
  
          EXAMPLES::
  
              sage: P.<a,b,c> = QQ[]
              sage: P*[a^2,a*b+c,c^3] # indirect doctest
              Ideal (a^2, a*b + c, c^3) of Multivariate Polynomial Ring in a, b, c over Rational Field
          """
          return "Ideal %s of %s"%(self._repr_short(), self.ring())
  
      def random_element(self, *args, **kwds):
          """
          Return a random element in this ideal.
  
          EXAMPLES::
  
              sage: P.<a,b,c> = GF(5)[[]]
              sage: I = P.ideal([a^2, a*b + c, c^3])
              sage: I.random_element()  # random
              2*a^5*c + a^2*b*c^4 + ... + O(a, b, c)^13
  
          """
          return sum(self.__ring.random_element(*args, **kwds) * g for g in self.__gens)
  
  
      def _richcmp_(self, other, op):
          """
          Compares the generators of two ideals.
  
          INPUT:
  
          - ``other`` -- an ideal
  
          OUTPUT:
  
          boolean
  
          EXAMPLES::
  
              sage: R = ZZ; I = ZZ*2; J = ZZ*(-2)
              sage: I == J
              True
          """
          S = set(self.gens())
          T = set(other.gens())
          if S == T:
              return rich_to_bool(op, 0)
          return richcmp(self.gens(), other.gens(), op)
  
      def __contains__(self, x):
          """
          Check if ``x`` is in ``self``.
  
          EXAMPLES::
  
              sage: P.<a,b,c> = QQ[]
              sage: I = P*[a, b]
              sage: a + b in I
              True
              sage: P2.<w,x,y,z> = QQ[]
              sage: x + 2*y + w*z in I
              False
          """
          try:
              return self._contains_(self.__ring(x))
          except TypeError:
              return False
  
      def _contains_(self, x):
          """
          Check if ``x``, which is assumed to be in the ambient ring, is in
          this ideal.
  
          .. TODO::
  
              Implement this method.
  
          EXAMPLES::
  
              sage: P.<a> = ZZ[]
              sage: I = P*[a]
              sage: I._contains_(a)
              Traceback (most recent call last):
              ...
              NotImplementedError
  
          Note that calling ``in`` does not call this method::
  
              sage: a in I
              True
          """
          raise NotImplementedError
  
      def __bool__(self):
          r"""
          Return ``True`` if this ideal is not `(0)`.
  
          TESTS::
  
              sage: I = ZZ.ideal(5)
              sage: bool(I)
              True
  
          ::
  
              sage: I = ZZ['x'].ideal(0)
              sage: bool(I)
              False
  
          ::
  
              sage: I = ZZ['x'].ideal(ZZ['x'].gen()^2)
              sage: bool(I)
              True
  
          ::
  
              sage: I = QQ['x', 'y'].ideal(0)
              sage: bool(I)
              False
          """
          for g in self.gens():
              if not g.is_zero():
                  return True
          return False
  
      
  
      def base_ring(self):
          r"""
          Returns the base ring of this ideal.
  
          EXAMPLES::
  
              sage: R = ZZ
              sage: I = 3*R; I
              Principal ideal (3) of Integer Ring
              sage: J = 2*I; J
              Principal ideal (6) of Integer Ring
              sage: I.base_ring(); J.base_ring()
              Integer Ring
              Integer Ring
  
          We construct an example of an ideal of a quotient ring::
  
              sage: R = PolynomialRing(QQ, 'x'); x = R.gen()
              sage: I = R.ideal(x^2 - 2)
              sage: I.base_ring()
              Rational Field
  
          And `p`-adic numbers::
  
              sage: R = Zp(7, prec=10); R
              7-adic Ring with capped relative precision 10
              sage: I = 7*R; I
              Principal ideal (7 + O(7^11)) of 7-adic Ring with capped relative precision 10
              sage: I.base_ring()
              7-adic Ring with capped relative precision 10
          """
          return self.ring().base_ring()
  
      def apply_morphism(self, phi):
          r"""
          Apply the morphism ``phi`` to every element of this ideal.
          Returns an ideal in the domain of ``phi``.
  
          EXAMPLES::
  
              sage: psi = CC['x'].hom([-CC['x'].0])
              sage: J = ideal([CC['x'].0 + 1]); J
              Principal ideal (x + 1.00000000000000) of Univariate Polynomial Ring in x over Complex Field with 53 bits of precision
              sage: psi(J)
              Principal ideal (x - 1.00000000000000) of Univariate Polynomial Ring in x over Complex Field with 53 bits of precision
              sage: J.apply_morphism(psi)
              Principal ideal (x - 1.00000000000000) of Univariate Polynomial Ring in x over Complex Field with 53 bits of precision
  
          ::
  
              sage: psi = ZZ['x'].hom([-ZZ['x'].0])
              sage: J = ideal([ZZ['x'].0, 2]); J
              Ideal (x, 2) of Univariate Polynomial Ring in x over Integer Ring
              sage: psi(J)
              Ideal (-x, 2) of Univariate Polynomial Ring in x over Integer Ring
              sage: J.apply_morphism(psi)
              Ideal (-x, 2) of Univariate Polynomial Ring in x over Integer Ring
  
          TESTS::
  
              sage: K.<a> = NumberField(x^2 + 1)
              sage: A = K.ideal(a)
              sage: taus = K.embeddings(K)
              sage: A.apply_morphism(taus[0]) # identity
              Fractional ideal (a)
              sage: A.apply_morphism(taus[1]) # complex conjugation
              Fractional ideal (-a)
              sage: A.apply_morphism(taus[0]) == A.apply_morphism(taus[1])
              True
  
          ::
  
              sage: K.<a> = NumberField(x^2 + 5)
              sage: B = K.ideal([2, a + 1]); B
              Fractional ideal (2, a + 1)
              sage: taus = K.embeddings(K)
              sage: B.apply_morphism(taus[0]) # identity
              Fractional ideal (2, a + 1)
  
          Since 2 is totally ramified, complex conjugation fixes it::
  
              sage: B.apply_morphism(taus[1]) # complex conjugation
              Fractional ideal (2, a + 1)
              sage: taus[1](B)
              Fractional ideal (2, a + 1)
          """
          from sage.categories.morphism import is_Morphism
          if not is_Morphism(phi):
              raise TypeError("phi must be a morphism")
          # delegate: morphisms know how to apply themselves to ideals
          return phi(self)
  
      def _latex_(self):
          r"""
          Return a latex representation of ``self``.
  
          EXAMPLES::
  
              sage: latex(3*ZZ) # indirect doctest
              \left(3\right)\Bold{Z}
          """
          import sage.misc.latex as latex
          return '\\left(%s\\right)%s' % (", ".join(latex.latex(g)
                                                    for g in self.gens()),
                                          latex.latex(self.ring()))
  
      def ring(self):
          """
          Return the ring containing this ideal.
  
          EXAMPLES::
  
              sage: R = ZZ
              sage: I = 3*R; I
              Principal ideal (3) of Integer Ring
              sage: J = 2*I; J
              Principal ideal (6) of Integer Ring
              sage: I.ring(); J.ring()
              Integer Ring
              Integer Ring
  
          Note that ``self.ring()`` is different from
          ``self.base_ring()``
  
          ::
  
              sage: R = PolynomialRing(QQ, 'x'); x = R.gen()
              sage: I = R.ideal(x^2 - 2)
              sage: I.base_ring()
              Rational Field
              sage: I.ring()
              Univariate Polynomial Ring in x over Rational Field
  
          Another example using polynomial rings::
  
              sage: R = PolynomialRing(QQ, 'x'); x = R.gen()
              sage: I = R.ideal(x^2 - 3)
              sage: I.ring()
              Univariate Polynomial Ring in x over Rational Field
              sage: Rbar = R.quotient(I, names='a')
              sage: S = PolynomialRing(Rbar, 'y'); y = Rbar.gen(); S
              Univariate Polynomial Ring in y over Univariate Quotient Polynomial Ring in a over Rational Field with modulus x^2 - 3
              sage: J = S.ideal(y^2 + 1)
              sage: J.ring()
              Univariate Polynomial Ring in y over Univariate Quotient Polynomial Ring in a over Rational Field with modulus x^2 - 3
          """
          return self.__ring
  
      def reduce(self, f):
          r"""
          Return the reduction of the element of `f` modulo ``self``.
  
          This is an element of `R` that is equivalent modulo `I` to `f` where
          `I` is ``self``.
  
          EXAMPLES::
  
              sage: ZZ.ideal(5).reduce(17)
              2
              sage: parent(ZZ.ideal(5).reduce(17))
              Integer Ring
          """
          return f       # default
  
      def gens(self):
          """
          Return a set of generators / a basis of ``self``.
  
          This is the set of generators provided during creation of this ideal.
  
          EXAMPLES::
  
              sage: P.<x,y> = PolynomialRing(QQ,2)
              sage: I = Ideal([x,y+1]); I
              Ideal (x, y + 1) of Multivariate Polynomial Ring in x, y over Rational Field
              sage: I.gens()
              [x, y + 1]
  
          ::
  
              sage: ZZ.ideal(5,10).gens()
              (5,)
          """
          return self.__gens
  
      def gen(self, i):
          """
          Return the ``i``-th generator in the current basis of this ideal.
  
          EXAMPLES::
  
              sage: P.<x,y> = PolynomialRing(QQ,2)
              sage: I = Ideal([x,y+1]); I
              Ideal (x, y + 1) of Multivariate Polynomial Ring in x, y over Rational Field
              sage: I.gen(1)
              y + 1
  
              sage: ZZ.ideal(5,10).gen()
              5
          """
          return self.__gens[i]
  
      def ngens(self):
          """
          Return the number of generators in the basis.
  
          EXAMPLES::
  
              sage: P.<x,y> = PolynomialRing(QQ,2)
              sage: I = Ideal([x,y+1]); I
              Ideal (x, y + 1) of Multivariate Polynomial Ring in x, y over Rational Field
              sage: I.ngens()
              2
  
              sage: ZZ.ideal(5,10).ngens()
              1
          """
          return len(self.__gens)
  
      def gens_reduced(self):
          r"""
          Same as :meth:`gens()` for this ideal, since there is currently no
          special ``gens_reduced`` algorithm implemented for this ring.
  
          This method is provided so that ideals in `\ZZ` have the method
          ``gens_reduced()``, just like ideals of number fields.
  
          EXAMPLES::
  
              sage: ZZ.ideal(5).gens_reduced()
              (5,)
          """
          return self.gens()
  
      def is_maximal(self):
          r"""
          Return ``True`` if the ideal is maximal in the ring containing the
          ideal.
  
          .. TODO::
  
              This is not implemented for many rings.  Implement it!
  
          EXAMPLES::
  
              sage: R = ZZ
              sage: I = R.ideal(7)
              sage: I.is_maximal()
              True
              sage: R.ideal(16).is_maximal()
              False
              sage: S = Integers(8)
              sage: S.ideal(0).is_maximal()
              False
              sage: S.ideal(2).is_maximal()
              True
              sage: S.ideal(4).is_maximal()
              False
          """
          from sage.rings.integer_ring import ZZ
          R = self.ring()
          if hasattr(R, 'cover_ring') and R.cover_ring() is ZZ:
              # The following test only works for quotients of Z/nZ: for
              # many other rings in Sage, testing whether R/I is a field
              # is done by testing whether I is maximal, so this would
              # result in a loop.
              return R.quotient(self).is_field()
          kd = R.krull_dimension()
          if kd == 0 or (kd == 1 and R.is_integral_domain()):
              # For rings of Krull dimension 0, or for integral domains of
              # Krull dimension 1, every nontrivial prime ideal is maximal.
              return self.is_prime()
          else:
              raise NotImplementedError
  
      def is_primary(self, P=None):
          r"""
          Returns ``True`` if this ideal is primary (or `P`-primary, if
          a prime ideal `P` is specified).
  
          Recall that an ideal `I` is primary if and only if `I` has a
          unique associated prime (see page 52 in [AM1969]_).  If this
          prime is `P`, then `I` is said to be `P`-primary.
  
          INPUT:
  
          - ``P`` - (default: ``None``) a prime ideal in the same ring
  
          EXAMPLES::
  
              sage: R.<x, y> = QQ[]
              sage: I = R.ideal([x^2, x*y])
              sage: I.is_primary()
              False
              sage: J = I.primary_decomposition()[1]; J
              Ideal (y, x^2) of Multivariate Polynomial Ring in x, y over Rational Field
              sage: J.is_primary()
              True
              sage: J.is_prime()
              False
  
          Some examples from the Macaulay2 documentation::
  
              sage: R.<x, y, z> = GF(101)[]
              sage: I = R.ideal([y^6])
              sage: I.is_primary()
              True
              sage: I.is_primary(R.ideal([y]))
              True
              sage: I = R.ideal([x^4, y^7])
              sage: I.is_primary()
              True
              sage: I = R.ideal([x*y, y^2])
              sage: I.is_primary()
              False
  
          .. NOTE::
  
              This uses the list of associated primes.
          """
          try:
              ass = self.associated_primes()
          except (NotImplementedError, ValueError):
              raise NotImplementedError
          if P is None:
              return (len(ass) == 1)
          else:
              return (len(ass) == 1) and (ass[0] == P)
  
  
      def primary_decomposition(self):
          r"""
          Return a decomposition of this ideal into primary ideals.
  
          EXAMPLES::
  
              sage: R = ZZ['x']
              sage: I = R.ideal(7)
              sage: I.primary_decomposition()
              Traceback (most recent call last):
              ...
              NotImplementedError
          """
          raise NotImplementedError
  
      def is_prime(self):
          r"""
          Return ``True`` if this ideal is prime.
  
          EXAMPLES::
  
              sage: R.<x, y> = QQ[]
              sage: I = R.ideal([x, y])
              sage: I.is_prime()        # a maximal ideal
              True
              sage: I = R.ideal([x^2-y])
              sage: I.is_prime()        # a non-maximal prime ideal
              True
              sage: I = R.ideal([x^2, y])
              sage: I.is_prime()        # a non-prime primary ideal
              False
              sage: I = R.ideal([x^2, x*y])
              sage: I.is_prime()        # a non-prime non-primary ideal
              False
  
              sage: S = Integers(8)
              sage: S.ideal(0).is_prime()
              False
              sage: S.ideal(2).is_prime()
              True
              sage: S.ideal(4).is_prime()
              False
  
          Note that this method is not implemented for all rings where it
          could be::
  
              sage: R.<x> = ZZ[]
              sage: I = R.ideal(7)
              sage: I.is_prime()        # when implemented, should be True
              Traceback (most recent call last):
              ...
              NotImplementedError
  
          .. NOTE::
  
              For general rings, uses the list of associated primes.
          """
          from sage.rings.integer_ring import ZZ
          R = self.ring()
          if hasattr(R, 'cover_ring') and R.cover_ring() is ZZ and R.is_finite():
              # For quotient rings of ZZ, prime is the same as maximal.
              return self.is_maximal()
          try:
              ass = self.associated_primes()
          except (NotImplementedError, ValueError):
              raise NotImplementedError
          if len(ass) != 1:
              return False
          if self == ass[0]:
              return True
          else:
              return False
  
      def associated_primes(self):
          r"""
          Return the list of associated prime ideals of this ideal.
  
          EXAMPLES::
  
              sage: R = ZZ['x']
              sage: I = R.ideal(7)
              sage: I.associated_primes()
              Traceback (most recent call last):
              ...
              NotImplementedError
          """
          raise NotImplementedError
  
      def minimal_associated_primes(self):
          r"""
          Return the list of minimal associated prime ideals of this ideal.
  
          EXAMPLES::
  
              sage: R = ZZ['x']
              sage: I = R.ideal(7)
              sage: I.minimal_associated_primes()
              Traceback (most recent call last):
              ...
              NotImplementedError
          """
          raise NotImplementedError
  
      def embedded_primes(self):
          r"""
          Return the list of embedded primes of this ideal.
  
          EXAMPLES::
  
              sage: R.<x, y> = QQ[]
              sage: I = R.ideal(x^2, x*y)
              sage: I.embedded_primes()
              [Ideal (y, x) of Multivariate Polynomial Ring in x, y over Rational Field]
          """
          # by definition, embedded primes are associated primes that
          # are not minimal (under inclusion)
          ass = self.associated_primes()
          min_ass = self.minimal_associated_primes()
          emb = []
          for p in ass:
              try:
                  min_ass.index(p)
              except ValueError:
                  emb.append(p)
          emb.sort()
          return emb
  
      def is_principal(self):
          r"""
          Returns ``True`` if the ideal is principal in the ring containing the
          ideal.
  
          .. TODO::
  
              Code is naive. Only keeps track of ideal generators as set
              during initialization of the ideal. (Can the base ring change? See
              example below.)
  
          EXAMPLES::
  
              sage: R = ZZ['x']
              sage: I = R.ideal(2,x)
              sage: I.is_principal()
              Traceback (most recent call last):
              ...
              NotImplementedError
              sage: J = R.base_extend(QQ).ideal(2,x)
              sage: J.is_principal()
              True
          """
          if len(self.gens()) <= 1:
              return True
          raise NotImplementedError
  
      def is_trivial(self):
          r"""
          Return ``True`` if this ideal is `(0)` or `(1)`.
  
          TESTS::
  
              sage: I = ZZ.ideal(5)
              sage: I.is_trivial()
              False
  
          ::
  
              sage: I = ZZ['x'].ideal(-1)
              sage: I.is_trivial()
              True
  
          ::
  
              sage: I = ZZ['x'].ideal(ZZ['x'].gen()^2)
              sage: I.is_trivial()
              False
  
          ::
  
              sage: I = QQ['x', 'y'].ideal(-5)
              sage: I.is_trivial()
              True
  
          ::
  
              sage: I = CC['x'].ideal(0)
              sage: I.is_trivial()
              True
  
          This test addresses ticket :trac:`20514`::
          
              sage: R = QQ['x', 'y']
              sage: I = R.ideal(R.gens())
              sage: I.is_trivial()
              False
          """
          return self.is_zero() or self == self.ring().unit_ideal()
  
      def category(self):
          """
          Return the category of this ideal.
  
          .. NOTE::
  
              category is dependent on the ring of the ideal.
  
          EXAMPLES::
  
              sage: P.<x> = ZZ[]
              sage: I = ZZ.ideal(7)
              sage: J = P.ideal(7,x)
              sage: K = P.ideal(7)
              sage: I.category()
              Category of ring ideals in Integer Ring
              sage: J.category()
              Category of ring ideals in Univariate Polynomial Ring in x
              over Integer Ring
              sage: K.category()
              Category of ring ideals in Univariate Polynomial Ring in x
              over Integer Ring
          """
          import sage.categories.all
          return sage.categories.all.Ideals(self.__ring)
  
      def __add__(self, other):
          """
          Add ``self`` on the left to ``other``.
  
          This makes sure that ``other`` and ``self`` are in the same rings.
  
          EXAMPLES::
  
              sage: P.<x,y,z> = QQ[]
              sage: I = [x + y]*P
              sage: I + [y + z]
              Ideal (x + y, y + z) of Multivariate Polynomial Ring in x, y, z over Rational Field
          """
          if not isinstance(other, Ideal_generic):
              other = self.ring().ideal(other)
          return self.ring().ideal(self.gens() + other.gens())
  
      def __radd__(self, other):
          """
          Add ``self`` on the right to ``other``.
  
          This makes sure that ``other`` and ``self`` are in the same rings.
  
          EXAMPLES::
  
              sage: P.<x,y,z> = QQ[]
              sage: I = [x + y]*P
              sage: [y + z] + I
              Ideal (x + y, y + z) of Multivariate Polynomial Ring in x, y, z over Rational Field
          """
          if not isinstance(other, Ideal_generic):
              other = self.ring().ideal(other)
          return self.ring().ideal(self.gens() + other.gens())
  
      def __mul__(self, other):
          """
          This method just makes sure that ``self`` and other are ideals in the
          same ring and then calls :meth:`_mul_`. If you want to change the
          behaviour of ideal multiplication in a subclass of
          :class:`Ideal_generic` please overwrite :meth:`_mul_` and not
          :meth:`__mul__`.
  
          EXAMPLES::
  
              sage: P.<x,y,z> = QQ[]
              sage: I = [x*y + y*z, x^2 + x*y - y*x - y^2] * P
              sage: I * 2    # indirect doctest
              Ideal (2*x*y + 2*y*z, 2*x^2 - 2*y^2) of Multivariate Polynomial Ring in x, y, z over Rational Field
          """
          if not isinstance(other, Ideal_generic):
              try:
                  if self.ring().has_coerce_map_from(other):
                      return self
              except (TypeError,ArithmeticError,ValueError):
                  pass
              other = self.ring().ideal(other)
          return self._mul_(other)
  
      def _mul_(self, other):
          """
          This is a very general implementation of Ideal multiplication.
  
          This method assumes that ``self`` and ``other`` are Ideals of the
          same ring.
  
          The number of generators of ```self * other` will be
          ``self.ngens() * other.ngens()``. So if used repeatedly this method
          will create an ideal with a uselessly large amount of generators.
          Therefore it is advisable to overwrite this method with a method that
          takes advantage of the structure of the ring your working in.
  
          Example::
  
              sage: P.<x,y,z> = QQ[]
              sage: I=P.ideal([x*y, x*z, x^2])
              sage: J=P.ideal([x^2, x*y])
              sage: I._mul_(J)
              Ideal (x^3*y, x^2*y^2, x^3*z, x^2*y*z, x^4, x^3*y) of Multivariate Polynomial Ring in x, y, z over Rational Field
          """
          return self.ring().ideal([z for z in [x*y for x in self.gens() for y in other.gens()] if z])
  
      def __rmul__(self, other):
          """
          Multiply ``self`` on the right with ``other``.
  
          EXAMPLES::
  
              sage: P.<x,y,z> = QQ[]
              sage: I = [x*y+y*z,x^2+x*y-y*x-y^2]*P
              sage: [2]*I    # indirect doctest
              Ideal (2*x*y + 2*y*z, 2*x^2 - 2*y^2) of Multivariate Polynomial Ring in x, y, z over Rational Field
  
          """
          if not isinstance(other, Ideal_generic):
              try:
                  if self.ring().has_coerce_map_from(other):
                      return self
              except (TypeError,ArithmeticError,ValueError):
                  pass
              other = self.ring().ideal(other)
          return self.ring().ideal([z for z in [y*x for x in self.gens() for y in other.gens()] if z])
  
      def norm(self):
          """
          Returns the norm of this ideal.
  
          In the general case, this is just the ideal itself, since the ring it
          lies in can't be implicitly assumed to be an extension of anything.
  
          We include this function for compatibility with cases such as ideals in
          number fields.
  
          EXAMPLES::
  
              sage: R.<t> = GF(8, names='a')[]
              sage: I = R.ideal(t^4 + t + 1)
              sage: I.norm()
              Principal ideal (t^4 + t + 1) of Univariate Polynomial Ring in t over Finite Field in a of size 2^3
          """
          return self
  
      def absolute_norm(self):
          """
          Returns the absolute norm of this ideal.
  
          In the general case, this is just the ideal itself, since the ring it
          lies in can't be implicitly assumed to be an extension of anything.
  
          We include this function for compatibility with cases such as ideals in
          number fields.
  
          .. TODO::
  
              Implement this method.
  
          EXAMPLES::
  
              sage: R.<t> = GF(9, names='a')[]
              sage: I = R.ideal(t^4 + t + 1)
              sage: I.absolute_norm()
              Traceback (most recent call last):
              ...
              NotImplementedError
          """
          raise NotImplementedError
  
      def _macaulay2_init_(self, macaulay2=None):
          """
          Return Macaulay2 ideal corresponding to this ideal.
  
          EXAMPLES:
  
          Ideals in multivariate polynomial rings::
  
              sage: R.<x,y,z,w> = PolynomialRing(ZZ, 4)
              sage: I = R.ideal([x*y-z^2, y^2-w^2]); I
              Ideal (x*y - z^2, y^2 - w^2) of Multivariate Polynomial Ring in x, y, z, w over Integer Ring
              sage: macaulay2(I)                              # optional - macaulay2
                            2   2    2
              ideal (x*y - z , y  - w )
  
          Ideals in univariate polynomial rings::
  
              sage: R.<x> = PolynomialRing(ZZ)
              sage: I = R.ideal([4 + 3*x + x^2, 1 + x^2]); I
              Ideal (x^2 + 3*x + 4, x^2 + 1) of Univariate Polynomial Ring in x over Integer Ring
              sage: macaulay2(I)                              # optional - macaulay2
                      2            2
              ideal (x  + 3x + 4, x  + 1)
  
          Field ideals generated from the polynomial ring over
          two variables in the finite field of size 2::
  
              sage: P.<x,y> = PolynomialRing(GF(2), 2)
              sage: I = sage.rings.ideal.FieldIdeal(P); I
              Ideal (x^2 + x, y^2 + y) of Multivariate Polynomial Ring in x, y over
              Finite Field of size 2
              sage: macaulay2(I)                              # optional - macaulay2
                      2       2
              ideal (x  + x, y  + y)
  
          Ideals in PIDs::
  
              sage: macaulay2(ideal(5))                       # optional - macaulay2
              ideal 5
              sage: J = ideal(QQ(5))
              ...
              sage: macaulay2(J)                              # optional - macaulay2
              ideal 1
  
          TESTS:
  
          Check that a cached base ring is used (:trac:`28074`)::
  
              sage: R.<x,y> = QQ[]
              sage: R1 = macaulay2(R)                        # optional - macaulay2
              sage: _ = macaulay2('ZZ[x,y]')                 # optional - macaulay2
              sage: R2 = macaulay2(R.ideal(y^2 - x)).ring()  # optional - macaulay2
              sage: R1._operator('===', R2)                  # optional - macaulay2
              true
  
          """
          if macaulay2 is None:
              from sage.interfaces.macaulay2 import macaulay2 as m2_default
              macaulay2 = m2_default
  
          R = self.ring()
          macaulay2.use(R._macaulay2_(macaulay2))
          gens = [repr(x) for x in self.gens()]
          if len(gens) == 0:
              gens = ['0']
          return macaulay2.ideal(gens)
  
  
  class Ideal_principal(Ideal_generic):
      """
      A principal ideal.
  
      See :func:`Ideal()`.
      """
      # now Ideal_principal takes a list.
      #def __init__(self, ring, gen):
      #    Ideal_generic.__init__(self, ring, [gen])
  
      def __repr__(self):
          """
          Return a string representation of ``self``.
  
          EXAMPLES::
  
              sage: R.<x> = ZZ[]
              sage: I = R.ideal(x)
              sage: I # indirect doctest
              Principal ideal (x) of Univariate Polynomial Ring in x over Integer Ring
          """
          return "Principal ideal (%s) of %s"%(self.gen(), self.ring())
  
      def is_principal(self):
          r"""
          Returns ``True`` if the ideal is principal in the ring containing the
          ideal. When the ideal construction is explicitly principal (i.e.
          when we define an ideal with one element) this is always the case.
  
          EXAMPLES:
  
          Note that Sage automatically coerces ideals into
          principal ideals during initialization::
  
              sage: R.<x> = ZZ[]
              sage: I = R.ideal(x)
              sage: J = R.ideal(2,x)
              sage: K = R.base_extend(QQ).ideal(2,x)
              sage: I
              Principal ideal (x) of Univariate Polynomial Ring in x
              over Integer Ring
              sage: J
              Ideal (2, x) of Univariate Polynomial Ring in x over Integer Ring
              sage: K
              Principal ideal (1) of Univariate Polynomial Ring in x
              over Rational Field
              sage: I.is_principal()
              True
              sage: K.is_principal()
              True
          """
          return True
  
      def gen(self):
          r"""
          Returns the generator of the principal ideal. The generators are
          elements of the ring containing the ideal.
  
          EXAMPLES:
  
          A simple example in the integers::
  
              sage: R = ZZ
              sage: I = R.ideal(7)
              sage: J = R.ideal(7, 14)
              sage: I.gen(); J.gen()
              7
              7
  
          Note that the generator belongs to the ring from which the ideal
          was initialized::
  
              sage: R.<x> = ZZ[]
              sage: I = R.ideal(x)
              sage: J = R.base_extend(QQ).ideal(2,x)
              sage: a = I.gen(); a
              x
              sage: b = J.gen(); b
              1
              sage: a.base_ring()
              Integer Ring
              sage: b.base_ring()
              Rational Field
          """
          return self.gens()[0]
  
      def __contains__(self, x):
          """
          Return ``True`` if ``x`` is in ``self``.
  
          EXAMPLES::
  
              sage: P.<x> = PolynomialRing(ZZ)
              sage: I = P.ideal(x^2-2)
              sage: x^2 in I
              False
              sage: x^2-2 in I
              True
              sage: x^2-3 in I
              False
          """
          if self.gen().is_zero():
              return x.is_zero()
          try:
              return self.gen().divides(x)
          except NotImplementedError:
              return self._contains_(self.ring()(x))
  
      def __hash__(self):
          r"""
          Very stupid constant hash function!
  
          TESTS::
  
              sage: P.<x, y> = PolynomialRing(ZZ)
              sage: I = P.ideal(x^2)
              sage: J = [x, y^2 + x*y]*P
              sage: hash(I)
              0
              sage: hash(J)
              0
          """
          return 0
  
      def _richcmp_(self, other, op):
          """
          Compare the two ideals.
  
          EXAMPLES:
  
          Comparison with non-principal ideal::
  
              sage: R.<x> = ZZ[]
              sage: I = R.ideal([x^3 + 4*x - 1, x + 6])
              sage: J = [x^2] * R
              sage: I > J  # indirect doctest
              True
              sage: J < I  # indirect doctest
              True
  
          Between two principal ideals::
  
              sage: P.<x> = PolynomialRing(ZZ)
              sage: I = P.ideal(x^2-2)
              sage: I2 = P.ideal(0)
              sage: I2.is_zero()
              True
              sage: I2 < I
              True
              sage: I3 = P.ideal(x)
              sage: I > I3
              True
          """
          if not isinstance(other, Ideal_generic):
              other = self.ring().ideal(other)
  
          try:
              if not other.is_principal():
                  return rich_to_bool(op, -1)
          except NotImplementedError:
              # If we do not know if the other is principal or not, then we
              #   fallback to the generic implementation
              return Ideal_generic._richcmp_(self, other, op)
  
          if self.is_zero():
              if not other.is_zero():
                  return rich_to_bool(op, -1)
              return rich_to_bool(op, 0)
  
          # is other.gen() / self.gen() a unit in the base ring?
          g0 = other.gen()
          g1 = self.gen()
          if g0.divides(g1) and g1.divides(g0):
              return rich_to_bool(op, 0)
          return rich_to_bool(op, 1)
  
      def divides(self, other):
          """
          Return ``True`` if ``self`` divides ``other``.
  
          EXAMPLES::
  
              sage: P.<x> = PolynomialRing(QQ)
              sage: I = P.ideal(x)
              sage: J = P.ideal(x^2)
              sage: I.divides(J)
              True
              sage: J.divides(I)
              False
          """
          if isinstance(other, Ideal_principal):
              return self.gen().divides(other.gen())
          raise NotImplementedError
  
  class Ideal_pid(Ideal_principal):
      """
      An ideal of a principal ideal domain.
  
      See :func:`Ideal()`.
      """
      def __init__(self, ring, gen):
          """
          Initialize ``self``.
  
          EXAMPLES::
  
              sage: I = 8*ZZ
              sage: I
              Principal ideal (8) of Integer Ring
          """
          Ideal_principal.__init__(self, ring, gen)
  
      def __add__(self, other):
          """
          Add the two ideals.
  
          EXAMPLES::
  
              sage: I = 8*ZZ
              sage: I2 = 3*ZZ
              sage: I + I2
              Principal ideal (1) of Integer Ring
          """
          if not isinstance(other, Ideal_generic):
              other = self.ring().ideal(other)
          return self.ring().ideal(self.gcd(other))
  
      def reduce(self, f):
          """
          Return the reduction of `f` modulo ``self``.
  
          EXAMPLES::
  
              sage: I = 8*ZZ
              sage: I.reduce(10)
              2
              sage: n = 10; n.mod(I)
              2
          """
          f = self.ring()(f)
          if self.gen() == 0:
              return f
          q, r = f.quo_rem(self.gen())
          return r
  
      def gcd(self, other):
          r"""
          Returns the greatest common divisor of the principal ideal with the
          ideal ``other``; that is, the largest principal ideal
          contained in both the ideal and ``other``
  
          .. TODO::
  
              This is not implemented in the case when ``other`` is neither
              principal nor when the generator of ``self`` is contained in
              ``other``. Also, it seems that this class is used only in PIDs--is
              this redundant?
  
          .. NOTE::
  
              The second example is broken.
  
          EXAMPLES:
  
          An example in the principal ideal domain `\ZZ`::
  
              sage: R = ZZ
              sage: I = R.ideal(42)
              sage: J = R.ideal(70)
              sage: I.gcd(J)
              Principal ideal (14) of Integer Ring
              sage: J.gcd(I)
              Principal ideal (14) of Integer Ring
  
          TESTS:
  
          We cannot take the gcd of a principal ideal with a
          non-principal ideal as well: ( ``gcd(I,J)`` should be `(7)` )
  
          ::
  
              sage: R.<x> = ZZ[]
              sage: I = ZZ.ideal(7)
              sage: J = R.ideal(7,x)
              sage: I.gcd(J)
              Traceback (most recent call last):
              ...
              NotImplementedError
              sage: J.gcd(I)
              Traceback (most recent call last):
              ...
              AttributeError: 'Ideal_generic' object has no attribute 'gcd'
  
          Note::
  
              sage: type(I)
              <class 'sage.rings.ideal.Ideal_pid'>
              sage: type(J)
              <class 'sage.rings.ideal.Ideal_generic'>
          """
          if isinstance(other, Ideal_principal):
              return self.ring().ideal(self.gen().gcd(other.gen()))
          elif self.gen() in other:
              return other
          else:
              raise NotImplementedError
  
      def is_prime(self):
          """
          Return ``True`` if the ideal is prime.
  
          This relies on the ring elements having a method ``is_irreducible()``
          implemented, since an ideal `(a)` is prime iff `a` is irreducible
          (or 0).
  
          EXAMPLES::
  
              sage: ZZ.ideal(2).is_prime()
              True
              sage: ZZ.ideal(-2).is_prime()
              True
              sage: ZZ.ideal(4).is_prime()
              False
              sage: ZZ.ideal(0).is_prime()
              True
              sage: R.<x> = QQ[]
              sage: P = R.ideal(x^2+1); P
              Principal ideal (x^2 + 1) of Univariate Polynomial Ring in x over Rational Field
              sage: P.is_prime()
              True
  
          In fields, only the zero ideal is prime::
  
              sage: RR.ideal(0).is_prime()
              True
              sage: RR.ideal(7).is_prime()
              False
          """
          if self.is_zero(): # PIDs are integral domains by definition
              return True
          g = self.gen()
          if g.is_one():     # The ideal (1) is never prime
              return False
          if hasattr(g, 'is_irreducible'):
              return g.is_irreducible()
  
          raise NotImplementedError
  
      def is_maximal(self):
          """
          Returns whether this ideal is maximal.
  
          Principal ideal domains have Krull dimension 1 (or 0), so an ideal is
          maximal if and only if it's prime (and nonzero if the ring is not a
          field).
  
          EXAMPLES::
  
              sage: R.<t> = GF(5)[]
              sage: p = R.ideal(t^2 + 2)
              sage: p.is_maximal()
              True
              sage: p = R.ideal(t^2 + 1)
              sage: p.is_maximal()
              False
              sage: p = R.ideal(0)
              sage: p.is_maximal()
              False
              sage: p = R.ideal(1)
              sage: p.is_maximal()
              False
          """
          if not self.ring().is_field() and self.is_zero():
              return False
          return self.is_prime()
  
      def residue_field(self):
          r"""
          Return the residue class field of this ideal, which must be prime.
  
          .. TODO::
  
              Implement this for more general rings. Currently only defined
              for `\ZZ` and for number field orders.
  
          EXAMPLES::
  
              sage: P = ZZ.ideal(61); P
              Principal ideal (61) of Integer Ring
              sage: F = P.residue_field(); F
              Residue field of Integers modulo 61
              sage: pi = F.reduction_map(); pi
              Partially defined reduction map:
                From: Rational Field
                To:   Residue field of Integers modulo 61
              sage: pi(123/234)
              6
              sage: pi(1/61)
              Traceback (most recent call last):
              ...
              ZeroDivisionError: Cannot reduce rational 1/61 modulo 61: it has negative valuation
              sage: lift = F.lift_map(); lift
              Lifting map:
                From: Residue field of Integers modulo 61
                To:   Integer Ring
              sage: lift(F(12345/67890))
              33
              sage: (12345/67890) % 61
              33
  
          TESTS::
  
              sage: ZZ.ideal(96).residue_field()
              Traceback (most recent call last):
              ...
              ValueError: The ideal (Principal ideal (96) of Integer Ring) is not prime
  
          ::
  
              sage: R.<x>=QQ[]
              sage: I=R.ideal(x^2+1)
              sage: I.is_prime()
              True
              sage: I.residue_field()
              Traceback (most recent call last):
              ...
              TypeError: residue fields only supported for polynomial rings over finite fields.
          """
          if not self.is_prime():
              raise ValueError("The ideal (%s) is not prime"%self)
          from sage.rings.integer_ring import ZZ
          if self.ring() is ZZ:
              return ZZ.residue_field(self, check = False)
          raise NotImplementedError("residue_field() is only implemented for ZZ and rings of integers of number fields.")
  
  class Ideal_fractional(Ideal_generic):
      """
      Fractional ideal of a ring.
  
      See :func:`Ideal()`.
      """
      def __repr__(self):
          """
          Return a string representation of ``self``.
  
          EXAMPLES::
  
              sage: from sage.rings.ideal import Ideal_fractional
              sage: K.<a> = NumberField(x^2 + 1)
              sage: Ideal_fractional(K, [a]) # indirect doctest
              Fractional ideal (a) of Number Field in a with defining polynomial x^2 + 1
          """
          return "Fractional ideal %s of %s"%(self._repr_short(), self.ring())
  
  # constructors for standard (benchmark) ideals, written uppercase as
  # these are constructors
  
  def Cyclic(R, n=None, homog=False, singular=None):
      """
      Ideal of cyclic ``n``-roots from 1-st ``n`` variables of ``R`` if ``R`` is
      coercible to :class:`Singular <sage.interfaces.singular.Singular>`.
  
      INPUT:
  
      -  ``R`` -- base ring to construct ideal for
  
      -  ``n`` -- number of cyclic roots (default: ``None``). If ``None``, then
         ``n`` is set to ``R.ngens()``.
  
      -  ``homog`` -- (default: ``False``) if ``True`` a homogeneous ideal is
         returned using the last variable in the ideal
  
      -  ``singular`` -- singular instance to use
  
      .. NOTE::
  
         ``R`` will be set as the active ring in
         :class:`Singular <sage.interfaces.singular.Singular>`
  
      EXAMPLES:
  
      An example from a multivariate polynomial ring over the
      rationals::
  
          sage: P.<x,y,z> = PolynomialRing(QQ,3,order='lex')
          sage: I = sage.rings.ideal.Cyclic(P)
          sage: I
          Ideal (x + y + z, x*y + x*z + y*z, x*y*z - 1) of Multivariate Polynomial
          Ring in x, y, z over Rational Field
          sage: I.groebner_basis()
          [x + y + z, y^2 + y*z + z^2, z^3 - 1]
  
      We compute a Groebner basis for cyclic 6, which is a standard
      benchmark and test ideal::
  
          sage: R.<x,y,z,t,u,v> = QQ['x,y,z,t,u,v']
          sage: I = sage.rings.ideal.Cyclic(R,6)
          sage: B = I.groebner_basis()
          sage: len(B)
          45
      """
      from .rational_field import RationalField
  
      if n:
          if n > R.ngens():
              raise ArithmeticError("n must be <= R.ngens()")
      else:
          n = R.ngens()
  
      if singular is None:
          from sage.interfaces.singular import singular as singular_default
          singular = singular_default
  
      singular.lib("polylib")
      R2 = R.change_ring(RationalField())
      R2._singular_().set_ring()
  
      if not homog:
          I = singular.cyclic(n)
      else:
          I = singular.cyclic(n).homog(R2.gen(n-1))
      return R2.ideal(I).change_ring(R)
  
  def Katsura(R, n=None, homog=False, singular=None):
      """
      ``n``-th katsura ideal of ``R`` if ``R`` is coercible to
      :class:`Singular <sage.interfaces.singular.Singular>`.
  
      INPUT:
  
      - ``R`` -- base ring to construct ideal for
  
      - ``n`` -- (default: ``None``) which katsura ideal of ``R``. If ``None``,
        then ``n`` is set to ``R.ngens()``.
  
      -  ``homog`` -- if ``True`` a homogeneous ideal is returned
         using the last variable in the ideal (default: ``False``)
  
      -  ``singular`` -- singular instance to use
  
  
      EXAMPLES::
  
          sage: P.<x,y,z> = PolynomialRing(QQ,3)
          sage: I = sage.rings.ideal.Katsura(P,3); I
          Ideal (x + 2*y + 2*z - 1, x^2 + 2*y^2 + 2*z^2 - x, 2*x*y + 2*y*z - y)
          of Multivariate Polynomial Ring in x, y, z over Rational Field
  
      ::
  
          sage: Q.<x> = PolynomialRing(QQ, implementation="singular")
          sage: J = sage.rings.ideal.Katsura(Q,1); J
          Ideal (x - 1) of Multivariate Polynomial Ring in x over Rational Field
      """
      from .rational_field import RationalField
      if n:
          if n > R.ngens():
              raise ArithmeticError("n must be <= R.ngens().")
      else:
          n = R.ngens()
  
      if singular is None:
          from sage.interfaces.singular import singular as singular_default
          singular = singular_default
      singular.lib("polylib")
      R2 = R.change_ring(RationalField())
      R2._singular_().set_ring()
  
      if not homog:
          I = singular.katsura(n)
      else:
          I = singular.katsura(n).homog(R2.gen(n-1))
      return R2.ideal(I).change_ring(R)
  
  def FieldIdeal(R):
      r"""
      Let ``q = R.base_ring().order()`` and `(x_0,...,x_n)` ``= R.gens()`` then
      if `q` is finite this constructor returns
  
      .. MATH::
  
          \langle x_0^q - x_0, ... , x_n^q - x_n \rangle.
  
      We call this ideal the field ideal and the generators the field
      equations.
  
      EXAMPLES:
  
      The field ideal generated from the polynomial ring over
      two variables in the finite field of size 2::
  
          sage: P.<x,y> = PolynomialRing(GF(2),2)
          sage: I = sage.rings.ideal.FieldIdeal(P); I
          Ideal (x^2 + x, y^2 + y) of Multivariate Polynomial Ring in x, y over
          Finite Field of size 2
  
      Another, similar example::
  
          sage: Q.<x1,x2,x3,x4> = PolynomialRing(GF(2^4,name='alpha'), 4)
          sage: J = sage.rings.ideal.FieldIdeal(Q); J
          Ideal (x1^16 + x1, x2^16 + x2, x3^16 + x3, x4^16 + x4) of
          Multivariate Polynomial Ring in x1, x2, x3, x4 over Finite
          Field in alpha of size 2^4
      """
  
      q = R.base_ring().order()
  
      import sage.rings.infinity
      if q is sage.rings.infinity.infinity:
          raise TypeError("Cannot construct field ideal for R.base_ring().order()==infinity")
  
      return R.ideal([x**q - x for x in R.gens() ])
  