def ncusps(self):
        r"""
        Return the number of orbits of cusps (regular or otherwise) for this subgroup.

        EXAMPLE::

            sage: GammaH(33,[2]).ncusps()
            8
            sage: GammaH(32079, [21676]).ncusps()
            28800

        AUTHORS:

        - Jordi Quer

        """
        N = self.level()
        H = self._list_of_elements_in_H()
        c = ZZ(0)
        for d in [d for d in N.divisors() if d**2 <= N]:
            Nd = lcm(d,N//d)
            Hd = set([x % Nd for x in H])
            lenHd = len(Hd)
            if Nd-1 not in Hd: lenHd *= 2
            summand = euler_phi(d)*euler_phi(N//d)//lenHd
            if d**2 == N:
                c = c + summand
            else:
                c = c + 2*summand
        return c

def num_cusps_of_width(N, d):
    r"""
    Return the number of cusps on `X_0(N)` of width d.

    INPUT:


    -  ``N`` - (integer): the level

    -  ``d`` - (integer): an integer dividing N, the cusp
       width


    EXAMPLES::

        sage: [num_cusps_of_width(18,d) for d in divisors(18)]
        [1, 1, 2, 2, 1, 1]
        sage: num_cusps_of_width(4,8)
        Traceback (most recent call last):
        ...
        ValueError: N and d must be positive integers with d|N
    """
    N = ZZ(N)
    d = ZZ(d)
    if N <= 0 or d <= 0 or (N % d) != 0:
        raise ValueError("N and d must be positive integers with d|N")

    return euler_phi(gcd(d, N//d))

def num_cusps_of_width(N, d):
    r"""
    Return the number of cusps on `X_0(N)` of width d.

    INPUT:


    -  ``N`` - (integer): the level

    -  ``d`` - (integer): an integer dividing N, the cusp
       width


    EXAMPLES::

        sage: [num_cusps_of_width(18,d) for d in divisors(18)]
        [1, 1, 2, 2, 1, 1]
    """
    try:
        N = ZZ(N)
        d = ZZ(d)
        assert N>0
        assert d>0
        assert ((N % d) == 0)
    except TypeError:
        raise TypeError, "N and d must be integers"
    except AssertionError:
        raise AssertionError, "N and d must be positive integers with d|N"

    return euler_phi(gcd(d, N//d))

    def cardinality(self):
        """
        Returns the number of integer necklaces with the evaluation e.
        
        EXAMPLES::
        
            sage: Necklaces([]).cardinality()
            0
            sage: Necklaces([2,2]).cardinality()
            2
            sage: Necklaces([2,3,2]).cardinality()
            30
        
        Check to make sure that the count matches up with the number of
        Lyndon words generated.
        
        ::
        
            sage: comps = [[],[2,2],[3,2,7],[4,2]]+Compositions(4).list()
            sage: ns = [ Necklaces(comp) for comp in comps]
            sage: all( [ n.cardinality() == len(n.list()) for n in ns] )
            True
        """
        evaluation = self.e
        le = list(evaluation)
        if len(le) == 0:
            return 0

        n = sum(le)

        return sum([euler_phi(j)*factorial(n/j) / prod([factorial(ni/j) for ni in evaluation]) for j in divisors(gcd(le))])/n

    def nu2(self):
        r"""
        Return the number of orbits of elliptic points of order 2 for this
        group.

        EXAMPLE::

            sage: [H.nu2() for n in [1..10] for H in Gamma0(n).gamma_h_subgroups()]
            [1, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0]
            sage: GammaH(33,[2]).nu2()
            0
            sage: GammaH(5,[2]).nu2()
            2

        AUTHORS:

        - Jordi Quer

        """
        N = self.level()
        H = self._list_of_elements_in_H()
        if N % 4 == 0: return ZZ(0)
        for p, r in N.factor():
            if p % 4 == 3: return ZZ(0)
        return (euler_phi(N) // len(H))*len([x for x in H if (x**2 + 1) % N == 0])

    def nu3(self):
        r"""
        Return the number of orbits of elliptic points of order 3 for this
        group.

        EXAMPLE::

            sage: [H.nu3() for n in [1..10] for H in Gamma0(n).gamma_h_subgroups()]
            [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
            sage: GammaH(33,[2]).nu3()
            0
            sage: GammaH(7,[2]).nu3()
            2

        AUTHORS:

        - Jordi Quer

        """
        N = self.level()
        H = self._list_of_elements_in_H()
        if N % 9 == 0: return ZZ(0)
        for p, r in N.factor():
            if p % 3 == 2: return ZZ(0)
        lenHpm = len(H)
        if N - ZZ(1) not in H: lenHpm*=2
        return (euler_phi(N)//lenHpm)*len([x for x in H if (x**2+x+1) % N == 0])

def GammaH_constructor(level, H):
    r"""
    Return the congruence subgroup `\Gamma_H(N)`, which is the subgroup of
    `SL_2(\ZZ)` consisting of matrices of the form `\begin{pmatrix} a & b \\
    c & d \end{pmatrix}` with `N | c` and `a, b \in H`, for `H` a specified
    subgroup of `(\ZZ/N\ZZ)^\times`.

    INPUT:

    - level -- an integer
    - H -- either 0, 1, or a list
        * If H is a list, return `\Gamma_H(N)`, where `H`
          is the subgroup of `(\ZZ/N\ZZ)^*` **generated** by the
          elements of the list.
        * If H = 0, returns `\Gamma_0(N)`.
        * If H = 1, returns `\Gamma_1(N)`.

    EXAMPLES::

        sage: GammaH(11,0) # indirect doctest
        Congruence Subgroup Gamma0(11)
        sage: GammaH(11,1)
        Congruence Subgroup Gamma1(11)
        sage: GammaH(11,[10])
        Congruence Subgroup Gamma_H(11) with H generated by [10]
        sage: GammaH(11,[10,1])
        Congruence Subgroup Gamma_H(11) with H generated by [10]
        sage: GammaH(14,[10])
        Traceback (most recent call last):
        ...
        ArithmeticError: The generators [10] must be units modulo 14
    """
    from all import Gamma0, Gamma1, SL2Z
    if level == 1:
        return SL2Z
    elif H == 0:
        return Gamma0(level)
    elif H == 1:
        return Gamma1(level)

    H = _normalize_H(H, level)
    if H == []:
        return Gamma1(level)

    Hlist = _list_subgroup(level, H)
    if len(Hlist) == euler_phi(level):
        return Gamma0(level)

    key = (level, tuple(H))
    try:
        return _gammaH_cache[key]
    except KeyError:
        _gammaH_cache[key] = GammaH_class(level, H, Hlist)
        return _gammaH_cache[key]

    def unit_group_order(self):
        """
        Return the order of the unit group of this residue class ring.

        EXAMPLES::

            sage: R = Integers(500)
            sage: R.unit_group_order()
            200
        """
        return euler_phi(self.order())

    def ncusps(self):
        r"""
        Return the number of cusps of this subgroup `\Gamma_0(N)`.

        EXAMPLES::

            sage: [Gamma0(n).ncusps() for n in [1..19]]
            [1, 2, 2, 3, 2, 4, 2, 4, 4, 4, 2, 6, 2, 4, 4, 6, 2, 8, 2]
            sage: [Gamma0(n).ncusps() for n in prime_range(2,100)]
            [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
        """
        n = self.level()
        return sum([arith.euler_phi(arith.gcd(d,n//d)) for d in n.divisors()])

    def nregcusps(self):
        r"""
        Return the number of orbits of regular cusps for this subgroup. A cusp is regular
        if we may find a parabolic element generating the stabiliser of that
        cusp whose eigenvalues are both +1 rather than -1. If G contains -1,
        all cusps are regular.

        EXAMPLES::

            sage: GammaH(20, [17]).nregcusps()
            4
            sage: GammaH(20, [17]).nirregcusps()
            2
            sage: GammaH(3212, [2045, 2773]).nregcusps()
            1440
            sage: GammaH(3212, [2045, 2773]).nirregcusps()
            720

        AUTHOR:

        - Jordi Quer
        """
        if self.is_even():
            return self.ncusps()

        N = self.level()
        H = self._list_of_elements_in_H()

        c = ZZ(0)
        for d in [d for d in divisors(N) if d**2 <= N]:
            Nd = lcm(d,N//d)
            Hd = set([x%Nd for x in H])
            if Nd - 1 not in Hd:
                summand = euler_phi(d)*euler_phi(N//d)//(2*len(Hd))
                if d**2==N:
                    c = c + summand
                else:
                    c = c + 2*summand
        return c

    def __init__(self, N, q, D, poly=None, secret_dist='uniform', m=None):
        """
        Construct a Ring-LWE oracle in dimension ``n=phi(N)`` over a ring of order
        ``q`` with noise distribution ``D``.

        INPUT:

        - ``N`` - index of cyclotomic polynomial (integer > 0, must be power of 2)
        - ``q`` - modulus typically > N (integer > 0)
        - ``D`` - an error distribution such as an instance of
          :class:`DiscreteGaussianDistributionPolynomialSampler` or :class:`UniformSampler`
        - ``poly`` - a polynomial of degree ``phi(N)``. If ``None`` the
          cyclotomic polynomial used (default: ``None``).
        - ``secret_dist`` - distribution of the secret. See documentation of
          :class:`LWE` for details (default='uniform')
        - ``m`` - number of allowed samples or ``None`` if no such limit exists
          (default: ``None``)

        EXAMPLE::

            sage: from sage.crypto.lwe import RingLWE
            sage: from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler
            sage: D = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], n=euler_phi(20), sigma=3.0)
            sage: RingLWE(N=20, q=next_prime(800), D=D);
            RingLWE(20, 809, Discrete Gaussian sampler for polynomials of degree < 8 with σ=3.000000 in each component, x^8 - x^6 + x^4 - x^2 + 1, 'uniform', None)
        """
        self.N  = ZZ(N)
        self.n = euler_phi(N)
        self.m =  m
        self.__i = 0
        self.K  = IntegerModRing(q)

        if self.n != D.n:
            raise ValueError("Noise distribution has dimensions %d != %d"%(D.n, self.n))

        self.D = D
        self.q = q
        if poly is not None:
            self.poly = poly
        else:
            self.poly = cyclotomic_polynomial(self.N, 'x')

        self.R_q = self.K['x'].quotient(self.poly, 'x')

        self.secret_dist = secret_dist
        if secret_dist == 'uniform':
            self.__s = self.R_q.random_element()  # uniform sampling of secret
        elif secret_dist == 'noise':
            self.__s = self.D()
        else:
            raise TypeError("Parameter secret_dist=%s not understood."%(secret_dist))

def find_m(n, k, bound = None):
    '''
    INPUT : an integers n, a base field k, an integer bound

    OUTPUT : an integer

    Algorithm :

    Functions that given an integer n (degree of an extension) and a bound 
    returns all the candidates m, such that :

    - n|phi(m), the euler totient function,

    - (n, phi(m)/n) = 1,

    - Another one ? Maybe for q = p^d we'd want (n,d) = 1,

    We can note that if m = r^e with (e-1,n) = 1 or e = 1, then r = a*n + 1 with
    (a,n) = 1 is a suitable form for m as then phi(m) = (a*n)(an + 1)^(e-1);

    It also works in the general case if all the prime factors of m are of the 
    form a*n + 1 with (a,n) = 1. You just have to apply that to them and 
    multiply the results.
    '''
    if bound is None:
        bound_a = 100 # Arbitrary value.  
    else:
        # if m = a*n + 1 < b, then a < (b- 1)/n.
        bound_a = (bound - 1) / n 

    sol = []

    for a in range(bound_a):
        m = a*n + 1
        # m composite not implemented yet
        if not m.is_prime_power():
            continue 
        elif (euler_phi(m)/n).gcd(n) != 1:
            continue
        else:
            S_t = find_trace(n, m, k)
            if len(S_t) < 1:   # Some time in the future we'd like to have a 
                continue       # better bound than just 1.
            else:
                return m, S_t

    def cardinality(self):
        r"""
        Return the number of integer necklaces with the evaluation ``content``.

        The formula for the number of necklaces of content `\alpha`
        a composition of `n` is:

        .. MATH::

            \sum_{d|gcd(\alpha)} \phi(d)
            \binom{n/d}{\alpha_1/d, \ldots, \alpha_\ell/d},

        where `\phi(d)` is the Euler `\phi` function.

        EXAMPLES::

            sage: Necklaces([]).cardinality()
            0
            sage: Necklaces([2,2]).cardinality()
            2
            sage: Necklaces([2,3,2]).cardinality()
            30
            sage: Necklaces([0,3,2]).cardinality()
            2

        Check to make sure that the count matches up with the number of
        necklace words generated.

        ::

            sage: comps = [[],[2,2],[3,2,7],[4,2],[0,4,2],[2,0,4]]+Compositions(4).list()
            sage: ns = [ Necklaces(comp) for comp in comps]
            sage: all( [ n.cardinality() == len(n.list()) for n in ns] )
            True
        """
        evaluation = self._content
        le = list(evaluation)
        if not le:
            return 0

        n = sum(le)

        return sum(euler_phi(j)*factorial(n/j) / prod(factorial(ni/j)
                    for ni in evaluation) for j in divisors(gcd(le))) / n

def processDirichletNavigation(args):
    s = '<table>\n'
    s += '<tr>\n<th scope="col">Characters</th>\n</tr>\n'
    for i in range(0, euler_phi(modulus)):
        s += '<tr>\n<th scope="row">' + str(i) + '</th>\n'
        s += '<td>\n'
        j = i - N
        for k in range(len(chars[j][1])):
            s += '<a style=\'display:inline\' href="Character/Dirichlet/'
            s += str(i)
            s += '/'
            s += str(chars[j][1][k])
            s += '/&numcoeff='
            s += str(numcoeff)
            s += '">'
            s += '\(\chi_{' + str(chars[j][1][k]) + '}\)</a> '
        s += '</td>\n</tr>\n'
    s += '</table>\n'
    return s

    def __cmp__(self, other):
        """
        Compare self to other.

        The ordering on congruence subgroups of the form GammaH(N) for
        some H is first by level and then by the subgroup H. In
        particular, this means that we have Gamma1(N) < GammaH(N) <
        Gamma0(N) for every nontrivial subgroup H.

        EXAMPLES::

            sage: G = Gamma0(86)
            sage: G.__cmp__(G)
            0
            sage: G.__cmp__(GammaH(86, [11])) is not 0
            True
            sage: Gamma1(17) < Gamma0(17)
            True
            sage: Gamma0(1) == SL2Z
            True
            sage: Gamma0(11) == GammaH(11, [2])
            True
            sage: Gamma0(2) == Gamma1(2) 
            True
        """
        if not is_CongruenceSubgroup(other):
            return cmp(type(self), type(other))

        c = cmp(self.level(), other.level())
        if c: return c

        # Since Gamma0(N) is GammaH(N) for H all of (Z/N)^\times,
        # we know how to compare it to any other GammaH without having
        # to look at self._list_of_elements_in_H().
        from all import is_GammaH, is_Gamma0
        if is_GammaH(other):
            if is_Gamma0(other):
                return 0
            else:
                H = other._list_of_elements_in_H()
                return cmp(len(H), arith.euler_phi(self.level()))
        return cmp(type(self), type(other))

def _GammaH_coset_helper(N, H):
    r"""
    Return a list of coset representatives for H in (Z / NZ)^*.

    EXAMPLE::

        sage: from sage.modular.arithgroup.congroup_gammaH import _GammaH_coset_helper
        sage: _GammaH_coset_helper(108, [1, 107])
        [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53]
    """
    t = [Zmod(N)(1)]
    W = [Zmod(N)(h) for h in H]
    HH = [Zmod(N)(h) for h in H]
    k = euler_phi(N)

    for i in xrange(1, N):
        if gcd(i, N) != 1: continue
        if not i in W:
            t.append(t[0]*i)
            W = W + [i*h for h in HH]
            if len(W) == k: break
    return t

def find_unique_orbit_elliptic(E, m, case = 0, one_element = 0):
    '''
    INPUT : 
    
    - ``E`` -- an elliptic curve with the properties given in isom_elliptic 
      and/or find_elliptic_curve.

    - ``m`` -- an integer with the properties given in isom_elliptic and/or in 
      find_m.

    - ``case`` -- integer (default : 0) depends on the j-invariant's value :
        - ``0`` means j is not 0 nor 1728 or E is supersingular,
        - ``1`` means j is 1728,
        - ``2`` means j is 0.

    OUPUT : 
    
    - An element in the field K_E over which E is defined, with a unique orbit 
      under the action of the Galois group  K_E/k.

    EXAMPLES :

    - Case j != 0, 1728

        sage: E = EllipticCurve(j = GF(5)(1))

        sage: EK = E.change_ring(GF(5**19, prefix = 'z', conway = True)

        sage: m = 229

        sage: elem1 = find_unique_orbit_elliptic(EK,m)

        sage: elem2 = find_unique_orbit_elliptic(EK,m)

        sage: elem1.minpoly() == elem2.minpoly()

        True

    - Case j = 1728 and trace != 0

        sage : E = EllipticCurve(j = GF(5)(1728))

        sage: EK = E.change_ring(GF(5**19, prefix = 'z', conway = True)

        sage: m = 229

        sage: elem1 = find_unique_orbit_elliptic(EK,m)

        sage: elem2 = find_unique_orbit_elliptic(EK,m)

        sage: elem1.minpoly() == elem2.minpoly()

        True

    - Case j = 0 and trace != 0

        sage: E = EllipticCurve(j = GF(7)(0))

        sage: EK = E.change_ring(GF(7**23, prefix = 'z', conway = True)

        sage: m = 139

        sage: elem1 = find_unique_orbit_elliptic(EK,m)

        sage: elem2 = find_unique_orbit_elliptic(EK,m)

        sage: elem1.minpoly() == elem2.minpoly()

        True

    ALGORITHM:

    From a point of order m on E/GF(q^n), we use its abscissas to generate a 
    uniquely defined element. To defined such element, we need to calculate 
    periods of the Galois action. The trace of the elliptic curve we are using 
    is of the form t = a + q/a, with a of order n in (Z/m)*. So for S a subgroup
    of the Galois groupe, we have (Z/m)* = <a> x S. To compute the elliptic
    periods, we use the formulas :

        - u = sum_{i \in S} (([i]P)[0])^2, for j not 0 nor 1728 or t = 0,
        - u = sum_{i \in S} (([i]P)[0])^4, for j = 1728,
        - u = sum_{i \in S} (([i]P)[0])^6, for j = 0.
    '''
    n = E.base_ring().degree()
    p = E.base_ring().characteristic()

    # Tbe case p = 2 or 3 can't use the XZ algorithm
    if p == 2 or p == 3:
        O = E([0,1,0])
        P = O
        cofactor = E.cardinality()/m
        while any(i*P == O for i in range(1,m)):
            P = ZZ(cofactor)*E.random_point()

        gen_G = Integers(m).unit_gens()[0]**n
        order = euler_phi(m)/(2*n)

        return sum( (ZZ(gen_G**i)*P)[0] for i in range(order))
    else:
        P = XZ.find_ordm(E, m)
#.........这里部分代码省略.........

#.........这里部分代码省略.........
        [ 0  0  0  0  0 11  0  0  0  0]
        [ 0  0  0  0 11  0  0  0  0  0]
        [ 0  0  0  1 -5 -2 -1  1 -3  5]
        [ 0  0  1  0 -3  4  1  4 -3 -2]
        [ 0  1  0  0 -4  5 -3  3  5  3]
        [ 1  0  0  0 -2 -1  4  2  5  4]

    * Relation of primal and dual bases ::

        sage: B_primal=sage.crypto.gen_lattice(m=10, q=11, seed=42)
        sage: B_dual=sage.crypto.gen_lattice(m=10, q=11, seed=42, dual=True)
        sage: B_dual_alt=transpose(11*B_primal.inverse()).change_ring(ZZ)
        sage: B_dual_alt.hermite_form() == B_dual.hermite_form()
        True

    REFERENCES:

.. [A96] Miklos Ajtai.
   Generating hard instances of lattice problems (extended abstract).
   STOC, pp. 99--108, ACM, 1996.

.. [GM02] Daniel Goldstein and Andrew Mayer.
   On the equidistribution of Hecke points.
   Forum Mathematicum, 15:2, pp. 165--189, De Gruyter, 2003.

.. [LM06] Vadim Lyubashevsky and Daniele Micciancio.
   Generalized compact knapsacks are collision resistant.
   ICALP, pp. 144--155, Springer, 2006.

.. [R05] Oded Regev.
   On lattices, learning with errors, random linear codes, and cryptography.
   STOC, pp. 84--93, ACM, 2005.
    """
    from sage.rings.finite_rings.integer_mod_ring \
        import IntegerModRing
    from sage.matrix.constructor import matrix, \
        identity_matrix, block_matrix
    from sage.matrix.matrix_space import MatrixSpace
    from sage.rings.integer_ring import IntegerRing
    if seed != None:
        from sage.misc.randstate import set_random_seed
        set_random_seed(seed)

    if type == 'random':
        if n != 1: raise ValueError('random bases require n = 1')

    ZZ = IntegerRing()
    ZZ_q = IntegerModRing(q)
    A = identity_matrix(ZZ_q, n)

    if type == 'random' or type == 'modular':
        R = MatrixSpace(ZZ_q, m-n, n)
        A = A.stack(R.random_element())

    elif type == 'ideal':
        if quotient == None: raise \
            ValueError('ideal bases require a quotient polynomial')
        x = quotient.default_variable()
        if n != quotient.degree(x): raise \
            ValueError('ideal bases require n  = quotient.degree()')
        R = ZZ_q[x].quotient(quotient, x)
        for i in range(m//n):
            A = A.stack(R.random_element().matrix())

    elif type == 'cyclotomic':
        from sage.rings.arith import euler_phi
        from sage.misc.functional import cyclotomic_polynomial

        # we assume that n+1 <= min( euler_phi^{-1}(n) ) <= 2*n
        found = False
        for k in range(2*n,n,-1):
            if euler_phi(k) == n:
                found = True
                break
        if not found: raise \
            ValueError('cyclotomic bases require that n is an image of' + \
                       'Euler\'s totient function')

        R = ZZ_q['x'].quotient(cyclotomic_polynomial(k, 'x'), 'x')
        for i in range(m//n):
            A = A.stack(R.random_element().matrix())

    # switch from representatives 0,...,(q-1) to (1-q)/2,....,(q-1)/2
    def minrep(a):
        if abs(a-q) < abs(a): return a-q
        else: return a
    A_prime = A[n:m].lift().apply_map(minrep)

    if not dual:
        B = block_matrix([[ZZ(q), ZZ.zero()], [A_prime, ZZ.one()] ], \
                         subdivide=False)
    else:
        B = block_matrix([[ZZ.one(), -A_prime.transpose()], [ZZ.zero(), \
                         ZZ(q)]], subdivide=False)
        for i in range(m//2): B.swap_rows(i,m-i-1)

    if not ntl:
        return B
    else:
        return B._ntl_()

#.........这里部分代码省略.........
      STOC, pp. 99--108, ACM, 1996.

    .. [GM02] Daniel Goldstein and Andrew Mayer.
      On the equidistribution of Hecke points.
      Forum Mathematicum, 15:2, pp. 165--189, De Gruyter, 2003.

    .. [LM06] Vadim Lyubashevsky and Daniele Micciancio.
      Generalized compact knapsacks are collision resistant.
      ICALP, pp. 144--155, Springer, 2006.

    .. [R05] Oded Regev.
      On lattices, learning with errors, random linear codes, and cryptography.
      STOC, pp. 84--93, ACM, 2005.
    """
    from sage.rings.finite_rings.integer_mod_ring import IntegerModRing
    from sage.matrix.constructor import identity_matrix, block_matrix
    from sage.matrix.matrix_space import MatrixSpace
    from sage.rings.integer_ring import IntegerRing

    if seed is not None:
        from sage.misc.randstate import set_random_seed

        set_random_seed(seed)

    if type == "random":
        if n != 1:
            raise ValueError("random bases require n = 1")

    ZZ = IntegerRing()
    ZZ_q = IntegerModRing(q)
    A = identity_matrix(ZZ_q, n)

    if type == "random" or type == "modular":
        R = MatrixSpace(ZZ_q, m - n, n)
        A = A.stack(R.random_element())

    elif type == "ideal":
        if quotient is None:
            raise ValueError("ideal bases require a quotient polynomial")
        try:
            quotient = quotient.change_ring(ZZ_q)
        except (AttributeError, TypeError):
            quotient = quotient.polynomial(base_ring=ZZ_q)

        P = quotient.parent()
        # P should be a univariate polynomial ring over ZZ_q
        if not is_PolynomialRing(P):
            raise TypeError("quotient should be a univariate polynomial")
        assert P.base_ring() is ZZ_q

        if quotient.degree() != n:
            raise ValueError("ideal basis requires n = quotient.degree()")
        R = P.quotient(quotient)
        for i in range(m // n):
            A = A.stack(R.random_element().matrix())

    elif type == "cyclotomic":
        from sage.rings.arith import euler_phi
        from sage.misc.functional import cyclotomic_polynomial

        # we assume that n+1 <= min( euler_phi^{-1}(n) ) <= 2*n
        found = False
        for k in range(2 * n, n, -1):
            if euler_phi(k) == n:
                found = True
                break
        if not found:
            raise ValueError("cyclotomic bases require that n " "is an image of Euler's totient function")

        R = ZZ_q["x"].quotient(cyclotomic_polynomial(k, "x"), "x")
        for i in range(m // n):
            A = A.stack(R.random_element().matrix())

    # switch from representatives 0,...,(q-1) to (1-q)/2,....,(q-1)/2
    def minrep(a):
        if abs(a - q) < abs(a):
            return a - q
        else:
            return a

    A_prime = A[n:m].lift().apply_map(minrep)

    if not dual:
        B = block_matrix([[ZZ(q), ZZ.zero()], [A_prime, ZZ.one()]], subdivide=False)
    else:
        B = block_matrix([[ZZ.one(), -A_prime.transpose()], [ZZ.zero(), ZZ(q)]], subdivide=False)
        for i in range(m // 2):
            B.swap_rows(i, m - i - 1)

    if ntl and lattice:
        raise ValueError("Cannot specify ntl=True and lattice=True " "at the same time")

    if ntl:
        return B._ntl_()
    elif lattice:
        from sage.modules.free_module_integer import IntegerLattice

        return IntegerLattice(B)
    else:
        return B

def find_unique_orbit_elliptic(E, m, Y_coordinates = False, case = 0):
    '''
    INPUT : 
    
    - ``E`` -- an elliptic curve with the properties given in isom_elliptic 
      and/or find_elliptic_curve.

    - ``m`` -- an integer with the properties given in isom_elliptic and/or in 
      find_m.

    - ``Y_coordinates`` -- boolean (default : False) determines if X or Y 
      coordinates are used.

    - ``case`` -- integer (default : 0) depends on the j-invariant's value :
        - ``0`` means j is not 0 nor 1728 or t = 0,
        - ``1`` means j is 1728,
        - ``2`` means j is 0.

    OUPUT : 
    
    - A uniquely defined element of the field where E is defined, namely the 
      extension of degree n considered; unique means every produced elements 
      have the same minimal polynomial.

    EXAMPLES :

    - Case j != 0, 1728

        sage: E = EllipticCurve(j = GF(5)(1))

        sage: EK = E.change_ring(GF(5**19, prefix = 'z', conway = True)

        sage: m = 229

        sage: elem1 = find_unique_orbit_elliptic(EK,m)

        sage: elem2 = find_unique_orbit_elliptic(EK,m)

        sage: elem1.minpoly() == elem2.minpoly()

        True

    - Case j = 1728 and trace != 0

        sage : E = EllipticCurve(j = GF(5)(1728))

        sage: EK = E.change_ring(GF(5**19, prefix = 'z', conway = True)

        sage: m = 229

        sage: elem1 = find_unique_orbit_elliptic(EK,m)

        sage: elem2 = find_unique_orbit_elliptic(EK,m)

        sage: elem1.minpoly() == elem2.minpoly()

        True

    - Case j = 0 and trace != 0

        sage: E = EllipticCurve(j = GF(7)(0))

        sage: EK = E.change_ring(GF(7**23, prefix = 'z', conway = True)

        sage: m = 139

        sage: elem1 = find_unique_orbit_elliptic(EK,m)

        sage: elem2 = find_unique_orbit_elliptic(EK,m)

        sage: elem1.minpoly() == elem2.minpoly()

        True


    ALGORITHM:
    TODO
    '''
    cofactor = E.cardinality()//m
    n = E.base_ring().degree()

    # Searching for a point of order exactly m.
    w = cputime()
    P = E(0)
    while any((m//i)*P == 0 for i in m.prime_divisors()):
        P = cofactor*E.random_point()
    w_ordm = cputime(w)
    w = cputime()

    if case == 0:
        # Looking for a generator of order exactly phi(m)/n in 
        # phi(m)/something.
        gen_G = Integers(m).unit_gens()[0]**n
        order = euler_phi(m)//(2*n)

        if not Y_coordinates:
            r = sum((ZZ(gen_G**i)*P)[0] for i in range(order))
            w_period = cputime(w)
            return w_ordm, w_period
        else:
#.........这里部分代码省略.........