ideal.py

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 <[email protected]>
#
#  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.misc.latex as latex
import sage.rings.ring
import commutative_ring
from sage.structure.element import MonoidElement
from sage.interfaces.singular import singular as singular_default
import sage.rings.infinity
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 = PolynomialRing(ZZ, 'x').objgen()
        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 = PolynomialRing(ZZ, 'x').objgen()
        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]

    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()
    else:
        R = first
        gens = args[1:]

    if not commutative_ring.is_CommutativeRing(R):
        raise TypeError, "R must be a commutative ring"

    return R.ideal(*gens, **kwds)

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 = PolynomialRing(ZZ, 'x').objgen()
            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
        """
        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_element(),)
        self.__gens = gens
        MonoidElement.__init__(self, ring.ideal_monoid())

    def _repr_short(self):
        """
        Represent the list of generators.

        EXAMPLE::

            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 __cmp__(self, other):
        """
        Compares the generators of two ideals.

        INPUT:

        - ``other`` -- an ideal

        OUTPUT:

        - 0 if ``self`` and ``other`` have the same generators, 1 otherwise.

        EXAMPLE::

            sage: R = ZZ; I = ZZ*2; J = ZZ*(-2)
            sage: cmp(I,J)
            0
        """
        S = set(self.gens())
        T = set(other.gens())
        if S == T:
            return 0
        return cmp(self.gens(), other.gens())

    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 __nonzero__(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):
        """
        Return a latex representation of ``self``.

        EXAMPLES::

            sage: latex(3*ZZ) # indirect doctest
            \left(3\right)\Bold{Z}
        """
        return '\\left(%s\\right)%s'%(", ".join([latex.latex(g) for g in \
                                                 self.gens()]),
                                      latex.latex(self.ring()))

    def ring(self):
        """
        Returns 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.

        EXAMPLE::

            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.

        EXAMPLE::

            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.

        EXAMPLE::

            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.all 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 [AtiMac]_).  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.

        REFERENCES:

        .. [AtiMac] Atiyah and Macdonald, "Introduction to commutative
           algebra", Addison-Wesley, 1969.

        """
        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 = ZZ[x]
            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.all 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:
                i = 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
        """
        if self.is_zero():
            return True
        # If self is principal, can give a complete answer
        if self.is_principal():
            return self.gens()[0].is_unit()
        # If self is not principal, can only give an affirmative answer
        for g in self.gens():
            if g.is_unit():
                return True
        raise NotImplementedError

    def category(self):
        """
        Return the category of this ideal.

        .. NOTE::

            category is dependent on the ring of the ideal.

        EXAMPLES::

            sage: I = ZZ.ideal(7)
            sage: J = ZZ[x].ideal(7,x)
            sage: K = ZZ[x].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__`.

        EXAMPLE::

            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``.

        EXAMPLE::

            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

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 = ZZ[x]
            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 = ZZ[x]
            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 = ZZ[x]
            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()
        return self.gen().divides(x)

    def __cmp__(self, other):
        """
        Compare the two ideals.

        EXAMPLE:

        Comparision with non-principal ideal::

            sage: P.<x, y> = PolynomialRing(ZZ)
            sage: I = P.ideal(x^2)
            sage: J = [x, y^2 + x*y]*P
            sage: cmp(I, J) # indirect doctest
            1

        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: cmp(I2, I)
            -1
            sage: I3 = P.ideal(x)
            sage: cmp(I, I3)
            1
        """
        if not isinstance(other, Ideal_generic):
            other = self.ring().ideal(other)

        if not other.is_principal():
            return -1

        if self.is_zero():
            if not other.is_zero():
                return -1
            return 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 0
        return 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: I = ZZ.ideal(7)
            sage: J = ZZ[x].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
        """
        if self.is_zero(): # PIDs are integral domains by definition
            return True
        g = self.gen()
        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=singular_default):
    """
    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()

    singular.lib("poly")
    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=singular_default):
    """
    ``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,1)
        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()
    singular.lib("poly")
    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()

    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() ])