def coefficient(self, P):
        """
        Return the coefficient of a given point P in this divisor.

        EXAMPLES::

            sage: x,y = AffineSpace(2, GF(5), names='xy').gens()
            sage: C = Curve(y^2 - x^9 - x)
            sage: pts = C.rational_points(); pts
            [(0, 0), (2, 2), (2, 3), (3, 1), (3, 4)]
            sage: D = C.divisor(pts[0])
            sage: D.coefficient(pts[0])
            1
            sage: D = C.divisor([(3,pts[0]), (-1,pts[1])]); D
            3*(x, y) - (x - 2, y - 2)
            sage: D.coefficient(pts[0])
            3
            sage: D.coefficient(pts[1])
            -1
        """
        P = self.parent().scheme()(P)
        if not(P in self.support()):
            return self.base_ring().zero()
        t, i = search(self.support(), P)
        assert t
        try:
            return self._points[i][0]
        except AttributeError:
                raise NotImplementedError

    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_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_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 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 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

def gens_to_basis_matrix(syms, relation_matrix, mod, field, sparse):
    """
    Compute echelon form of 3-term relation matrix, and read off each
    generator in terms of basis.

    INPUT:

    -  ``syms`` - a ManinSymbols object

    -  ``relation_matrix`` - as output by
       ``__compute_T_relation_matrix(self, mod)``

    -  ``mod`` - quotient of modular symbols modulo the
       2-term S (and possibly I) relations

    -  ``field`` - base field

    -  ``sparse`` - (bool): whether or not matrix should be
       sparse

    OUTPUT:

    -  ``matrix`` - a matrix whose ith row expresses the
       Manin symbol generators in terms of a basis of Manin symbols
       (modulo the S, (possibly I,) and T rels) Note that the entries of
       the matrix need not be integers.

    -  ``list`` - integers i, such that the Manin symbols `x_i` are a basis.

    EXAMPLE::

        sage: from sage.modular.modsym.relation_matrix import *
        sage: L = sage.modular.modsym.manin_symbols.ManinSymbolList_gamma1(4, 3)
        sage: modS = sparse_2term_quotient(modS_relations(L), 24, GF(3))
        sage: gens_to_basis_matrix(L, T_relation_matrix_wtk_g0(L, modS, GF(3), 24), modS, GF(3), True)
        (24 x 2 sparse matrix over Finite Field of size 3, [13, 23])
    """
    from sage.matrix.matrix import is_Matrix
    if not is_Matrix(relation_matrix):
        raise TypeError("relation_matrix must be a matrix")
    if not isinstance(mod, list):
        raise TypeError("mod must be a list")

    misc.verbose(str(relation_matrix.parent()))

    try:
        h = relation_matrix.height()
    except AttributeError:
        h = 9999999
    tm = misc.verbose("putting relation matrix in echelon form (height = %s)"%h)
    if h < 10:
        A = relation_matrix.echelon_form(algorithm='multimodular', height_guess=1)
    else:
        A = relation_matrix.echelon_form()
    A.set_immutable()
    tm = misc.verbose('finished echelon', tm)

    tm = misc.verbose("Now creating gens --> basis mapping")

    basis_set = set(A.nonpivots())
    pivots = A.pivots()

    basis_mod2 = set([j for j,c in mod if c != 0])

    basis_set = basis_set.intersection(basis_mod2)
    basis = sorted(basis_set)

    ONE = field(1)

    misc.verbose("done doing setup",tm)


    tm = misc.verbose("now forming quotient matrix")
    M = matrix_space.MatrixSpace(field, len(syms), len(basis), sparse=sparse)

    B = M(0)
    cols_index = dict([(basis[i], i) for i in range(len(basis))])

    for i in basis_mod2:
        t, l = search(basis, i)
        if t:
            B[i,l] = ONE
        else:
            _, r = search(pivots, i)    # so pivots[r] = i
            # Set row i to -(row r of A), but where we only take
            # the non-pivot columns of A:
            B._set_row_to_negative_of_row_of_A_using_subset_of_columns(i, A, r, basis, cols_index)

    misc.verbose("done making quotient matrix",tm)

    # The following is very fast (over Q at least).
    tm = misc.verbose('now filling in the rest of the matrix')
    k = 0
    for i in range(len(mod)):
        j, s = mod[i]
        if j != i and s != 0:   # ignored in the above matrix
            k += 1
            B.set_row_to_multiple_of_row(i, j, s)
    misc.verbose("set %s rows"%k)
    tm = misc.verbose("time to fill in rest of matrix", tm)
#.........这里部分代码省略.........

    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