text: r"""
  Lists of Manin symbols (elements of `\mathbb{P}^1(R/N)`) over number fields
  
  Lists of elements of `\mathbb{P}^1(R/N)` where `R` is the ring of integers of a number
  field `K` and `N` is an integral ideal.
  
  AUTHORS:
  
  - Maite Aranes (2009): Initial version
  
  EXAMPLES:
  
  We define a P1NFList:
  
  ::
  
      sage: k.<a> = NumberField(x^3 + 11)
      sage: N = k.ideal(5, a^2 - a + 1)
      sage: P = P1NFList(N); P
      The projective line over the ring of integers modulo the Fractional ideal (5, a^2 - a + 1)
  
  List operations with the P1NFList:
  
  ::
  
      sage: len(P)
      26
      sage: [p for p in P]
      [M-symbol (0: 1) of level Fractional ideal (5, a^2 - a + 1),
      ...
      M-symbol (1: 2*a^2 + 2*a) of level Fractional ideal (5, a^2 - a + 1)]
  
  The elements of the P1NFList are M-symbols:
  
  ::
  
      sage: type(P[2])
      <class 'sage.modular.modsym.p1list_nf.MSymbol'>
  
  Definition of MSymbols:
  
  ::
  
      sage: alpha = MSymbol(N, 3, a^2); alpha
      M-symbol (3: a^2) of level Fractional ideal (5, a^2 - a + 1)
  
  Find the index of the class of an M-Symbol `(c: d)` in the list:
  
  ::
  
      sage: i = P.index(alpha)
      sage: P[i].c*alpha.d - P[i].d*alpha.c in N
      True
  
  Lift an MSymbol to a matrix in `SL(2, R)`:
  
  ::
  
      sage: alpha = MSymbol(N, a + 2, 3*a^2)
      sage: alpha.lift_to_sl2_Ok()
      [1, -4*a^2 + 9*a - 21, a + 2, a^2 - 3*a + 3]
      sage: Ok = k.ring_of_integers()
      sage: M = Matrix(Ok, 2, alpha.lift_to_sl2_Ok())
      sage: det(M)
      1
      sage: M[1][1] - alpha.d in N
      True
  
  Lift an MSymbol from P1NFList to a matrix in `SL(2, R)`
  
  ::
  
      sage: P[3]
      M-symbol (1: -2*a) of level Fractional ideal (5, a^2 - a + 1)
      sage: P.lift_to_sl2_Ok(3)
      [0, -1, 1, -2*a]
  """
  #*****************************************************************************
  #       Copyright (C) 2009, Maite Aranes <M.T.Aranes@warwick.ac.uk>
  #
  #  Distributed under the terms of the GNU General Public License (GPL)
  #                  http://www.gnu.org/licenses/
  #*****************************************************************************
  
  
  from sage.structure.sage_object import SageObject
  
  from sage.misc.search import search
  
  _level_cache = {} # The info stored here is used in the normalization of MSymbols.
  
  def P1NFList_clear_level_cache():
      """
      Clear the global cache of data for the level ideals.
  
      EXAMPLES::
  
          sage: k.<a> = NumberField(x^3 + 11)
          sage: N = k.ideal(a+1)
          sage: alpha = MSymbol(N, 2*a^2, 5)
          sage: alpha.normalize()
          M-symbol (-4*a^2: 5*a^2) of level Fractional ideal (a + 1)
          sage: sage.modular.modsym.p1list_nf._level_cache
          {Fractional ideal (a + 1): (...)}
          sage: sage.modular.modsym.p1list_nf.P1NFList_clear_level_cache()
          sage: sage.modular.modsym.p1list_nf._level_cache
          {}
      """
      global _level_cache
      _level_cache = {}
  
  
  class MSymbol(SageObject):
      """
      The constructor for an M-symbol over a number field.
  
      INPUT:
  
      -  ``N`` -- integral ideal (the modulus or level).
  
      - ``c`` -- integral element of the underlying number field or an MSymbol of
        level N.
  
      - ``d`` -- (optional) when present, it must be an integral element such
        that <c> + <d> + N = R, where R is the corresponding ring of integers.
  
      - ``check`` -- bool (default True). If ``check=False`` the constructor does
        not check the condition <c> + <d> + N = R.
  
      OUTPUT:
  
      An M-symbol modulo the given ideal N, i.e. an element of the
      projective line `\\mathbb{P}^1(R/N)`, where R is the ring of integers of
      the underlying number field.
  
      EXAMPLES::
  
          sage: k.<a> = NumberField(x^3 + 11)
          sage: N = k.ideal(a + 1, 2)
          sage: MSymbol(N, 3, a^2 + 1)
          M-symbol (3: a^2 + 1) of level Fractional ideal (2, a + 1)
  
      We can give a tuple as input:
  
      ::
  
          sage: MSymbol(N, (1, 0))
          M-symbol (1: 0) of level Fractional ideal (2, a + 1)
  
      We get an error if <c>, <d> and N are not coprime:
  
      ::
  
          sage: MSymbol(N, 2*a, a - 1)
          Traceback (most recent call last):
          ...
          ValueError: (2*a, a - 1) is not an element of P1(R/N).
          sage: MSymbol(N, (0, 0))
          Traceback (most recent call last):
          ...
          ValueError: (0, 0) is not an element of P1(R/N).
  
      Saving and loading works:
  
      ::
  
          sage: alpha = MSymbol(N, 3, a^2 + 1)
          sage: loads(dumps(alpha))==alpha
          True
      """
      def __init__(self, N, c, d=None, check=True):
          """
          See ``MSymbol`` for full documentation.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^4 + 13*x - 7)
              sage: N = k.ideal(5)
              sage: MSymbol(N, 0, 6*a)
              M-symbol (0: 6*a) of level Fractional ideal (5)
              sage: MSymbol(N, a^2 + 3, 7)
              M-symbol (a^2 + 3: 7) of level Fractional ideal (5)
          """
          k = N.number_field()
          R = k.ring_of_integers()
          self.__N = N
          if d is None:  # if we give a list (c, d) or an MSymbol as input
              if isinstance(c, MSymbol):
                  if c.N() is N:
                      c1 = R(c[0])
                      d1 = R(c[1])
                  else:
                      raise ValueError("Cannot change level of an MSymbol")
              else:
                  try:
                      c1 = R(c[0])
                      d1 = R(c[1])
                  except (ValueError, TypeError):
                      raise TypeError("Unable to create a Manin symbol from %s"%c)
          else:
              try:
                  c1 = R(c)
                  d1 = R(d)
              except (ValueError, TypeError):
                  raise TypeError("Unable to create a Manin symbol from (%s, %s)"%(c, d))
          if check:
              if (c1.is_zero() and d1.is_zero()) or not N.is_coprime(k.ideal(c1, d1)):
                  raise ValueError("(%s, %s) is not an element of P1(R/N)."%(c1, d1))
          self.__c, self.__d = (c1, d1)
  
      def __repr__(self):
          """
          Returns the string representation of this MSymbol.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 23)
              sage: N = k.ideal(3, a - 1)
              sage: MSymbol(N, 3, a)
              M-symbol (3: a) of level Fractional ideal (3, 1/2*a - 1/2)
          """
          return "M-symbol (%s: %s) of level %s"%(self.__c, self.__d, self.__N)
  
      def _latex_(self):
          r"""
          Return latex representation of self.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^4 + 13*x - 7)
              sage: N = k.ideal(a^3 - 1)
              sage: alpha = MSymbol(N, 3, 5*a^2 - 1)
              sage: latex(alpha) # indirect doctest
              \(3: 5 a^{2} - 1\)
          """
          return "\\(%s: %s\)"%(self.c._latex_(), self.d._latex_())
  
      def __cmp__(self, other):
          """
          Comparison function for objects of the class MSymbol.
  
          The order is the same as for the underlying lists of lists.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 23)
              sage: N = k.ideal(3, a - 1)
              sage: alpha = MSymbol(N, 3, a)
              sage: beta = MSymbol(N, 1, 0)
              sage: alpha < beta
              False
              sage: beta = MSymbol(N, 3, a + 1)
              sage: alpha < beta
              True
          """
          if not isinstance(other, MSymbol):
              raise ValueError("You can only compare with another M-symbol")
          return cmp([self.__c.list(), self.__d.list()],
                              [other.__c.list(), other.__d.list()])
  
      def N(self):
          """
          Returns the level or modulus of this MSymbol.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 23)
              sage: N = k.ideal(3, a - 1)
              sage: alpha = MSymbol(N, 3, a)
              sage: alpha.N()
              Fractional ideal (3, 1/2*a - 1/2)
          """
          return self.__N
  
      def tuple(self):
          """
          Returns the MSymbol as a list (c, d).
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 23)
              sage: N = k.ideal(3, a - 1)
              sage: alpha = MSymbol(N, 3, a); alpha
              M-symbol (3: a) of level Fractional ideal (3, 1/2*a - 1/2)
              sage: alpha.tuple()
              (3, a)
          """
          return self.__c, self.__d
  
      def __getitem__(self, n):
          """
          Indexing function for the list defined by an M-symbol.
  
          INPUT:
  
          - ``n`` -- integer (0 or 1, since the list defined by an M-symbol has
          length 2)
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 23)
              sage: N = k.ideal(3, a - 1)
              sage: alpha = MSymbol(N, 3, a); alpha
              M-symbol (3: a) of level Fractional ideal (3, 1/2*a - 1/2)
              sage: alpha[0]
              3
              sage: alpha[1]
              a
          """
          return self.tuple()[n]
  
      def __get_c(self):
          """
          Returns the first coefficient of the M-symbol.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^3 + 11)
              sage: N = k.ideal(a + 1, 2)
              sage: alpha = MSymbol(N, 3, a^2 + 1)
              sage: alpha.c # indirect doctest
              3
          """
          return self.__c
      c = property(__get_c)
  
      def __get_d(self):
          """
          Returns the second coefficient of the M-symbol.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^3 + 11)
              sage: N = k.ideal(a + 1, 2)
              sage: alpha = MSymbol(N, 3, a^2 + 1)
              sage: alpha.d # indirect doctest
              a^2 + 1
          """
          return self.__d
      d = property(__get_d)
  
      def lift_to_sl2_Ok(self):
          """
          Lift the MSymbol to an element of `SL(2, Ok)`, where `Ok` is the ring
          of integers of the corresponding number field.
  
          OUTPUT:
  
          A list of integral elements `[a, b, c', d']` that are the entries of
          a 2x2 matrix with determinant 1. The lower two entries are congruent
          (modulo the level) to the coefficients `c, d` of the MSymbol self.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 23)
              sage: N = k.ideal(3, a - 1)
              sage: alpha = MSymbol(N, 3*a + 1, a)
              sage: alpha.lift_to_sl2_Ok()
              [0, -1, 1, a]
          """
          return lift_to_sl2_Ok(self.__N, self.__c, self.__d)
  
      def normalize(self, with_scalar=False):
          """
          Returns a normalized MSymbol (a canonical representative of an element
          of `\mathbb{P}^1(R/N)` ) equivalent to ``self``.
  
          INPUT:
  
          - ``with_scalar`` -- bool (default False)
  
          OUTPUT:
  
          - (only if ``with_scalar=True``) a transforming scalar `u`, such that
            `(u*c', u*d')` is congruent to `(c: d)` (mod `N`), where `(c: d)`
            are the coefficients of ``self`` and `N` is the level.
  
          -  a normalized MSymbol (c': d') equivalent to ``self``.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 23)
              sage: N = k.ideal(3, a - 1)
              sage: alpha1 = MSymbol(N, 3, a); alpha1
              M-symbol (3: a) of level Fractional ideal (3, 1/2*a - 1/2)
              sage: alpha1.normalize()
              M-symbol (0: 1) of level Fractional ideal (3, 1/2*a - 1/2)
              sage: alpha2 = MSymbol(N, 4, a + 1)
              sage: alpha2.normalize()
              M-symbol (1: -a) of level Fractional ideal (3, 1/2*a - 1/2)
  
          We get the scaling factor by setting ``with_scalar=True``:
  
          ::
  
              sage: alpha1.normalize(with_scalar=True)
              (a, M-symbol (0: 1) of level Fractional ideal (3, 1/2*a - 1/2))
              sage: r, beta1 = alpha1.normalize(with_scalar=True)
              sage: r*beta1.c - alpha1.c in N
              True
              sage: r*beta1.d - alpha1.d in N
              True
              sage: r, beta2 = alpha2.normalize(with_scalar=True)
              sage: r*beta2.c - alpha2.c in N
              True
              sage: r*beta2.d - alpha2.d in N
              True
          """
          N = self.__N
          k = N.number_field()
          R = k.ring_of_integers()
  
          if self.__c in N:
              if with_scalar:
                  return N.reduce(self.d), MSymbol(N, 0, 1)
              else:
                  return MSymbol(N, 0, 1)
          if self.d in N:
              if with_scalar:
                  return N.reduce(self.c), MSymbol(N, 1, 0)
              else:
                  return MSymbol(N, 1, 0)
          if N.is_coprime(self.c):
              cinv = R(self.c).inverse_mod(N)
              if with_scalar:
                  return N.reduce(self.c), MSymbol(N, 1, N.reduce(self.d*cinv))
              else:
                  return MSymbol(N, 1, N.reduce(self.d*cinv))
  
          if N in _level_cache:
              Lfacs, Lxs = _level_cache[N]
          else:
              Lfacs = [p**e for p, e in N.factor()]
              Lxs = [(N/p).element_1_mod(p) for p in Lfacs]
              # Lfacs, Lxs only depend of the ideal: same lists every time we
              # call normalize for a given level, so we store the lists.
              _level_cache[N] = (Lfacs, Lxs)
          u = 0  # normalizer factor
          p_i = 0
          for p in Lfacs:
              if p.is_coprime(self.c):
                  inv = self.c.inverse_mod(p)
              else:
                  inv = self.d.inverse_mod(p)
              u = u + inv*Lxs[p_i]
              p_i = p_i + 1
          c, d = (N.reduce(u*self.c), N.reduce(u*self.d))
          if (c - 1) in N:
              c = R(1)
          if with_scalar:
              return u.inverse_mod(N), MSymbol(N, c, d)
          else:
              return MSymbol(N, c, d)
  
  
  #**************************************************************************
  #*       P1NFList class                                                   *
  #**************************************************************************
  class P1NFList(SageObject):
      """
      The class for `\mathbb{P}^1(R/N)`, the projective line modulo `N`, where
      `R` is the ring of integers of a number field `K` and `N` is an integral ideal.
  
      INPUT:
  
      -  ``N`` - integral ideal (the modulus or level).
  
      OUTPUT:
  
      A P1NFList object representing `\mathbb{P}^1(R/N)`.
  
      EXAMPLES::
  
          sage: k.<a> = NumberField(x^3 + 11)
          sage: N = k.ideal(5, a + 1)
          sage: P = P1NFList(N); P
          The projective line over the ring of integers modulo the Fractional ideal (5, a + 1)
  
      Saving and loading works.
  
      ::
  
          sage: loads(dumps(P)) == P
          True
      """
      def __init__(self, N):
          """
          The constructor for the class P1NFList. See ``P1NFList`` for full
          documentation.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 5)
              sage: N = k.ideal(3, a - 1)
              sage: P = P1NFList(N); P
              The projective line over the ring of integers modulo the Fractional ideal (3, a + 2)
          """
          self.__N = N
          self.__list = p1NFlist(N)
          self.__list.sort()
  
      def __cmp__(self, other):
          """
          Comparison function for objects of the class P1NFList.
  
          The order is the same as for the underlying modulus.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 23)
              sage: N1 = k.ideal(3, a + 1)
              sage: P1 = P1NFList(N1)
              sage: N2 = k.ideal(a + 2)
              sage: P2 = P1NFList(N2)
              sage: P1 < P2
              False
              sage: P1 > P2
              True
              sage: P1 == P1NFList(N1)
              True
          """
          if not isinstance(other, P1NFList):
              raise ValueError("You can only compare with another P1NFList")
          return cmp(self.__N, other.__N)
  
      def __getitem__(self, n):
          """
          Standard indexing function for the class P1NFList.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^3 + 11)
              sage: N = k.ideal(a)
              sage: P = P1NFList(N)
              sage: list(P) == P._P1NFList__list
              True
              sage: j = randint(0,len(P)-1)
              sage: P[j] == P._P1NFList__list[j]
              True
          """
          return self.__list[n]
  
      def __len__(self):
          """
          Returns the length of this P1NFList.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^3 + 11)
              sage: N = k.ideal(5, a^2 - a + 1)
              sage: P = P1NFList(N)
              sage: len(P)
              26
          """
          return len(self.__list)
  
      def __repr__(self):
          """
          Returns the string representation of this P1NFList.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^3 + 11)
              sage: N = k.ideal(5, a+1)
              sage: P = P1NFList(N); P
              The projective line over the ring of integers modulo the Fractional ideal (5, a + 1)
  
          """
          return "The projective line over the ring of integers modulo the %s"%self.__N
  
      def list(self):
          """
          Returns the underlying list of this P1NFList object.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^3 + 11)
              sage: N = k.ideal(5, a+1)
              sage: P = P1NFList(N)
              sage: type(P)
              <class 'sage.modular.modsym.p1list_nf.P1NFList'>
              sage: type(P.list())
              <type 'list'>
          """
          return self.__list
  
      def normalize(self, c, d=None, with_scalar=False):
          """
          Returns a normalised element of `\mathbb{P}^1(R/N)`.
  
          INPUT:
  
          - ``c`` -- integral element of the underlying number field, or an
            MSymbol.
  
          - ``d`` -- (optional) when present, it must be an integral element of
            the number field such that `(c, d)` defines an M-symbol of level `N`.
  
          - ``with_scalar`` -- bool (default False)
  
          OUTPUT:
  
          - (only if ``with_scalar=True``) a transforming scalar `u`, such that
            `(u*c', u*d')` is congruent to `(c: d)` (mod `N`).
  
          - a normalized MSymbol (c': d') equivalent to `(c: d)`.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 31)
              sage: N = k.ideal(5, a + 3)
              sage: P = P1NFList(N)
              sage: P.normalize(3, a)
              M-symbol (1: 2*a) of level Fractional ideal (5, 1/2*a + 3/2)
  
          We can use an MSymbol as input:
  
          ::
  
              sage: alpha = MSymbol(N, 3, a)
              sage: P.normalize(alpha)
              M-symbol (1: 2*a) of level Fractional ideal (5, 1/2*a + 3/2)
  
          If we are interested in the normalizing scalar:
  
          ::
  
              sage: P.normalize(alpha, with_scalar=True)
              (-a, M-symbol (1: 2*a) of level Fractional ideal (5, 1/2*a + 3/2))
              sage: r, beta = P.normalize(alpha, with_scalar=True)
              sage: (r*beta.c - alpha.c in N) and (r*beta.d - alpha.d in N)
              True
          """
          if d is None:
              try:
                  c = MSymbol(self.__N, c) # check that c is an MSymbol
              except ValueError: # catch special case of wrong level
                  raise ValueError("The MSymbol is of a different level")
              return c.normalize(with_scalar)
          return MSymbol(self.N(), c, d).normalize(with_scalar)
  
      def N(self):
          """
          Returns the level or modulus of this P1NFList.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 31)
              sage: N = k.ideal(5, a + 3)
              sage: P = P1NFList(N)
              sage: P.N()
              Fractional ideal (5, 1/2*a + 3/2)
          """
          return self.__N
  
      def index(self, c, d=None, with_scalar=False):
          """
          Returns the index of the class of the pair `(c, d)` in the fixed list
          of representatives of `\mathbb{P}^1(R/N)`.
  
          INPUT:
  
          - ``c`` -- integral element of the corresponding number field, or an
            MSymbol.
  
          - ``d`` -- (optional) when present, it must be an integral element of
            the number field such that `(c, d)` defines an M-symbol of level `N`.
  
          - ``with_scalar`` -- bool (default False)
  
          OUTPUT:
  
          - ``u`` - the normalizing scalar (only if ``with_scalar=True``)
  
          - ``i`` - the index of `(c, d)` in the list.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 31)
              sage: N = k.ideal(5, a + 3)
              sage: P = P1NFList(N)
              sage: P.index(3,a)
              5
              sage: P[5]==MSymbol(N, 3, a).normalize()
              True
  
          We can give an MSymbol as input:
  
          ::
  
              sage: alpha = MSymbol(N, 3, a)
              sage: P.index(alpha)
              5
  
          We cannot look for the class of an MSymbol of a different level:
  
          ::
  
              sage: M = k.ideal(a + 1)
              sage: beta = MSymbol(M, 0, 1)
              sage: P.index(beta)
              Traceback (most recent call last):
              ...
              ValueError: The MSymbol is of a different level
  
          If we are interested in the transforming scalar:
  
          ::
  
              sage: alpha = MSymbol(N, 3, a)
              sage: P.index(alpha, with_scalar=True)
              (-a, 5)
              sage: u, i = P.index(alpha, with_scalar=True)
              sage: (u*P[i].c - alpha.c in N) and (u*P[i].d - alpha.d in N)
              True
          """
          if d is None:
              try:
                  c = MSymbol(self.__N, c) # check that c is an MSymbol
              except ValueError: # catch special case of wrong level
                  raise ValueError("The MSymbol is of a different level")
              if with_scalar:
                  u, norm_c = c.normalize(with_scalar=True)
              else:
                  norm_c = c.normalize()
          else:
              if with_scalar:
                  u, norm_c = MSymbol(self.__N, c, d).normalize(with_scalar=True)
              else:
                  norm_c = MSymbol(self.__N, c, d).normalize()
          t, i = search(self.__list, norm_c)
          if t:
              if with_scalar:
                  return u, i
              else:
                  return i
          return False
  
      def index_of_normalized_pair(self, c, d=None):
          """
          Returns the index of the class `(c, d)` in the fixed list of
          representatives of `\mathbb(P)^1(R/N)`.
  
          INPUT:
  
          - ``c`` -- integral element of the corresponding number field, or a
            normalized MSymbol.
  
          - ``d`` -- (optional) when present, it must be an integral element of
            the number field such that `(c, d)` defines a normalized M-symbol of
            level `N`.
  
          OUTPUT:
  
          - ``i`` - the index of `(c, d)` in the list.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 31)
              sage: N = k.ideal(5, a + 3)
              sage: P = P1NFList(N)
              sage: P.index_of_normalized_pair(1, 0)
              3
              sage: j = randint(0,len(P)-1)
              sage: P.index_of_normalized_pair(P[j])==j
              True
          """
          if d is None:
              try:
                  c = MSymbol(self.__N, c) # check that c is an MSymbol
              except ValueError: # catch special case of wrong level
                  raise ValueError("The MSymbol is of a different level")
              t, i = search(self.__list, c)
          else:
              t, i = search(self.__list, MSymbol(self.__N, c, d))
          if t: return i
          return False
  
      def lift_to_sl2_Ok(self, i):
          """
          Lift the `i`-th element of this P1NFList to an element of `SL(2, R)`,
          where `R` is the ring of integers of the corresponding number field.
  
          INPUT:
  
          - ``i`` - integer (index of the element to lift)
  
          OUTPUT:
  
          If the `i`-th element is `(c : d)`, the function returns a list of
          integral elements `[a, b, c', d']` that defines a 2x2 matrix with
          determinant 1 and such that `c=c'` (mod `N`) and `d=d'` (mod `N`).
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^2 + 23)
              sage: N = k.ideal(3)
              sage: P = P1NFList(N)
              sage: len(P)
              16
              sage: P[5]
              M-symbol (1/2*a + 1/2: -a) of level Fractional ideal (3)
              sage: P.lift_to_sl2_Ok(5)
              [1, -2, 1/2*a + 1/2, -a]
  
          ::
  
              sage: Ok = k.ring_of_integers()
              sage: L = [Matrix(Ok, 2, P.lift_to_sl2_Ok(i)) for i in range(len(P))]
              sage: all([det(L[i]) == 1 for i in range(len(L))])
              True
          """
          return self[i].lift_to_sl2_Ok()
  
      def apply_S(self, i):
          """
          Applies the matrix S = [0, -1, 1, 0] to the i-th M-Symbol of the list.
  
          INPUT:
  
          - ``i`` -- integer
  
          OUTPUT:
  
          integer -- the index of the M-Symbol obtained by the right action of
          the matrix S = [0, -1, 1, 0] on the i-th M-Symbol.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^3 + 11)
              sage: N = k.ideal(5, a + 1)
              sage: P = P1NFList(N)
              sage: j = P.apply_S(P.index_of_normalized_pair(1, 0))
              sage: P[j]
              M-symbol (0: 1) of level Fractional ideal (5, a + 1)
  
          We test that S has order 2:
  
          ::
  
              sage: j = randint(0,len(P)-1)
              sage: P.apply_S(P.apply_S(j))==j
              True
          """
          c, d = self.__list[i].tuple()
          t, j = search(self.__list, self.normalize(d, -c))
          return j
  
      def apply_TS(self, i):
          """
          Applies the matrix TS = [1, -1, 0, 1] to the i-th M-Symbol of the list.
  
          INPUT:
  
          - ``i`` -- integer
  
          OUTPUT:
  
          integer -- the index of the M-Symbol obtained by the right action of
          the matrix TS = [1, -1, 0, 1] on the i-th M-Symbol.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^3 + 11)
              sage: N = k.ideal(5, a + 1)
              sage: P = P1NFList(N)
              sage: P.apply_TS(3)
              2
  
          We test that TS has order 3:
  
          ::
  
              sage: j = randint(0,len(P)-1)
              sage: P.apply_TS(P.apply_TS(P.apply_TS(j)))==j
              True
          """
          c, d = self.__list[i].tuple()
          t, j = search(self.__list, self.normalize(c + d, -c))
          return j
  
      def apply_T_alpha(self, i, alpha=1):
          """
          Applies the matrix T_alpha = [1, alpha, 0, 1] to the i-th M-Symbol of
          the list.
  
          INPUT:
  
          - ``i`` -- integer
  
          - ``alpha`` -- element of the corresponding ring of integers(default 1)
  
          OUTPUT:
  
          integer -- the index of the M-Symbol obtained by the right action of
          the matrix T_alpha = [1, alpha, 0, 1] on the i-th M-Symbol.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^3 + 11)
              sage: N = k.ideal(5, a + 1)
              sage: P = P1NFList(N)
              sage: P.apply_T_alpha(4, a^ 2 - 2)
              3
  
          We test that T_a*T_b = T_(a+b):
  
          ::
  
              sage: P.apply_T_alpha(3, a^2 - 2)==P.apply_T_alpha(P.apply_T_alpha(3,a^2),-2)
              True
          """
          c, d = self.__list[i].tuple()
          t, j = search(self.__list, self.normalize(c, alpha*c + d))
          return j
  
      def apply_J_epsilon(self, i, e1, e2=1):
          """
          Applies the matrix `J_{\epsilon}` = [e1, 0, 0, e2] to the i-th
          M-Symbol of the list.
  
          e1, e2 are units of the underlying number field.
  
          INPUT:
  
          - ``i`` -- integer
  
          - ``e1`` -- unit
  
          - ``e2`` -- unit (default 1)
  
          OUTPUT:
  
          integer -- the index of the M-Symbol obtained by the right action of
          the matrix `J_{\epsilon}` = [e1, 0, 0, e2] on the i-th M-Symbol.
  
          EXAMPLES::
  
              sage: k.<a> = NumberField(x^3 + 11)
              sage: N = k.ideal(5, a + 1)
              sage: P = P1NFList(N)
              sage: u = k.unit_group().gens_values(); u
              [-1, 2*a^2 + 4*a - 1]
              sage: P.apply_J_epsilon(4, -1)
              2
              sage: P.apply_J_epsilon(4, u[0], u[1])
              1
  
          ::
  
              sage: k.<a> = NumberField(x^4 + 13*x - 7)
              sage: N = k.ideal(a + 1)
              sage: P = P1NFList(N)
              sage: u = k.unit_group().gens_values(); u
              [-1, a^3 + a^2 + a + 12, a^3 + 3*a^2 - 1]
              sage: P.apply_J_epsilon(3, u[2]^2)==P.apply_J_epsilon(P.apply_J_epsilon(3, u[2]),u[2])
              True
          """
          c, d = self.__list[i].tuple()
          t, j = search(self.__list, self.normalize(c*e1, d*e2))
          return j
  
  
  #**************************************************************************
  #  Global functions:
  #    - p1NFList --compute list of M-symbols
  #    - lift_to_sl2_Ok
  #    - make_coprime -- need it for ``lift_to_sl2_Ok``
  #    - psi -- useful to check cardinality of the M-symbols list
  #**************************************************************************
  
  def p1NFlist(N):
      """
      Returns a list of the normalized elements of `\\mathbb{P}^1(R/N)`, where
      `N` is an integral ideal.
  
      INPUT:
  
      -  ``N`` - integral ideal (the level or modulus).
  
      EXAMPLES::
  
          sage: k.<a> = NumberField(x^2 + 23)
          sage: N = k.ideal(3)
          sage: from sage.modular.modsym.p1list_nf import p1NFlist, psi
          sage: len(p1NFlist(N))==psi(N)
          True
      """
      k = N.number_field()
  
      L = [MSymbol(N, k(0),k(1), check=False)]
      #N.residues() = iterator through the residues mod N
      L = L+[MSymbol(N, k(1), r, check=False) for r in N.residues()]
  
      from sage.rings.arith import divisors
      for D in divisors(N):
          if not D.is_trivial() and D!=N:
              #we find Dp ideal coprime to N, in inverse class to D
              if D.is_principal():
                  Dp = k.ideal(1)
                  c = D.gens_reduced()[0]
              else:
                  it = k.primes_of_degree_one_iter()
                  Dp = it.next()
                  while not Dp.is_coprime(N) or not (Dp*D).is_principal():
                      Dp = it.next()
                  c = (D*Dp).gens_reduced()[0]
              #now we find all the (c,d)'s which have associated divisor D
              I = D + N/D
              for d in (N/D).residues():
                  if I.is_coprime(d):
                      M = D.prime_to_idealM_part(N/D)
                      u = (Dp*M).element_1_mod(N/D)
                      d1 = u*d + (1-u)
                      L.append(MSymbol(N, c, d1, check=False).normalize())
      return L
  
  def lift_to_sl2_Ok(N, c, d):
      """
      Lift a pair (c, d) to an element of `SL(2, O_k)`, where `O_k` is the ring
      of integers of the corresponding number field.
  
      INPUT:
  
      - ``N`` -- number field ideal
  
      - ``c`` -- integral element of the number field
  
      - ``d`` -- integral element of the number field
  
      OUTPUT:
  
      A list [a, b, c', d'] of integral elements that are the entries of
      a 2x2 matrix with determinant 1. The lower two entries are congruent to
      c, d modulo the ideal `N`.
  
  
      EXAMPLES::
  
          sage: from sage.modular.modsym.p1list_nf import lift_to_sl2_Ok
          sage: k.<a> = NumberField(x^2 + 23)
          sage: Ok = k.ring_of_integers(k)
          sage: N = k.ideal(3)
          sage: M = Matrix(Ok, 2, lift_to_sl2_Ok(N, 1, a))
          sage: det(M)
          1
          sage: M = Matrix(Ok, 2, lift_to_sl2_Ok(N, 0, a))
          sage: det(M)
          1
          sage: (M[1][0] in N) and (M[1][1] - a in N)
          True
          sage: M = Matrix(Ok, 2, lift_to_sl2_Ok(N, 0, 0))
          Traceback (most recent call last):
          ...
          ValueError: Cannot lift (0, 0) to an element of Sl2(Ok).
  
      ::
  
          sage: k.<a> = NumberField(x^3 + 11)
          sage: Ok = k.ring_of_integers(k)
          sage: N = k.ideal(3, a - 1)
          sage: M = Matrix(Ok, 2, lift_to_sl2_Ok(N, 2*a, 0))
          sage: det(M)
          1
          sage: (M[1][0] - 2*a in N) and (M[1][1] in N)
          True
          sage: M = Matrix(Ok, 2, lift_to_sl2_Ok(N, 4*a^2, a + 1))
          sage: det(M)
          1
          sage: (M[1][0] - 4*a^2 in N) and (M[1][1] - (a+1) in N)
          True
  
      ::
  
          sage: k.<a> = NumberField(x^4 - x^3 -21*x^2 + 17*x + 133)
          sage: Ok = k.ring_of_integers(k)
          sage: N = k.ideal(7, a)
          sage: M = Matrix(Ok, 2, lift_to_sl2_Ok(N, 0, a^2 - 1))
          sage: det(M)
          1
          sage: (M[1][0] in N) and (M[1][1] - (a^2-1) in N)
          True
          sage: M = Matrix(Ok, 2, lift_to_sl2_Ok(N, 0, 7))
          Traceback (most recent call last):
          ...
          ValueError: <0> + <7> and the Fractional ideal (7, a) are not coprime.
      """
      k = N.number_field()
      #check the input
      if c.is_zero() and d.is_zero():
          raise ValueError("Cannot lift (%s, %s) to an element of Sl2(Ok)."%(c, d))
      if not N.is_coprime(k.ideal(c, d)):
          raise ValueError("<%s> + <%s> and the %s are not coprime."%(c, d, N))
      #a few special cases
      if c - 1 in N:
          return [k(0), k(-1), 1, d]
      if d - 1 in N:
          return [k(1), k(0), c, 1]
      if c.is_zero(): # and d!=1, so won't happen for normalized M-symbols (c: d)
          it = k.primes_of_degree_one_iter()
          q = k.ideal(1)
          while not (q.is_coprime(d) and (q*N).is_principal()):
              q = it.next()
          m = (q*N).gens_reduced()[0]
          B = k.ideal(m).element_1_mod(k.ideal(d))
          return [(1-B)/d, -B/m, m, d]
      if d.is_zero(): # and c!=1, so won't happen for normalized M-symbols (c: d)
          it = k.primes_of_degree_one_iter()
          q = k.ideal(1)
          while not (q.is_coprime(c) and (q*N).is_principal()):
              q = it.next()
          m = (q*N).gens_reduced()[0]
          B = k.ideal(c).element_1_mod(k.ideal(m))
          return [(1-B)/m, -B/c, c, m]
  
      c, d = make_coprime(N, c, d)
  
      B = k.ideal(c).element_1_mod(k.ideal(d))
      b = -B/c
      a = (1-B)/d
      return [a, b, c, d]
  
  def make_coprime(N, c, d):
      """
      Returns (c, d') so d' is congruent to d modulo N, and such that c and d' are
      coprime (<c> + <d'> = R).
  
      INPUT:
  
      - ``N`` -- number field ideal
  
      - ``c`` -- integral element of the number field
  
      - ``d`` -- integral element of the number field
  
      OUTPUT:
  
      A pair (c, d') where c, d' are integral elements of the corresponding
      number field, with d' congruent to d mod N, and such that <c> + <d'> = R
      (R being the corresponding ring of integers).
  
      EXAMPLES::
  
          sage: from sage.modular.modsym.p1list_nf import make_coprime
          sage: k.<a> = NumberField(x^2 + 23)
          sage: N = k.ideal(3, a - 1)
          sage: c = 2*a; d = a + 1
          sage: N.is_coprime(k.ideal(c, d))
          True
          sage: k.ideal(c).is_coprime(d)
          False
          sage: c, dp = make_coprime(N, c, d)
          sage: k.ideal(c).is_coprime(dp)
          True
      """
      k = N.number_field()
      if k.ideal(c).is_coprime(d):
          return c, d
      else:
          q = k.ideal(c).prime_to_idealM_part(d)
          it = k.primes_of_degree_one_iter()
          r = k.ideal(1)
          qN = q*N
          while not (r.is_coprime(c) and (r*qN).is_principal()):
              r = it.next()
          m = (r*qN).gens_reduced()[0]
          d1 = d + m
          return c, d1
  
  def psi(N):
      """
      The index `[\Gamma : \Gamma_0(N)]`, where `\Gamma = GL(2, R)` for `R` the
      corresponding ring of integers, and `\Gamma_0(N)` standard congruence
      subgroup.
  
      EXAMPLES::
  
          sage: from sage.modular.modsym.p1list_nf import psi
          sage: k.<a> = NumberField(x^2 + 23)
          sage: N = k.ideal(3, a - 1)
          sage: psi(N)
          4
  
      ::
  
          sage: k.<a> = NumberField(x^2 + 23)
          sage: N = k.ideal(5)
          sage: psi(N)
          26
      """
      if not N.is_integral():
          raise ValueError("psi only defined for integral ideals")
  
      from sage.misc.misc import prod
      return prod([(np+1)*np**(e-1) \
                       for np,e in [(p.absolute_norm(),e) \
                                    for p,e in N.factor()]])
  