text: """
  Orders in Number Fields
  
  AUTHORS:
  
  - William Stein and Robert Bradshaw (2007-09): initial version
  
  EXAMPLES:
  
  We define an absolute order::
  
      sage: K.<a> = NumberField(x^2 + 1); O = K.order(2*a)
      sage: O.basis()
      [1, 2*a]
  
  We compute a basis for an order in a relative extension
  that is generated by 2 elements::
  
      sage: K.<a,b> = NumberField([x^2 + 1, x^2 - 3]); O = K.order([3*a,2*b])
      sage: O.basis()
      [1, 3*a - 2*b, -6*b*a + 6, 3*a]
  
  We compute a maximal order of a degree 10 field::
  
      sage: K.<a> = NumberField((x+1)^10 + 17)
      sage: K.maximal_order()
      Maximal Order in Number Field in a with defining polynomial x^10 + 10*x^9 + 45*x^8 + 120*x^7 + 210*x^6 + 252*x^5 + 210*x^4 + 120*x^3 + 45*x^2 + 10*x + 18
  
  We compute a suborder, which has index a power of 17 in the maximal order::
  
      sage: O = K.order(17*a); O
      Order in Number Field in a with defining polynomial x^10 + 10*x^9 + 45*x^8 + 120*x^7 + 210*x^6 + 252*x^5 + 210*x^4 + 120*x^3 + 45*x^2 + 10*x + 18
      sage: m = O.index_in(K.maximal_order()); m
      23453165165327788911665591944416226304630809183732482257
      sage: factor(m)
      17^45
  """
  # ****************************************************************************
  # This program is free software: you can redistribute it and/or modify
  # it under the terms of the GNU General Public License as published by
  # the Free Software Foundation, either version 2 of the License, or
  # (at your option) any later version.
  #                  http://www.gnu.org/licenses/
  # ****************************************************************************
  from __future__ import absolute_import
  
  import six
  
  from sage.misc.cachefunc import cached_method
  from sage.rings.ring import IntegralDomain
  from sage.structure.sequence import Sequence
  from sage.rings.integer_ring import ZZ
  from sage.structure.element import is_Element
  
  from .number_field_element import OrderElement_absolute, OrderElement_relative
  
  from .number_field_element_quadratic import OrderElement_quadratic
  
  from sage.rings.monomials import monomials
  
  from sage.libs.pari.all import pari
  
  
  def is_NumberFieldOrder(R):
      r"""
      Return True if R is either an order in a number field or is the ring `\ZZ` of integers.
  
      EXAMPLES::
  
          sage: from sage.rings.number_field.order import is_NumberFieldOrder
          sage: is_NumberFieldOrder(NumberField(x^2+1,'a').maximal_order())
          True
          sage: is_NumberFieldOrder(ZZ)
          True
          sage: is_NumberFieldOrder(QQ)
          False
          sage: is_NumberFieldOrder(45)
          False
      """
      return isinstance(R, Order) or R == ZZ
  
  
  def EquationOrder(f, names, **kwds):
      r"""
      Return the equation order generated by a root of the irreducible
      polynomial f or list of polynomials `f` (to construct a relative
      equation order).
  
      IMPORTANT: Note that the generators of the returned order need
      *not* be roots of `f`, since the generators of an order are -- in
      Sage -- module generators.
  
      EXAMPLES::
  
          sage: O.<a,b> = EquationOrder([x^2+1, x^2+2])
          sage: O
          Relative Order in Number Field in a with defining polynomial x^2 + 1 over its base field
          sage: O.0
          -b*a - 1
          sage: O.1
          -3*a + 2*b
  
      Of course the input polynomial must be integral::
  
          sage: R = EquationOrder(x^3 + x + 1/3, 'alpha'); R
          Traceback (most recent call last):
          ...
          ValueError: each generator must be integral
  
          sage: R = EquationOrder( [x^3 + x + 1, x^2 + 1/2], 'alpha'); R
          Traceback (most recent call last):
          ...
          ValueError: each generator must be integral
      """
      from .number_field import NumberField
      R = ZZ['x']
      if isinstance(f, (list, tuple)):
          for g in f:
              try:
                  R(g)
              except TypeError:
                  raise ValueError('each generator must be integral')
      else:
          try:
              R(f)
          except TypeError:
              raise ValueError('each generator must be integral')
  
      K = NumberField(f, names=names, **kwds)
      return K.order(K.gens())
  
  
  class Order(IntegralDomain):
      r"""
      An order in a number field.
  
      An order is a subring of the number field that has `\ZZ`-rank equal
      to the degree of the number field over `\QQ`.
  
      EXAMPLES::
  
          sage: K.<theta> = NumberField(x^4 + x + 17)
          sage: K.maximal_order()
          Maximal Order in Number Field in theta with defining polynomial x^4 + x + 17
          sage: R = K.order(17*theta); R
          Order in Number Field in theta with defining polynomial x^4 + x + 17
          sage: R.basis()
          [1, 17*theta, 289*theta^2, 4913*theta^3]
          sage: R = K.order(17*theta, 13*theta); R
          Order in Number Field in theta with defining polynomial x^4 + x + 17
          sage: R.basis()
          [1, theta, theta^2, theta^3]
          sage: R = K.order([34*theta, 17*theta + 17]); R
          Order in Number Field in theta with defining polynomial x^4 + x + 17
  
          sage: K.<b> = NumberField(x^4 + x^2 + 2)
          sage: (b^2).charpoly().factor()
          (x^2 + x + 2)^2
          sage: K.order(b^2)
          Traceback (most recent call last):
          ...
          ValueError: the rank of the span of gens is wrong
      """
      def __init__(self, K, is_maximal):
          """
          This is called when creating an order to set the ambient field.
  
          EXAMPLES::
  
              sage: k = CyclotomicField(5)
              sage: k.maximal_order()
              Maximal Order in Cyclotomic Field of order 5 and degree 4
  
          TESTS::
  
              sage: k.<alg> = NumberField(x^7+3*x+1, embedding=CC(0,1))
              sage: O = k.order(alg)
              sage: ordelt = O(alg)
              sage: CC(ordelt)
              0.0535229072603327 + 1.20934552493846*I
          """
          self._K = K
          self._is_maximal = is_maximal
          IntegralDomain.__init__(self, ZZ, names = K.variable_names(), normalize = False)
          self._populate_coercion_lists_(embedding=self.number_field())
  
      def fractional_ideal(self, *args, **kwds):
          """
          Return the fractional ideal of the maximal order with given
          generators.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^2 + 2)
              sage: R = K.maximal_order()
              sage: R.fractional_ideal(2/3 + 7*a, a)
              Fractional ideal (1/3*a)
          """
          return self.number_field().fractional_ideal(*args, **kwds)
  
      def ideal(self, *args, **kwds):
          """
          Return the integral ideal with given generators.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^2 + 7)
              sage: R = K.maximal_order()
              sage: R.ideal(2/3 + 7*a, a)
              Traceback (most recent call last):
              ...
              ValueError: ideal must be integral; use fractional_ideal to create a non-integral ideal.
              sage: R.ideal(7*a, 77 + 28*a)
              Fractional ideal (7)
              sage: R = K.order(4*a)
              sage: R.ideal(8)
              Traceback (most recent call last):
              ...
              NotImplementedError: ideals of non-maximal orders not yet supported.
  
          This function is called implicitly below::
  
              sage: R = EquationOrder(x^2 + 2, 'a'); R
              Order in Number Field in a with defining polynomial x^2 + 2
              sage: (3,15)*R
              Fractional ideal (3)
  
          The zero ideal is handled properly::
  
              sage: R.ideal(0)
              Ideal (0) of Number Field in a with defining polynomial x^2 + 2
          """
          if not self.is_maximal():
              raise NotImplementedError("ideals of non-maximal orders not yet supported.")
          I = self.number_field().ideal(*args, **kwds)
          if not I.is_integral():
              raise ValueError("ideal must be integral; use fractional_ideal to create a non-integral ideal.")
          return I
  
      def _coerce_map_from_(self, R):
          """
          Orders currently only have coerce maps from the integers.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 5077)
              sage: Ok = k.maximal_order()
              sage: Ok.has_coerce_map_from(k) #indirect doctest
              False
              sage: Ok.has_coerce_map_from(ZZ)
              True
          """
          return R is ZZ or R in six.integer_types
  
      def __mul__(self, right):
          """
          Create an ideal in this order using the notation ``Ok*gens``
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 5077); G = k.class_group(); G
              Class group of order 22 with structure C22 of Number Field in a with defining polynomial x^2 + 5077
              sage: G.0 ^ -9
              Fractional ideal class (11, a + 7)
              sage: Ok = k.maximal_order(); Ok
              Maximal Order in Number Field in a with defining polynomial x^2 + 5077
              sage: Ok * (11, a + 7)
              Fractional ideal (11, a + 7)
              sage: (11, a + 7) * Ok
              Fractional ideal (11, a + 7)
          """
          if self.is_maximal():
              return self._K.ideal(right)
          raise TypeError
  
      def __rmul__(self, left):
          """
          Create an ideal in this order using the notation ``gens*Ok``.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 431); G = k.class_group(); G
              Class group of order 21 with structure C21 of Number Field in a with defining polynomial x^2 + 431
              sage: G.0   # random output
              Fractional ideal class (6, 1/2*a + 11/2)
              sage: Ok = k.maximal_order(); Ok
              Maximal Order in Number Field in a with defining polynomial x^2 + 431
              sage: (6, 1/2*a + 11/2)*Ok    # random output
              Fractional ideal (6, 1/2*a + 11/2)
              sage: 17*Ok
              Fractional ideal (17)
          """
          return self * left
  
      def is_maximal(self):
          """
          Return ``True`` if this is the maximal order.
  
          EXAMPLES::
  
              sage: k.<i> = NumberField(x^2 + 1)
              sage: O3 = k.order(3*i); O5 = k.order(5*i); Ok = k.maximal_order(); Osum = O3 + O5
              sage: Osum.is_maximal()
              True
              sage: O3.is_maximal()
              False
              sage: O5.is_maximal()
              False
              sage: Ok.is_maximal()
              True
  
           An example involving a relative order::
  
              sage: K.<a,b> = NumberField([x^2 + 1, x^2 - 3]); O = K.order([3*a,2*b]); O
              Relative Order in Number Field in a with defining polynomial x^2 + 1 over its base field
              sage: O.is_maximal()
              False
  
          """
          if self._is_maximal is None:
              self._is_maximal = (self.absolute_discriminant() == self._K.absolute_discriminant())
          return self._is_maximal
  
      def is_field(self, proof = True):
          r"""
          Return ``False`` (because an order is never a field).
  
          EXAMPLES::
  
              sage: L.<alpha> = NumberField(x**4 - x**2 + 7)
              sage: O = L.maximal_order() ; O.is_field()
              False
              sage: CyclotomicField(12).ring_of_integers().is_field()
              False
          """
          return False
  
      def is_noetherian(self):
          r"""
          Return ``True`` (because orders are always Noetherian)
  
          EXAMPLES::
  
              sage: L.<alpha> = NumberField(x**4 - x**2 + 7)
              sage: O = L.maximal_order() ; O.is_noetherian()
              True
              sage: E.<w> = NumberField(x^2 - x + 2)
              sage: OE = E.ring_of_integers(); OE.is_noetherian()
              True
          """
          return True
  
      def is_integrally_closed(self):
          """
          Return ``True`` if this ring is integrally closed, i.e., is equal
          to the maximal order.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^2 + 189*x + 394)
              sage: R = K.order(2*a)
              sage: R.is_integrally_closed()
              False
              sage: R
              Order in Number Field in a with defining polynomial x^2 + 189*x + 394
              sage: S = K.maximal_order(); S
              Maximal Order in Number Field in a with defining polynomial x^2 + 189*x + 394
              sage: S.is_integrally_closed()
              True
          """
          return self.is_maximal()
  
      def krull_dimension(self):
          """
          Return the Krull dimension of this order, which is 1.
  
          EXAMPLES::
  
              sage: K.<a> = QuadraticField(5)
              sage: OK = K.maximal_order()
              sage: OK.krull_dimension()
              1
              sage: O2 = K.order(2*a)
              sage: O2.krull_dimension()
              1
          """
          return ZZ(1)
  
      def integral_closure(self):
          """
          Return the integral closure of this order.
  
          EXAMPLES::
  
              sage: K.<a> = QuadraticField(5)
              sage: O2 = K.order(2*a); O2
              Order in Number Field in a with defining polynomial x^2 - 5
              sage: O2.integral_closure()
              Maximal Order in Number Field in a with defining polynomial x^2 - 5
              sage: OK = K.maximal_order()
              sage: OK is OK.integral_closure()
              True
          """
          if self.is_maximal():
              return self
          else:
              return self.number_field().maximal_order()
  
      def gen(self, i):
          r"""
          Return `i`'th module generator of this order.
  
          EXAMPLES::
  
              sage: K.<c> = NumberField(x^3 + 2*x + 17)
              sage: O = K.maximal_order(); O
              Maximal Order in Number Field in c with defining polynomial x^3 + 2*x + 17
              sage: O.basis()
              [1, c, c^2]
              sage: O.gen(1)
              c
              sage: O.gen(2)
              c^2
              sage: O.gen(5)
              Traceback (most recent call last):
              ...
              IndexError: no 5th generator
              sage: O.gen(-1)
              Traceback (most recent call last):
              ...
              IndexError: no -1th generator
          """
          b = self.basis()
          if i < 0 or i >= len(b):
              raise IndexError("no %sth generator" % i)
          return self.basis()[i]
  
      def ngens(self):
          """
          Return the number of module generators of this order.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8)
              sage: O = K.maximal_order()
              sage: O.ngens()
              3
          """
          return self.absolute_degree()
  
      def basis(self):  # this must be defined in derived class
          r"""
          Return a basis over `\ZZ` of this order.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^3 + x^2 - 16*x + 16)
              sage: O = K.maximal_order(); O
              Maximal Order in Number Field in a with defining polynomial x^3 + x^2 - 16*x + 16
              sage: O.basis()
              [1, 1/4*a^2 + 1/4*a, a^2]
          """
          raise NotImplementedError
  
      def coordinates(self, x):
          r"""
          Return the coordinate vector of `x` with respect to this order.
  
          INPUT:
  
          - ``x`` -- an element of the number field of this order.
  
          OUTPUT:
  
          A vector of length `n` (the degree of the field) giving
          the coordinates of `x` with respect to the integral basis
          of the order.  In general this will be a vector of
          rationals; it will consist of integers if and only if `x`
          is in the order.
  
          AUTHOR: John Cremona  2008-11-15
  
          ALGORITHM:
  
          Uses linear algebra.  The change-of-basis matrix is
          cached.  Provides simpler implementations for
          ``_contains_()``, ``is_integral()`` and ``smallest_integer()``.
  
          EXAMPLES::
  
              sage: K.<i> = QuadraticField(-1)
              sage: OK = K.ring_of_integers()
              sage: OK_basis = OK.basis(); OK_basis
              [1, i]
              sage: a = 23-14*i
              sage: acoords = OK.coordinates(a); acoords
              (23, -14)
              sage: sum([OK_basis[j]*acoords[j] for j in range(2)]) == a
              True
              sage: OK.coordinates((120+340*i)/8)
              (15, 85/2)
  
              sage: O = K.order(3*i)
              sage: O.is_maximal()
              False
              sage: O.index_in(OK)
              3
              sage: acoords = O.coordinates(a); acoords
              (23, -14/3)
              sage: sum([O.basis()[j]*acoords[j] for j in range(2)]) == a
              True
  
         """
          K = self.number_field()
          V, from_V, to_V = K.absolute_vector_space()
  
          try:
              M = self.__basis_matrix_inverse
          except AttributeError:
              from sage.matrix.constructor import Matrix
              self.__basis_matrix_inverse = Matrix([to_V(b) for b in self.basis()]).inverse()
              M = self.__basis_matrix_inverse
          return to_V(K(x))*M
  
      def free_module(self):
          r"""
          Return the free `\ZZ`-module contained in the vector space
          associated to the ambient number field, that corresponds
          to this ideal.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8)
              sage: O = K.maximal_order(); O.basis()
              [1, 1/2*a^2 + 1/2*a, a^2]
              sage: O.free_module()
              Free module of degree 3 and rank 3 over Integer Ring
              User basis matrix:
              [  1   0   0]
              [  0 1/2 1/2]
              [  0   0   1]
  
          An example in a relative extension.  Notice that the module is
          a `\ZZ`-module in the absolute_field associated to the relative
          field::
  
              sage: K.<a,b> = NumberField([x^2 + 1, x^2 + 2])
              sage: O = K.maximal_order(); O.basis()
              [(-3/2*b - 5)*a + 7/2*b - 2, -3*a + 2*b, -2*b*a - 3, -7*a + 5*b]
              sage: O.free_module()
              Free module of degree 4 and rank 4 over Integer Ring
              User basis matrix:
              [1/4 1/4 3/4 3/4]
              [  0 1/2   0 1/2]
              [  0   0   1   0]
              [  0   0   0   1]
          """
          try:
              return self.__free_module
          except AttributeError:
              pass
          from .number_field_ideal import basis_to_module
          M = basis_to_module(self.basis(), self.number_field())
          self.__free_module = M
          return M
  
      @cached_method
      def ring_generators(self):
          """
          Return generators for self as a ring.
  
          EXAMPLES::
  
              sage: K.<i> = NumberField(x^2 + 1)
              sage: O = K.maximal_order(); O
              Gaussian Integers in Number Field in i with defining polynomial x^2 + 1
              sage: O.ring_generators()
              [i]
  
          This is an example where 2 generators are required (because 2 is an essential
          discriminant divisor).::
  
              sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8)
              sage: O = K.maximal_order(); O.basis()
              [1, 1/2*a^2 + 1/2*a, a^2]
              sage: O.ring_generators()
              [1/2*a^2 + 1/2*a, a^2]
  
          An example in a relative number field::
  
              sage: K.<a, b> = NumberField([x^2 + x + 1, x^3 - 3])
              sage: O = K.maximal_order()
              sage: O.ring_generators()
              [(-5/3*b^2 + 3*b - 2)*a - 7/3*b^2 + b + 3, (-5*b^2 - 9)*a - 5*b^2 - b, (-6*b^2 - 11)*a - 6*b^2 - b]
          """
          K = self._K
          n = []
          V, from_V, to_V = self._K.absolute_vector_space()
          A = ZZ**K.absolute_degree()
          remaining = [x for x in self.basis() if x != 1]
          gens = []
          while remaining:
              g = remaining.pop(0)
              gens.append(g)
              n.append(g.absolute_minpoly().degree())
              W = A.span([to_V(x) for x in monomials(gens, n)])
              remaining = [x for x in remaining if not to_V(x) in W]
          return Sequence(gens,immutable=True)
  
      @cached_method
      def _defining_names(self):
          """
          Return the generators of the ambient number field, but with
          this order as parent.
  
          EXAMPLES::
  
              sage: B.<z> = EquationOrder(x^2 + 3)
              sage: B._defining_names()
              (z,)
  
          For relative extensions::
  
              sage: O.<a,b> = EquationOrder([x^2 + 1, x^2 + 2])
              sage: O._defining_names()
              (a, b)
          """
          gens = self.number_field().gens()
          return tuple(self(g) for g in gens)
  
      def zeta(self, n=2, all=False):
          r"""
          Return a primitive n-th root of unity in this order, if it
          contains one. If all is True, return all of them.
  
          EXAMPLES::
  
              sage: F.<alpha> = NumberField(x**2+3)
              sage: F.ring_of_integers().zeta(6)
              1/2*alpha + 1/2
              sage: O = F.order([3*alpha])
              sage: O.zeta(3)
              Traceback (most recent call last):
              ...
              ArithmeticError: There are no 3rd roots of unity in self.
          """
          roots_in_field = self.number_field().zeta(n, True)
          roots_in_self = [ self(x) for x in roots_in_field if x in self ]
          if len(roots_in_self) == 0:
              if all:
                  return []
              else:
                  raise ArithmeticError("There are no %s roots of unity in self."%n.ordinal_str())
          if all:
              return roots_in_self
          else:
              return roots_in_self[0]
  
  
      def number_field(self):
          """
          Return the number field of this order, which is the ambient
          number field that this order is embedded in.
  
          EXAMPLES::
  
              sage: K.<b> = NumberField(x^4 + x^2 + 2)
              sage: O = K.order(2*b); O
              Order in Number Field in b with defining polynomial x^4 + x^2 + 2
              sage: O.basis()
              [1, 2*b, 4*b^2, 8*b^3]
              sage: O.number_field()
              Number Field in b with defining polynomial x^4 + x^2 + 2
              sage: O.number_field() is K
              True
          """
          return self._K
  
      def ambient(self):
          r"""
          Return the ambient number field that contains self.
  
          This is the same as ``self.number_field()`` and
          ``self.fraction_field()``
  
          EXAMPLES::
  
              sage: k.<z> = NumberField(x^2 - 389)
              sage: o = k.order(389*z + 1)
              sage: o
              Order in Number Field in z with defining polynomial x^2 - 389
              sage: o.basis()
              [1, 389*z]
              sage: o.ambient()
              Number Field in z with defining polynomial x^2 - 389
          """
          return self._K
  
      def residue_field(self, prime, names=None, check=False):
          """
          Return the residue field of this order at a given prime, ie `O/pO`.
  
          INPUT:
  
          - ``prime`` -- a prime ideal of the maximal order in this number field.
          - ``names`` -- the name of the variable in the residue field
          - ``check`` -- whether or not to check the primality of prime.
  
          OUTPUT:
  
          The residue field at this prime.
  
          EXAMPLES::
  
              sage: R.<x> = QQ[]
              sage: K.<a> = NumberField(x^4+3*x^2-17)
              sage: P = K.ideal(61).factor()[0][0]
              sage: OK = K.maximal_order()
              sage: OK.residue_field(P)
              Residue field in abar of Fractional ideal (61, a^2 + 30)
              sage: Fp.<b> = OK.residue_field(P)
              sage: Fp
              Residue field in b of Fractional ideal (61, a^2 + 30)
          """
          if self.is_maximal():
              return self.number_field().residue_field(prime, names, check)
  
          raise NotImplementedError("Residue fields of non-maximal orders "
                                    "are not yet supported.")
  
      def fraction_field(self):
          """
          Return the fraction field of this order, which is the
          ambient number field.
  
          EXAMPLES::
  
              sage: K.<b> = NumberField(x^4 + 17*x^2 + 17)
              sage: O = K.order(17*b); O
              Order in Number Field in b with defining polynomial x^4 + 17*x^2 + 17
              sage: O.fraction_field()
              Number Field in b with defining polynomial x^4 + 17*x^2 + 17
          """
          return self._K
  
      def degree(self):
          r"""
          Return the degree of this order, which is the rank of this order as a
          `\ZZ`-module.
  
          EXAMPLES::
  
              sage: k.<c> = NumberField(x^3 + x^2 - 2*x+8)
              sage: o = k.maximal_order()
              sage: o.degree()
              3
              sage: o.rank()
              3
          """
          return self._K.degree()
  
      def rank(self):
          r"""
          Return the rank of this order, which is the rank of the underlying
          `\ZZ`-module, or the degree of the ambient number field that contains
          this order.
  
          This is a synonym for ``degree()``.
  
          EXAMPLES::
  
              sage: k.<c> = NumberField(x^5 + x^2 + 1)
              sage: o = k.maximal_order(); o
              Maximal Order in Number Field in c with defining polynomial x^5 + x^2 + 1
              sage: o.rank()
              5
          """
          return self.degree()
  
      def class_number(self, proof=None):
          r"""
          Return the class number of this order.
  
          EXAMPLES::
  
              sage: ZZ[2^(1/3)].class_number()
              1
              sage: QQ[sqrt(-23)].maximal_order().class_number()
              3
              sage: ZZ[120*sqrt(-23)].class_number()
              288
  
          Note that non-maximal orders are only supported in quadratic fields::
  
              sage: ZZ[120*sqrt(-23)].class_number()
              288
              sage: ZZ[100*sqrt(3)].class_number()
              4
              sage: ZZ[11*2^(1/3)].class_number()
              Traceback (most recent call last):
              ...
              NotImplementedError: computation of class numbers of non-maximal orders not in quadratic fields is not implemented
  
          """
          if not self.is_maximal():
              K = self.number_field()
              if K.degree() != 2:
                  raise NotImplementedError("computation of class numbers of non-maximal orders not in quadratic fields is not implemented")
              return ZZ(pari.qfbclassno(self.discriminant()))
          return self.number_field().class_number(proof=proof)
  
      def class_group(self, proof=None, names='c'):
          r"""
          Return the class group of this order.
  
          (Currently only implemented for the maximal order.)
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 5077)
              sage: O = k.maximal_order(); O
              Maximal Order in Number Field in a with defining polynomial x^2 + 5077
              sage: O.class_group()
              Class group of order 22 with structure C22 of Number Field in a with defining polynomial x^2 + 5077
          """
          if self.is_maximal():
              return self.number_field().class_group(proof=proof, names=names)
          else:
              raise NotImplementedError
  
      def is_suborder(self, other):
          """
          Return True if self and other are both orders in the
          same ambient number field and self is a subset of other.
  
          EXAMPLES::
  
              sage: W.<i> = NumberField(x^2 + 1)
              sage: O5 = W.order(5*i)
              sage: O10 = W.order(10*i)
              sage: O15 = W.order(15*i)
              sage: O15.is_suborder(O5)
              True
              sage: O5.is_suborder(O15)
              False
              sage: O10.is_suborder(O15)
              False
  
          We create another isomorphic but different field::
  
              sage: W2.<j> = NumberField(x^2 + 1)
              sage: P5 = W2.order(5*j)
  
          This is False because the ambient number fields are not equal.::
  
              sage: O5.is_suborder(P5)
              False
  
          We create a field that contains (in no natural way!) W,
          and of course again is_suborder returns False::
  
              sage: K.<z> = NumberField(x^4 + 1)
              sage: M = K.order(5*z)
              sage: O5.is_suborder(M)
              False
          """
          if not isinstance(other, Order):
              return False
          if other.number_field() != self.number_field():
              return False
          return self.module().is_submodule(other.module())
  
      def __eq__(self, other):
          r"""
          Check whether the order ``self`` is equal to ``other``.
  
          .. NOTE::
  
              This method is just for equality. If you want to check if
              ``self`` is contained in ``other``, use instead
              ``self.is_suborder(other)`` to determine inclusion.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^3 + 2)
              sage: O1 = K.order(a); O1
              Order in Number Field in a with defining polynomial x^3 + 2
              sage: O2 = K.order(a^2); O2
              Order in Number Field in a with defining polynomial x^3 + 2
              sage: O1 == O2
              False
  
              sage: O1 == K
              False
              sage: K == O1
              False
  
          Here is how to check for inclusion::
  
              sage: O2.is_suborder(O1)
              True
          """
          if not isinstance(other, Order):
              return False
          if self._K != other._K:
              return False
          if self is other:
              return True
          return self._module_rep == other._module_rep
  
      def __ne__(self, other):
          """
          Check whether the order ``self`` is not equal to ``other``.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^3 + 2)
              sage: O1 = K.order(a); O1
              Order in Number Field in a with defining polynomial x^3 + 2
              sage: O2 = K.order(a^2); O2
              Order in Number Field in a with defining polynomial x^3 + 2
              sage: O1 != O2
              True
          """
          return not (self == other)
  
      def __hash__(self):
          """
          Compute the hash of ``self``.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^3 + 2)
              sage: O1 = K.order(a)
              sage: h = hash(O1)
          """
          return hash((self._K, self._module_rep))
  
      def random_element(self, *args, **kwds):
          r"""
          Return a random element of this order.
  
          INPUT:
  
          - ``args``, ``kwds`` -- parameters passed to the random
            integer function.  See the documentation for
            ``ZZ.random_element()`` for details.
  
          OUTPUT:
  
          A random element of this order, computed as a random
          `\ZZ`-linear combination of the basis.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^3 + 2)
              sage: OK = K.ring_of_integers()
              sage: OK.random_element() # random output
              -2*a^2 - a - 2
              sage: OK.random_element(distribution="uniform") # random output
              -a^2 - 1
              sage: OK.random_element(-10,10) # random output
              -10*a^2 - 9*a - 2
              sage: K.order(a).random_element() # random output
              a^2 - a - 3
  
          ::
  
              sage: K.<z> = CyclotomicField(17)
              sage: OK = K.ring_of_integers()
              sage: OK.random_element() # random output
              z^15 - z^11 - z^10 - 4*z^9 + z^8 + 2*z^7 + z^6 - 2*z^5 - z^4 - 445*z^3 - 2*z^2 - 15*z - 2
              sage: OK.random_element().is_integral()
              True
              sage: OK.random_element().parent() is OK
              True
  
          A relative example::
  
              sage: K.<a, b> = NumberField([x^2 + 2, x^2 + 1000*x + 1])
              sage: OK = K.ring_of_integers()
              sage: OK.random_element() # random output
              (42221/2*b + 61/2)*a + 7037384*b + 7041
              sage: OK.random_element().is_integral() # random output
              True
              sage: OK.random_element().parent() is OK # random output
              True
  
          An example in a non-maximal order::
  
              sage: K.<a> = QuadraticField(-3)
              sage: R = K.ring_of_integers()
              sage: A = K.order(a)
              sage: A.index_in(R)
              2
              sage: R.random_element() # random output
              -39/2*a - 1/2
              sage: A.random_element() # random output
              2*a - 1
              sage: A.random_element().is_integral()
              True
              sage: A.random_element().parent() is A
              True
          """
          return sum([ZZ.random_element(*args, **kwds)*a for a in self.basis()])
  
      def absolute_degree(self):
          r"""
          Returns the absolute degree of this order, ie the degree of this order over `\ZZ`.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^3 + 2)
              sage: O = K.maximal_order()
              sage: O.absolute_degree()
              3
          """
          return self.number_field().absolute_degree()
  
      def valuation(self, p):
          r"""
          Return the ``p``-adic valuation on this order.
  
          EXAMPLES:
  
          The valuation can be specified with an integer ``prime`` that is
          completely ramified or unramified::
  
              sage: K.<a> = NumberField(x^2 + 1)
              sage: O = K.order(2*a)
              sage: valuations.pAdicValuation(O, 2)
              2-adic valuation
  
              sage: GaussianIntegers().valuation(2)
              2-adic valuation
  
          ::
  
              sage: GaussianIntegers().valuation(3)
              3-adic valuation
  
          A ``prime`` that factors into pairwise distinct factors, results in an error::
  
              sage: GaussianIntegers().valuation(5)
              Traceback (most recent call last):
              ...
              ValueError: The valuation Gauss valuation induced by 5-adic valuation does not approximate a unique extension of 5-adic valuation with respect to x^2 + 1
  
          The valuation can also be selected by giving a valuation on the base
          ring that extends uniquely::
  
              sage: CyclotomicField(5).ring_of_integers().valuation(ZZ.valuation(5))
              5-adic valuation
  
          When the extension is not unique, this does not work::
  
              sage: GaussianIntegers().valuation(ZZ.valuation(5))
              Traceback (most recent call last):
              ...
              ValueError: The valuation Gauss valuation induced by 5-adic valuation does not approximate a unique extension of 5-adic valuation with respect to x^2 + 1
  
          If the fraction field is of the form `K[x]/(G)`, you can specify a
          valuation by providing a discrete pseudo-valuation on `K[x]` which
          sends `G` to infinity::
  
              sage: R.<x> = QQ[]
              sage: v = GaussianIntegers().valuation(GaussValuation(R, QQ.valuation(5)).augmentation(x + 2, infinity))
              sage: w = GaussianIntegers().valuation(GaussValuation(R, QQ.valuation(5)).augmentation(x + 1/2, infinity))
              sage: v == w
              False
  
          .. SEEALSO::
  
              :meth:`NumberField_generic.valuation() <sage.rings.number_field.number_field.NumberField_generic.valuation>`,
              :meth:`pAdicGeneric.valuation() <sage.rings.padics.padic_generic.pAdicGeneric.valuation>`
  
          """
          from sage.rings.padics.padic_valuation import pAdicValuation
          return pAdicValuation(self, p)
  
      def some_elements(self):
          """
          Return a list of elements of the given order.
  
          EXAMPLES::
  
              sage: G = GaussianIntegers(); G
              Gaussian Integers in Number Field in I with defining polynomial x^2 + 1
              sage: G.some_elements()
              [1, I, 2*I, -1, 0, -I, 2, 4*I, -2, -2*I, -4]
  
              sage: R.<t> = QQ[]
              sage: K.<a> = QQ.extension(t^3 - 2); K
              Number Field in a with defining polynomial t^3 - 2
              sage: Z = K.ring_of_integers(); Z
              Maximal Order in Number Field in a with defining polynomial t^3 - 2
              sage: Z.some_elements()
              [1, a, a^2, 2*a, 0, 2, a^2 + 2*a + 1, ..., a^2 + 1, 2*a^2 + 2, a^2 + 2*a, 4*a^2 + 4]
  
          TESTS:
  
          This also works for trivial extensions::
          
              sage: R.<t> = QQ[]
              sage: K.<a> = QQ.extension(t); K
              Number Field in a with defining polynomial t
              sage: Z = K.ring_of_integers(); Z
              Maximal Order in Number Field in a with defining polynomial t
              sage: Z.some_elements()
              [1, 0, 2, -1, -2, 4]
  
          """
          elements = list(self.basis())
          for a in self.fraction_field().some_elements():
              if a in self and a not in elements:
                  elements.append(self(a))
          return elements
  
  ##     def absolute_polynomial(self):
  ##         """
  ##         Returns the absolute polynomial of this order, which is just the absolute polynomial of the number field.
  
  ##         EXAMPLES::
  
  ##         sage: K.<a, b> = NumberField([x^2 + 1, x^3 + x + 1]); OK = K.maximal_order()
  ##         Traceback (most recent call last):
  ##         ...
  ##         NotImplementedError
  
  ##         #sage: OK.absolute_polynomial()
  ##         #x^6 + 5*x^4 - 2*x^3 + 4*x^2 + 4*x + 1
  ##         """
  ##         return self.number_field().absolute_polynomial()
  
  ##     def polynomial(self):
  ##         """
  ##         Returns the polynomial defining the number field that contains self.
  ##         """
  ##         return self.number_field().polynomial()
  
  ##     def polynomial_ntl(self):
  ##         """
  ##         Return defining polynomial of the parent number field as a
  ##         pair, an ntl polynomial and a denominator.
  
  ##         This is used mainly to implement some internal arithmetic.
  
  ##         EXAMPLES::
  
  ##             sage: NumberField(x^2 + 1,'a').maximal_order().polynomial_ntl()
  ##             ([1 0 1], 1)
  ##         """
  ##         return self.number_field().polynomial_ntl()
  
  class AbsoluteOrder(Order):
  
      def __init__(self, K, module_rep, is_maximal=None, check=True):
          """
          EXAMPLES::
  
              sage: from sage.rings.number_field.order import *
              sage: x = polygen(QQ)
              sage: K.<a> = NumberField(x^3+2)
              sage: V, from_v, to_v = K.vector_space()
              sage: M = span([to_v(a^2), to_v(a), to_v(1)],ZZ)
              sage: O = AbsoluteOrder(K, M); O
              Order in Number Field in a with defining polynomial x^3 + 2
  
              sage: M = span([to_v(a^2), to_v(a), to_v(2)],ZZ)
              sage: O = AbsoluteOrder(K, M); O
              Traceback (most recent call last):
              ...
              ValueError: 1 is not in the span of the module, hence not an order.
  
              sage: loads(dumps(O)) == O
              True
  
          Quadratic elements have a special optimized type:
  
          """
          if K.degree() == 2:
              self._element_type = OrderElement_quadratic
              # adding the following attribute makes the comparison of elements
              # faster.
              self._standard_embedding = K._standard_embedding
          else:
              self._element_type = OrderElement_absolute
  
          self._module_rep = module_rep
          V, from_v, to_v = K.vector_space()
          Order.__init__(self, K, is_maximal=is_maximal)
  
          if check:
              if not K.is_absolute():
                  raise ValueError("AbsoluteOrder must be called with an absolute number field.")
              if to_v(1) not in module_rep:
                  raise ValueError("1 is not in the span of the module, hence not an order.")
              if module_rep.rank() != self._K.degree():
                  raise ValueError("the module must have full rank.")
  
      def _element_constructor_(self, x):
          r"""
          Coerce ``x`` into this order.
  
          EXAMPLES::
  
              sage: x = polygen(QQ)
              sage: k.<z> = NumberField(x^2 - 389)
              sage: m = k.order(3*z); m
              Order in Number Field in z with defining polynomial x^2 - 389
              sage: m(6*z)
              6*z
              sage: k(m(6*z))
              6*z
  
          If ``x`` is a list or tuple the element constructed is the
          linear combination of the generators with these coefficients
          (see :trac:`10017`)::
  
              sage: x = polygen(QQ)
              sage: K.<a> = NumberField(x^3-10)
              sage: ZK = K.ring_of_integers()
              sage: ZK.basis()
              [1/3*a^2 + 1/3*a + 1/3, a, a^2]
              sage: ZK([1,2,3])
              10/3*a^2 + 7/3*a + 1/3
              sage: K([1,2,3])
              3*a^2 + 2*a + 1
  
          """
          if is_Element(x) and x.parent() is self:
              return x
          if isinstance(x, (tuple, list)):
              x = sum(xi*gi for xi,gi in zip(x,self.gens()))
          if not is_Element(x) or x.parent() is not self._K:
              x = self._K(x)
          V, _, embedding = self._K.vector_space()
          if not embedding(x) in self._module_rep:
              raise TypeError("Not an element of the order.")
          return self._element_type(self, x)
  
      def __reduce__(self):
          r"""
          Used in pickling.
  
          We test that :trac:`6462` is fixed. This used to fail because
          pickling the order also pickled the cached results of the
          ``basis`` call, which were elements of the order.
  
          ::
  
              sage: L.<a> = QuadraticField(-1)
              sage: OL = L.maximal_order()
              sage: _ = OL.basis()
              sage: loads(dumps(OL)) == OL
              True
          """
          return (AbsoluteOrder, (self.number_field(), self.free_module(), self._is_maximal, False))
  
      def __add__(left, right):
          """
          Add two orders.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(polygen(QQ,'z')^3 - 2)
              sage: O6 = K.order(6*a); O6
              Order in Number Field in a with defining polynomial z^3 - 2
              sage: O6.basis()
              [1, 6*a, 36*a^2]
              sage: O15 = K.order(15*a^2); O15.basis()
              [1, 450*a, 15*a^2]
              sage: R = O6 + O15; R
              Order in Number Field in a with defining polynomial z^3 - 2
              sage: R.basis()
              [1, 6*a, 3*a^2]
          """
          if not isinstance(left, AbsoluteOrder) or not isinstance(right, AbsoluteOrder):
              raise NotImplementedError
          if left.number_field() != right.number_field():
              raise TypeError("Number fields don't match.")
          if left._is_maximal:
              return left
          elif right._is_maximal:
              return right
          return AbsoluteOrder(left._K, left._module_rep + right._module_rep, None)
  
      def __and__(left, right):
          """
          Intersect orders.
  
          EXAMPLES::
  
              sage: K.<i> = QuadraticField(-1)
              sage: O3 = K.order(3*i); O5 = K.order(5*i)
              sage: R = O3 & O5; R
              Order in Number Field in i with defining polynomial x^2 + 1
              sage: R.basis()
              [1, 15*i]
              sage: O3.intersection(O5).basis()
              [1, 15*i]
          """
          if not isinstance(left, AbsoluteOrder) or not isinstance(right, AbsoluteOrder):
              raise NotImplementedError
          if left.number_field() != right.number_field():
              raise TypeError("Number fields don't match.")
          return AbsoluteOrder(left._K, left._module_rep.intersection(right._module_rep), False)
  
      def _magma_init_(self, magma):
          """
          Return Magma version of this absolute order.
  
          INPUT:
  
          - ``magma`` -- a magma interpreter
  
          OUTPUT:
  
          a MagmaElement, the magma version of this absolute order
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^3 + 2) # optional - magma
              sage: magma(K.maximal_order())  # optional - magma
              Equation Order with defining polynomial x^3 + 2 over its ground order
  
          _magma_init_ was called implicitly by the above call::
  
              sage: K.maximal_order()._magma_init_(magma) # optional - magma
              'Order([(_sage_[...]![1, 0, 0]),(_sage_[...]![0, 1, 0]),(_sage_[...]![0, 0, 1])])'
          """
          K = self.number_field()
          v = [K(a)._magma_init_(magma) for a in self.basis()]
          return 'Order([%s])'%(','.join(v))
  
      def discriminant(self):
          """
          Return the discriminant of this order.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^8 + x^3 - 13*x + 26)
              sage: O = K.maximal_order()
              sage: factor(O.discriminant())
              3 * 11 * 13^2 * 613 * 1575917857
              sage: L = K.order(13*a^2)
              sage: factor(L.discriminant())
              3^3 * 5^2 * 11 * 13^60 * 613 * 733^2 * 1575917857
              sage: factor(L.index_in(O))
              3 * 5 * 13^29 * 733
              sage: L.discriminant() / O.discriminant() == L.index_in(O)^2
              True
          """
          try:
              return self.__discriminant
          except AttributeError:
              if self._is_maximal:
                  D = self._K.discriminant()
              else:
                  D = self._K.discriminant(self.basis())
              self.__discriminant = D
              return D
  
      absolute_discriminant = discriminant
  
  
      def change_names(self, names):
          """
          Return a new order isomorphic to this one in the number field with
          given variable names.
  
          EXAMPLES::
  
              sage: R = EquationOrder(x^3 + x + 1, 'alpha'); R
              Order in Number Field in alpha with defining polynomial x^3 + x + 1
              sage: R.basis()
              [1, alpha, alpha^2]
              sage: S = R.change_names('gamma'); S
              Order in Number Field in gamma with defining polynomial x^3 + x + 1
              sage: S.basis()
              [1, gamma, gamma^2]
          """
          K = self.number_field().change_names(names)
          _, to_K = K.structure()
          B = [to_K(a) for a in self.basis()]
          return K.order(B, check_is_integral=False, check_rank=False, allow_subfield=True)
  
      def index_in(self, other):
          """
          Return the index of self in other.  This is a lattice index,
          so it is a rational number if self isn't contained in other.
  
          INPUT:
  
          - ``other`` -- another absolute order with the same ambient number field.
  
          OUTPUT:
  
          a rational number
  
          EXAMPLES::
  
              sage: k.<i> = NumberField(x^2 + 1)
              sage: O1 = k.order(i)
              sage: O5 = k.order(5*i)
              sage: O5.index_in(O1)
              5
  
              sage: k.<a> = NumberField(x^3 + x^2 - 2*x+8)
              sage: o = k.maximal_order()
              sage: o
              Maximal Order in Number Field in a with defining polynomial x^3 + x^2 - 2*x + 8
              sage: O1 = k.order(a); O1
              Order in Number Field in a with defining polynomial x^3 + x^2 - 2*x + 8
              sage: O1.index_in(o)
              2
              sage: O2 = k.order(1+2*a); O2
              Order in Number Field in a with defining polynomial x^3 + x^2 - 2*x + 8
              sage: O1.basis()
              [1, a, a^2]
              sage: O2.basis()
              [1, 2*a, 4*a^2]
              sage: o.index_in(O2)
              1/16
          """
          if not isinstance(other, AbsoluteOrder):
              raise TypeError("other must be an absolute order.")
          if other.ambient() != self.ambient():
              raise ValueError("other must have the same ambient number field as self.")
          return self._module_rep.index_in(other._module_rep)
  
      def module(self):
          """
          Returns the underlying free module corresponding to this
          order, embedded in the vector space corresponding to the
          ambient number field.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^3 + x + 3)
              sage: m = k.order(3*a); m
              Order in Number Field in a with defining polynomial x^3 + x + 3
              sage: m.module()
              Free module of degree 3 and rank 3 over Integer Ring
              Echelon basis matrix:
              [1 0 0]
              [0 3 0]
              [0 0 9]
          """
          return self._module_rep
  
      def intersection(self, other):
          """
          Return the intersection of this order with another order.
  
          EXAMPLES::
  
              sage: k.<i> = NumberField(x^2 + 1)
              sage: O6 = k.order(6*i)
              sage: O9 = k.order(9*i)
              sage: O6.basis()
              [1, 6*i]
              sage: O9.basis()
              [1, 9*i]
              sage: O6.intersection(O9).basis()
              [1, 18*i]
              sage: (O6 & O9).basis()
              [1, 18*i]
              sage: (O6 + O9).basis()
              [1, 3*i]
          """
          return self & other
  
      def _repr_(self):
          """
          Return print representation of this absolute order.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^4 - 5)
              sage: K.maximal_order()._repr_()
              'Maximal Order in Number Field in a with defining polynomial x^4 - 5'
              sage: K.order(a)._repr_()
              'Order in Number Field in a with defining polynomial x^4 - 5'
  
          We have special cases for Gaussian and Eisenstein integers::
  
              sage: K = CyclotomicField(4)
              sage: K.ring_of_integers()
              Gaussian Integers in Cyclotomic Field of order 4 and degree 2
              sage: K = QuadraticField(-3)
              sage: K.ring_of_integers()
              Eisenstein Integers in Number Field in a with defining polynomial x^2 + 3
          """
          if self._is_maximal:
              s = "Maximal Order"
              if self.degree() == 2:
                  D = self.discriminant()
                  if D == -3:
                      s = "Eisenstein Integers"
                  if D == -4:
                      s = "Gaussian Integers"
          else:
              s = "Order"
          return s + " in " + repr(self._K)
  
      def basis(self):
          r"""
          Return the basis over `\ZZ` for this order.
  
          EXAMPLES::
  
              sage: k.<c> = NumberField(x^3 + x^2 + 1)
              sage: O = k.maximal_order(); O
              Maximal Order in Number Field in c with defining polynomial x^3 + x^2 + 1
              sage: O.basis()
              [1, c, c^2]
  
          The basis is an immutable sequence::
  
              sage: type(O.basis())
              <class 'sage.structure.sequence.Sequence_generic'>
  
          The generator functionality uses the basis method::
  
              sage: O.0
              1
              sage: O.1
              c
              sage: O.basis()
              [1, c, c^2]
              sage: O.ngens()
              3
          """
          try:
              return self.__basis
          except AttributeError:
              V, from_V, to_V = self._K.vector_space()
              B = Sequence([self(from_V(b)) for b in self._module_rep.basis()], immutable=True)
              self.__basis = B
          return B
  
      def absolute_order(self):
          """
          Return the absolute order associated to this order, which is
          just this order again since this is an absolute order.
  
          EXAMPLES::
  
              sage: K.<a> = NumberField(x^3 + 2)
              sage: O1 = K.order(a); O1
              Order in Number Field in a with defining polynomial x^3 + 2
              sage: O1.absolute_order() is O1
              True
          """
          return self
  
  class RelativeOrder(Order):
      """
      A relative order in a number field.
  
      A relative order is an order in some relative number field
  
      Invariants of this order may be computed with respect to the
      contained order.
      """
      def __init__(self, K, absolute_order, is_maximal=None, check=True):
          """
          Create the relative order.
  
          EXAMPLES::
  
              sage: k.<a,b> = NumberFieldTower([x^2 - 3, x^2 + 1])
              sage: O = k.maximal_order(); O # indirect doctest
              Maximal Relative Order in Number Field in a with defining polynomial x^2 - 3 over its base field
  
              sage: _ = O.basis()
              sage: loads(dumps(O)) == O
              True
          """
          self._absolute_order = absolute_order
          self._module_rep = absolute_order._module_rep
          Order.__init__(self, K, is_maximal=is_maximal)
  
      def _element_constructor_(self, x):
          """
          Coerce an element into this relative order.
  
          EXAMPLES::
  
              sage: K.<a, b> = NumberField([x^2 + 2, x^2 + 1000*x + 1])
              sage: OK = K.ring_of_integers()
              sage: OK(a)
              a
              sage: OK([3, 4])
              4*a + 3
  
          The following used to fail; see :trac:`5276`::
  
              sage: S.<y> = OK[]; S
              Univariate Polynomial Ring in y over Maximal Relative Order in Number Field in a with defining polynomial x^2 + 2 over its base field
  
          We test that :trac:`4193` is also fixed::
  
              sage: K1.<a> = NumberField(x^3 - 2)
              sage: R.<y> = PolynomialRing(K1)
              sage: K2.<b> = K1.extension(y^2 - a)
              sage: R = K2.order(b)
              sage: b in R
              True
              sage: bb = R.basis()[1]  # b by any other name
              sage: bb == b
              True
              sage: bb.parent() is R
              True
              sage: bb in R # this used to return False
              True
              sage: R(bb) == bb # this used to raise an error
              True
          """
  
          x = self._K(x)
          abs_order = self._absolute_order
          to_abs = abs_order._K.structure()[1]
          x = abs_order(to_abs(x)) # will test membership
          return OrderElement_relative(self, x)
  
      def _repr_(self):
          """
          Return print representation of this relative order.
  
          EXAMPLES::
  
              sage: O = EquationOrder([x^2 + x + 1, x^3 - 2],'a,b')
              sage: O._repr_()
              'Relative Order in Number Field in a with defining polynomial x^2 + x + 1 over its base field'
          """
          #", ".join([str(b) for b in self.basis()]),
          return "%sRelative Order in %r" % ("Maximal " if self._is_maximal else "", self._K)
  
      def absolute_order(self, names='z'):
          """
          Return underlying absolute order associated to this relative
          order.
  
          INPUT:
  
          - ``names`` -- string (default: 'z'); name of generator of absolute extension.
  
          .. note::
  
             There *is* a default variable name, since this absolute
             order is frequently used for internal algorithms.
  
          EXAMPLES::
  
              sage: R = EquationOrder([x^2 + 1, x^2 - 5], 'i,g'); R
              Relative Order in Number Field in i with defining polynomial x^2 + 1 over its base field
              sage: R.basis()
              [1, 6*i - g, -g*i + 2, 7*i - g]
  
              sage: S = R.absolute_order(); S
              Order in Number Field in z with defining polynomial x^4 - 8*x^2 + 36
              sage: S.basis()
              [1, 5/12*z^3 + 1/6*z, 1/2*z^2, 1/2*z^3]
  
          We compute a relative order in alpha0, alpha1, then make the
          number field that contains the absolute order be called
          gamma.::
  
              sage: R = EquationOrder( [x^2 + 2, x^2 - 3], 'alpha'); R
              Relative Order in Number Field in alpha0 with defining polynomial x^2 + 2 over its base field
              sage: R.absolute_order('gamma')
              Order in Number Field in gamma with defining polynomial x^4 - 2*x^2 + 25
              sage: R.absolute_order('gamma').basis()
              [1/2*gamma^2 + 1/2, 7/10*gamma^3 + 1/10*gamma, gamma^2, gamma^3]
          """
          if names == 'z' or names == ('z',):
              return self._absolute_order
          else:
              return self._absolute_order.change_names(names)
  
      def __reduce__(self):
          r"""
          Used for pickling.
  
          EXAMPLES::
  
              sage: L.<a, b> = NumberField([x^2 + 1, x^2 - 5])
              sage: O = L.maximal_order()
              sage: _ = O.basis()
              sage: O == loads(dumps(O))
              True
          """
          return (RelativeOrder, (self.number_field(), self.absolute_order(), self._is_maximal, False))
  
      def basis(self):
          r"""
          Return a basis for this order as `\ZZ`-module.
  
          EXAMPLES::
  
              sage: K.<a,b> = NumberField([x^2+1, x^2+3])
              sage: O = K.order([a,b])
              sage: O.basis()
              [1, -2*a + b, -b*a - 2, -5*a + 3*b]
              sage: z = O.1; z
              -2*a + b
              sage: z.absolute_minpoly()
              x^4 + 14*x^2 + 1
          """
          try:
              return self.__basis
          except AttributeError:
              pass
          O = self._absolute_order
          K = O.number_field()
          from_K, _ = K.structure()
          self.__basis = [OrderElement_relative(self, from_K(a)) for a in O.basis()]
          return self.__basis
  
      def __add__(left, right):
          """
          Add two relative orders or a relative order to an absolute
          order (which always results in an absolute order).
  
          EXAMPLES::
  
              sage: K.<a,b> = NumberField([x^2+1, x^2+3])
              sage: O2 = K.order([2*a, b]); O2.absolute_discriminant()
              36864
              sage: O3 = K.order([3*a, 2*b]); O3.absolute_discriminant()
              2985984
              sage: R = O2 + O3; R
              Relative Order in Number Field in a with defining polynomial x^2 + 1 over its base field
              sage: R.absolute_discriminant()
              9216
              sage: R.is_suborder(O2)
              False
              sage: O2.is_suborder(R)
              True
              sage: O3.is_suborder(R)
              True
          """
          if isinstance(left, AbsoluteOrder):
              return left + right._absolute_order
          elif isinstance(right, AbsoluteOrder):
              return left._absolute_order + right
          elif isinstance(left, RelativeOrder) and isinstance(right, RelativeOrder):
              if left._K != right._K:
                  raise TypeError("Number fields don't match.")
              return RelativeOrder(left._K, left._absolute_order + right._absolute_order,
                                   check=False)
          else:
              raise NotImplementedError
  
      def __and__(left, right):
          """
          Intersect two relative orders or a relative and absolute order
          (which always results in an absolute order).
  
          EXAMPLES::
  
              sage: L.<a, b> = NumberField([x^2 + 1, x^2 - 5])
              sage: O1 = L.order([a, 2*b])
              sage: O2 = L.order([2*a, b])
              sage: O3 = O1 & O2; O3
              Relative Order in Number Field in a with defining polynomial x^2 + 1 over its base field
              sage: O3.index_in(L.maximal_order())
              32
          """
          if isinstance(left, AbsoluteOrder):
              return left & right._absolute_order
          elif isinstance(right, AbsoluteOrder):
              return left._absolute_order & right
          elif isinstance(left, RelativeOrder) and isinstance(right, RelativeOrder):
              if left._K != right._K:
                  raise TypeError("Number fields don't match.")
              return RelativeOrder(left._K, left._absolute_order & right._absolute_order,
                                    check=False)
          else:
              raise NotImplementedError
  
      def absolute_discriminant(self):
          """
          Return the absolute discriminant of self, which is the discriminant
          of the absolute order associated to self.
  
          OUTPUT:
  
          an integer
  
          EXAMPLES::
  
              sage: R = EquationOrder([x^2 + 1, x^3 + 2], 'a,b')
              sage: d = R.absolute_discriminant(); d
              -746496
              sage: d is R.absolute_discriminant()
              True
              sage: factor(d)
              -1 * 2^10 * 3^6
          """
          return self.absolute_order().discriminant()
  
      def is_suborder(self, other):
          """
          Returns true if self is a subset of the order other.
  
          EXAMPLES::
  
              sage: K.<a,b> = NumberField([x^2 + 1, x^3 + 2])
              sage: R1 = K.order([a,b])
              sage: R2 = K.order([2*a,b])
              sage: R3 = K.order([a + b, b + 2*a])
              sage: R1.is_suborder(R2)
              False
              sage: R2.is_suborder(R1)
              True
              sage: R3.is_suborder(R1)
              True
              sage: R1.is_suborder(R3)
              True
              sage: R1 == R3
              True
          """
          return self.absolute_order().is_suborder(other.absolute_order())
  
      def index_in(self, other):
          """
          Return the index of self in other.  This is a lattice index,
          so it is a rational number if self isn't contained in other.
  
          INPUT:
  
          - ``other`` -- another order with the same ambient absolute number field.
  
          OUTPUT:
  
          a rational number
  
          EXAMPLES::
  
              sage: K.<a,b> = NumberField([x^3 + x + 3, x^2 + 1])
              sage: R1 = K.order([3*a, 2*b])
              sage: R2 = K.order([a, 4*b])
              sage: R1.index_in(R2)
              729/8
              sage: R2.index_in(R1)
              8/729
          """
          if not isinstance(other, Order):
              raise TypeError("other must be an absolute order.")
          return self.absolute_order().index_in(other.absolute_order())
  
  
  
  def each_is_integral(v):
      """
      Return True if each element of the list ``v`` of elements of a number
      field is integral.
  
      EXAMPLES::
  
          sage: W.<sqrt5> = NumberField(x^2 - 5)
          sage: from sage.rings.number_field.order import each_is_integral
          sage: each_is_integral([sqrt5, 2, (1+sqrt5)/2])
          True
          sage: each_is_integral([sqrt5, (1+sqrt5)/3])
          False
      """
      for x in v:
          if not x.is_integral():
              return False
      return True
  
  def absolute_order_from_ring_generators(gens, check_is_integral=True,
                                          check_rank=True, is_maximal=None,
                                          allow_subfield=False):
      """
      INPUT:
  
      - ``gens`` -- list of integral elements of an absolute order.
      - ``check_is_integral`` -- bool (default: True), whether to check that each
        generator is integral.
      - ``check_rank`` -- bool (default: True), whether to check that the ring
        generated by gens is of full rank.
      - ``is_maximal`` -- bool (or None); set if maximality of the generated order is
        known
      - ``allow_subfield`` -- bool (default: False), if True and the generators do
        not generate an order, i.e., they generate a subring of smaller rank,
        instead of raising an error, return an order in a smaller number field.
  
      EXAMPLES::
  
          sage: K.<a> = NumberField(x^4 - 5)
          sage: K.order(a)
          Order in Number Field in a with defining polynomial x^4 - 5
  
      We have to explicitly import this function, since typically it is called
      with ``K.order`` as above.::
  
          sage: from sage.rings.number_field.order import absolute_order_from_ring_generators
          sage: absolute_order_from_ring_generators([a])
          Order in Number Field in a with defining polynomial x^4 - 5
          sage: absolute_order_from_ring_generators([3*a, 2, 6*a+1])
          Order in Number Field in a with defining polynomial x^4 - 5
  
      If one of the inputs is non-integral, it is an error.::
  
          sage: absolute_order_from_ring_generators([a/2])
          Traceback (most recent call last):
          ...
          ValueError: each generator must be integral
  
      If the gens do not generate an order, i.e., generate a ring of full
      rank, then it is an error.::
  
          sage: absolute_order_from_ring_generators([a^2])
          Traceback (most recent call last):
          ...
          ValueError: the rank of the span of gens is wrong
  
      Both checking for integrality and checking for full rank can be
      turned off in order to save time, though one can get nonsense as
      illustrated below.::
  
          sage: absolute_order_from_ring_generators([a/2], check_is_integral=False)
          Order in Number Field in a with defining polynomial x^4 - 5
          sage: absolute_order_from_ring_generators([a^2], check_rank=False)
          Order in Number Field in a with defining polynomial x^4 - 5
      """
      if check_is_integral and not each_is_integral(gens):
          raise ValueError("each generator must be integral")
      gens = Sequence(gens)
      n = [x.absolute_minpoly().degree() for x in gens]
      module_gens = monomials(gens, n)
      return absolute_order_from_module_generators(module_gens,
                 check_integral=False, check_is_ring=False,
                 check_rank=check_rank, is_maximal=is_maximal,
                 allow_subfield = allow_subfield)
  
  
  def absolute_order_from_module_generators(gens,
                check_integral=True, check_rank=True,
                check_is_ring=True, is_maximal=None,
                allow_subfield = False):
      """
      INPUT:
  
      - ``gens`` -- list of elements of an absolute number field that generates an
        order in that number field as a ZZ *module*.
      - ``check_integral`` -- check that each gen is integral
      - ``check_rank`` -- check that the gens span a module of the correct rank
      - ``check_is_ring`` -- check that the module is closed under multiplication
        (this is very expensive)
      - ``is_maximal`` -- bool (or None); set if maximality of the generated order is known
  
      OUTPUT:
  
      an absolute order
  
      EXAMPLES:
  
      We have to explicitly import the function, since it isn't meant
      for regular usage::
  
          sage: from sage.rings.number_field.order import absolute_order_from_module_generators
  
          sage: K.<a> = NumberField(x^4 - 5)
          sage: O = K.maximal_order(); O
          Maximal Order in Number Field in a with defining polynomial x^4 - 5
          sage: O.basis()
          [1/2*a^2 + 1/2, 1/2*a^3 + 1/2*a, a^2, a^3]
          sage: O.module()
          Free module of degree 4 and rank 4 over Integer Ring
          Echelon basis matrix:
          [1/2   0 1/2   0]
          [  0 1/2   0 1/2]
          [  0   0   1   0]
          [  0   0   0   1]
          sage: g = O.basis(); g
          [1/2*a^2 + 1/2, 1/2*a^3 + 1/2*a, a^2, a^3]
          sage: absolute_order_from_module_generators(g)
          Order in Number Field in a with defining polynomial x^4 - 5
  
      We illustrate each check flag -- the output is the same but in case
      the function would run ever so slightly faster::
  
          sage: absolute_order_from_module_generators(g,  check_is_ring=False)
          Order in Number Field in a with defining polynomial x^4 - 5
          sage: absolute_order_from_module_generators(g,  check_rank=False)
          Order in Number Field in a with defining polynomial x^4 - 5
          sage: absolute_order_from_module_generators(g,  check_integral=False)
          Order in Number Field in a with defining polynomial x^4 - 5
  
      Next we illustrate constructing "fake" orders to illustrate turning
      off various check flags::
  
          sage: k.<i> = NumberField(x^2 + 1)
          sage: R = absolute_order_from_module_generators([2, 2*i],  check_is_ring=False); R
          Order in Number Field in i with defining polynomial x^2 + 1
          sage: R.basis()
          [2, 2*i]
          sage: R = absolute_order_from_module_generators([k(1)],  check_rank=False); R
          Order in Number Field in i with defining polynomial x^2 + 1
          sage: R.basis()
          [1]
  
      If the order contains a non-integral element, even if we don't check
      that, we'll find that the rank is wrong or that the order isn't closed
      under multiplication::
  
          sage: absolute_order_from_module_generators([1/2, i],  check_integral=False)
          Traceback (most recent call last):
          ...
          ValueError: the module span of the gens is not closed under multiplication.
          sage: R = absolute_order_from_module_generators([1/2, i],  check_is_ring=False, check_integral=False); R
          Order in Number Field in i with defining polynomial x^2 + 1
          sage: R.basis()
          [1/2, i]
  
      We turn off all check flags and make a really messed up order::
  
          sage: R = absolute_order_from_module_generators([1/2, i],  check_is_ring=False, check_integral=False, check_rank=False); R
          Order in Number Field in i with defining polynomial x^2 + 1
          sage: R.basis()
          [1/2, i]
  
      An order that lives in a subfield::
  
          sage: F.<alpha> = NumberField(x**4+3)
          sage: F.order([alpha**2], allow_subfield=True)
          Order in Number Field in alpha with defining polynomial x^4 + 3
      """
      if len(gens) == 0:
          raise ValueError("gens must span an order over ZZ")
      gens = Sequence(gens)
      if check_integral and not each_is_integral(gens):
          raise ValueError("each generator must be integral")
  
      K = gens.universe()
      if is_NumberFieldOrder(K):
          K = K.number_field()
      V, from_V, to_V = K.vector_space()
      mod_gens = [to_V(x) for x in gens]
      ambient = ZZ**V.dimension()
      W = ambient.span(mod_gens)
  
      if allow_subfield:
          if W.rank() < K.degree():
              # We have to make the order in a smaller field.
              # We do this by choosing a random element of W,
              # moving it back to K, and checking that it defines
              # a field of degree equal to the degree of W.
              # Then we move everything into that field, where
              # W does define an order.
              while True:
                  z = V.random_element()
                  alpha = from_V(z)
                  if alpha.minpoly().degree() == W.rank():
                      break
              # Now alpha generates a subfield there W is an order
              # (with the right rank).
              # We move each element of W to this subfield.
              c = alpha.coordinates_in_terms_of_powers()
  
      elif check_rank:
          if W.rank() != K.degree():
              raise ValueError("the rank of the span of gens is wrong")
  
      if check_is_ring:
          # Is there a faster way?
          alg = [to_V(x) for x in monomials(gens, [f.absolute_minpoly().degree() for f in gens])]
          if ambient.span(alg) != W:
              raise ValueError("the module span of the gens is not closed under multiplication.")
  
      return AbsoluteOrder(K, W, check=False, is_maximal=is_maximal)  # we have already checked everything
  
  
  
  
  
  def relative_order_from_ring_generators(gens,
                                          check_is_integral=True,
                                          check_rank=True,
                                          is_maximal = None,
                                          allow_subfield=False):
      """
      INPUT:
  
      - ``gens`` -- list of integral elements of an absolute order.
      - ``check_is_integral`` -- bool (default: True), whether to check that each
        generator is integral.
      - ``check_rank`` -- bool (default: True), whether to check that the ring
        generated by gens is of full rank.
      - ``is_maximal`` -- bool (or None); set if maximality of the generated order is
        known
  
      EXAMPLES:
  
      We have to explicitly import this function, since it isn't meant
      for regular usage::
  
          sage: from sage.rings.number_field.order import relative_order_from_ring_generators
          sage: K.<i, a> = NumberField([x^2 + 1, x^2 - 17])
          sage: R = K.base_field().maximal_order()
          sage: S = relative_order_from_ring_generators([i,a]); S
          Relative Order in Number Field in i with defining polynomial x^2 + 1 over its base field
  
      Basis for the relative order, which is obtained by computing the algebra generated
      by i and a::
  
          sage: S.basis()
          [1, 7*i - 2*a, -a*i + 8, 25*i - 7*a]
      """
      if check_is_integral and not each_is_integral(gens):
          raise ValueError("each generator must be integral")
      gens = Sequence(gens)
  
      # The top number field that contains the order.
      K = gens.universe()
  
      # The absolute version of that field.
      Kabs = K.absolute_field('z')
      from_Kabs, to_Kabs = Kabs.structure()
  
      module_gens = [to_Kabs(a) for a in gens]
      n = [a.absolute_minpoly().degree() for a in gens]
      absolute_order_module_gens = monomials(module_gens, n)
  
      abs_order =  absolute_order_from_module_generators(absolute_order_module_gens,
                                                         check_integral=False, check_is_ring=False,
                                                         check_rank=check_rank)
  
      return RelativeOrder(K, abs_order, check=False, is_maximal=is_maximal)
  
  
  def GaussianIntegers(names="I"):
      r"""
      Return the ring of Gaussian integers, that is all complex numbers
      of the form `a + b I` with `a` and `b` integers and `I = \sqrt{-1}`.
  
      EXAMPLES::
  
          sage: ZZI.<I> = GaussianIntegers()
          sage: ZZI
          Gaussian Integers in Number Field in I with defining polynomial x^2 + 1
          sage: factor(3 + I)
          (-I) * (I + 1) * (2*I + 1)
          sage: CC(I)
          1.00000000000000*I
          sage: I.minpoly()
          x^2 + 1
          sage: GaussianIntegers().basis()
          [1, I]
      """
      from sage.rings.all import CDF, NumberField
      f = ZZ['x']([1,0,1])
      nf = NumberField(f, names, embedding=CDF(0, 1))
      return nf.ring_of_integers()
  
  
  def EisensteinIntegers(names="omega"):
      r"""
      Return the ring of Eisenstein integers, that is all complex numbers
      of the form `a + b \omega` with `a` and `b` integers and
      `omega = (-1 + \sqrt{-3})/2`.
  
      EXAMPLES::
  
          sage: R.<omega> = EisensteinIntegers()
          sage: R
          Eisenstein Integers in Number Field in omega with defining polynomial x^2 + x + 1
          sage: factor(3 + omega)
          (omega) * (-3*omega - 2)
          sage: CC(omega)
          -0.500000000000000 + 0.866025403784439*I
          sage: omega.minpoly()
          x^2 + x + 1
          sage: EisensteinIntegers().basis()
          [1, omega]
      """
      from sage.rings.all import CDF, NumberField
      f = ZZ['x']([1,1,1])
      nf = NumberField(f, names, embedding=CDF(-0.5, 0.8660254037844386))
      return nf.ring_of_integers()
  