def __classcall_private__(cls, R, n=None, M=None, ambient=None):
        """
        Normalize input to ensure a unique representation.

        EXAMPLES::

            sage: from sage.categories.examples.finite_dimensional_lie_algebras_with_basis import AbelianLieAlgebra
            sage: A1 = AbelianLieAlgebra(QQ, n=3)
            sage: A2 = AbelianLieAlgebra(QQ, M=FreeModule(QQ, 3))
            sage: A3 = AbelianLieAlgebra(QQ, 3, FreeModule(QQ, 3))
            sage: A1 is A2 and A2 is A3
            True

            sage: A1 = AbelianLieAlgebra(QQ, 2)
            sage: A2 = AbelianLieAlgebra(ZZ, 2)
            sage: A1 is A2
            False

            sage: A1 = AbelianLieAlgebra(QQ, 0)
            sage: A2 = AbelianLieAlgebra(QQ, 1)
            sage: A1 is A2
            False
        """
        if M is None:
            M = FreeModule(R, n)
        else:
            M = M.change_ring(R)
            n = M.dimension()
        return super(AbelianLieAlgebra, cls).__classcall__(cls, R, n=n, M=M,
                                                           ambient=ambient)

    def reduce_basis(self, long_etas):
        r"""
        Produce a more manageable basis via LLL-reduction.

        INPUT:


        - ``long_etas`` -  a list of EtaGroupElement objects (which
          should all be of the same level)


        OUTPUT:


        - a new list of EtaGroupElement objects having
          hopefully smaller norm


        ALGORITHM: We define the norm of an eta-product to be the
        `L^2` norm of its divisor (as an element of the free
        `\ZZ`-module with the cusps as basis and the
        standard inner product). Applying LLL-reduction to this gives a
        basis of hopefully more tractable elements. Of course we'd like to
        use the `L^1` norm as this is just twice the degree, which
        is a much more natural invariant, but `L^2` norm is easier
        to work with!

        EXAMPLES::

            sage: EtaGroup(4).reduce_basis([ EtaProduct(4, {1:8,2:24,4:-32}), EtaProduct(4, {1:8, 4:-8})])
            [Eta product of level 4 : (eta_1)^8 (eta_4)^-8,
            Eta product of level 4 : (eta_1)^-8 (eta_2)^24 (eta_4)^-16]
        """
        from six.moves import range
        N = self.level()
        cusps = AllCusps(N)
        r = matrix(ZZ, [[et.order_at_cusp(c) for c in cusps] for et in long_etas])
        V = FreeModule(ZZ, r.ncols())
        A = V.submodule_with_basis([V(rw) for rw in r.rows()])
        rred = r.LLL()
        short_etas = []
        for shortvect in rred.rows():
            bv = A.coordinates(shortvect)
            dict = {d: sum(bv[i] * long_etas[i].r(d)
                           for i in range(r.nrows()))
                    for d in divisors(N)}
            short_etas.append(self(dict))
        return short_etas

def basiclemmavec(self, M):
    """
    Finds a vector where the value of the quadratic form is coprime to M.

    EXAMPLES::

        sage: Q = QuadraticForm(ZZ, 2, [2, 1, 5])
        sage: Q.basiclemmavec(10)
        (6, 5)
        sage: Q(_)
        227

    """
    V = FreeModule(self.base_ring(), self.dim())
    mat = self.matrix()
    vec = []
    mod = []
    M0 = abs(M)
    if M0 == 1:
        return V(0)

    for i in range(self.dim()):
        M1 = prime_to_m_part(M0, self[i, i])
        if M1 != 1:
            vec.append(V.gen(i))
            mod.append(M1)
        M0 = M0 / M1
        if M0 == 1:
            return tuple(CRT_vectors(vec, mod))

    for i in range(self.dim()):
        for j in range(i):
            M1 = prime_to_m_part(M0, self[i, j])
            if M1 != 1:
                vec.append(V.i + V.j)
                mod.append(M1)
            M0 = M0 / M1
            if M0 == 1:
                return __crt_list(vec, mod)

    raise ValueError("not primitive form")

 def __init__( self, degrees ) :
     r"""
     INPUT:
         - ``degrees`` -- A list or tuple of `n` positive integers.
     
     TESTS::
         sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import *
         sage: g = DegreeGrading((1,2))
         sage: g = DegreeGrading([5,2,3])
     """
     
     self.__degrees = tuple(degrees)
     self.__module = FreeModule(ZZ, len(degrees))
     self.__module_basis = self.__module.basis()

    def __init__(self, R, form, names=None):
        """
        Initialize ``self``.

        TESTS::

            sage: m = matrix([[-2,3],[3,4]])
            sage: J = JordanAlgebra(m)
            sage: TestSuite(J).run()
        """
        self._form = form
        self._M = FreeModule(R, form.ncols())
        cat = MagmaticAlgebras(R).Commutative().Unital().FiniteDimensional().WithBasis()
        self._no_generic_basering_coercion = True # Remove once 16492 is fixed
        Parent.__init__(self, base=R, names=names, category=cat)

    def __init__(self, R, s_coeff, names, index_set, category=None, prefix=None,
                 bracket=None, latex_bracket=None, string_quotes=None, **kwds):
        """
        Initialize ``self``.

        EXAMPLES::

            sage: L = LieAlgebra(QQ, 'x,y', {('x','y'): {'x':1}})
            sage: TestSuite(L).run()
        """
        default = (names != tuple(index_set))
        if prefix is None:
            if default:
                prefix = 'L'
            else:
                prefix = ''
        if bracket is None:
            bracket = default
        if latex_bracket is None:
            latex_bracket = default
        if string_quotes is None:
            string_quotes = default

        #self._pos_to_index = dict(enumerate(index_set))
        self._index_to_pos = {k: i for i,k in enumerate(index_set)}
        if "sorting_key" not in kwds:
            kwds["sorting_key"] = self._index_to_pos.__getitem__

        cat = LieAlgebras(R).WithBasis().FiniteDimensional().or_subcategory(category)
        FinitelyGeneratedLieAlgebra.__init__(self, R, names, index_set, cat)
        IndexedGenerators.__init__(self, self._indices, prefix=prefix,
                                   bracket=bracket, latex_bracket=latex_bracket,
                                   string_quotes=string_quotes, **kwds)

        self._M = FreeModule(R, len(index_set))

        # Transform the values in the structure coefficients to elements
        def to_vector(tuples):
            vec = [R.zero()]*len(index_set)
            for k,c in tuples:
                vec[self._index_to_pos[k]] = c
            vec = self._M(vec)
            vec.set_immutable()
            return vec
        self._s_coeff = {(self._index_to_pos[k[0]], self._index_to_pos[k[1]]):
                         to_vector(s_coeff[k])
                         for k in s_coeff.keys()}

 def __init__( self, q):
     """
     We initialize by a list of integers $[a_1,...,a_N]$. The
     lattice self is then $L = (L,\beta) = (G^{-1}\ZZ^n/\ZZ^n, G[x])$,
     where $G$ is the symmetric matrix
     $G=[a_1,...,a_n;*,a_{n+1},....;..;* ... * a_N]$,
     i.e.~the $a_j$ denote the elements above the diagonal of $G$.
     """
     self.__form = q
     # We compute the rank
     N = len(q)
     assert is_square( 1+8*N)
     n = Integer( (-1+isqrt(1+8*N))/2)
     self.__rank = n
     # We set up the Gram matrix
     self.__G = matrix( IntegerRing(), n, n)
     i = j = 0
     for a in q:
         self.__G[i,j] = self.__G[j,i] = Integer(a)
         if j < n-1:
             j += 1
         else:
             i += 1
             j = i
     # We compute the level
     Gi = self.__G**-1
     self.__Gi = Gi
     a = lcm( map( lambda x: x.denominator(), Gi.list()))
     I = Gi.diagonal()
     b =  lcm( map( lambda x: (x/2).denominator(), I))
     self.__level = lcm( a, b)
     # We define the undelying module and the ambient space
     self.__module = FreeModule( IntegerRing(), n)
     self.__space = self.__module.ambient_vector_space()
     # We compute a shadow vector
     self.__shadow_vector = self.__space([(a%2)/2 for a in self.__G.diagonal()])*Gi
     # We define a basis
     M = Matrix( IntegerRing(), n, n, 1)
     self.__basis = self.__module.basis()
     # We prepare a cache
     self.__dual_vectors = None
     self.__values = None
     self.__chi = {}

 def __init__(self, dim):
     from sage.modules.free_module import FreeModule
     self._free_module = FreeModule(ZZ, int(dim))

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

        INPUT:

        - ``n`` - dimension (integer > 0)
        - ``q`` - modulus typically > n (integer > 0)
        - ``D`` - an error distribution such as an instance of
          :class:`DiscreteGaussianDistributionIntegerSampler` or :class:`UniformSampler`
        - ``secret_dist`` - distribution of the secret (default: 'uniform'); one of

          - "uniform" - secret follows the uniform distribution in `\Zmod{q}`
          - "noise" - secret follows the noise distribution
          - ``(lb,ub)`` - the secret is chosen uniformly from ``[lb,...,ub]`` including both endpoints

        - ``m`` - number of allowed samples or ``None`` if no such limit exists
          (default: ``None``)

        EXAMPLES:

        First, we construct a noise distribution with standard deviation 3.0::

            sage: from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
            sage: D = DiscreteGaussianDistributionIntegerSampler(3.0)

        Next, we construct our oracle::

            sage: from sage.crypto.lwe import LWE
            sage: lwe = LWE(n=20, q=next_prime(400), D=D); lwe
            LWE(20, 401, Discrete Gaussian sampler over the Integers with sigma = 3.000000 and c = 0, 'uniform', None)

        and sample 1000 samples::

            sage: L = [lwe() for _ in range(1000)]

        To test the oracle, we use the internal secret to evaluate the samples
        in the secret::

            sage: S = [ZZ(a.dot_product(lwe._LWE__s) - c) for (a,c) in L]

        However, while Sage represents finite field elements between 0 and q-1
        we rely on a balanced representation of those elements here. Hence, we
        fix the representation and recover the correct standard deviation of the
        noise::

            sage: sqrt(variance([e if e <= 200 else e-401 for e in S]).n())
            3.0...

        If ``m`` is not ``None`` the number of available samples is restricted::

            sage: from sage.crypto.lwe import LWE
            sage: lwe = LWE(n=20, q=next_prime(400), D=D, m=30)
            sage: _ = [lwe() for _ in range(30)]
            sage: lwe() # 31
            Traceback (most recent call last):
            ...
            IndexError: Number of available samples exhausted.
        """
        self.n  = ZZ(n)
        self.m =  m
        self.__i = 0
        self.K  = IntegerModRing(q)
        self.FM = FreeModule(self.K, n)
        self.D = D

        self.secret_dist = secret_dist
        if secret_dist == 'uniform':
            self.__s = random_vector(self.K, self.n)
        elif secret_dist == 'noise':
            self.__s = vector(self.K, self.n, [self.D() for _ in range(n)])
        else:
            try:
                lb, ub = map(ZZ, secret_dist)
                self.__s = vector(self.K, self.n, [randint(lb,ub) for _ in range(n)])
            except (IndexError, TypeError):
                raise TypeError("Parameter secret_dist=%s not understood."%(secret_dist))

class LWE(SageObject):
    """
    Learning with Errors (LWE) oracle.

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

        INPUT:

        - ``n`` - dimension (integer > 0)
        - ``q`` - modulus typically > n (integer > 0)
        - ``D`` - an error distribution such as an instance of
          :class:`DiscreteGaussianSamplerRejection` or :class:`UniformSampler`
        - ``secret_dist`` - distribution of the secret (default: 'uniform'); one of

          - "uniform" - secret follows the uniform distribution in `\Zmod{q}`
          - "noise" - secret follows the noise distribution
          - ``(lb,ub)`` - the secret is chosen uniformly from ``[lb,...,ub]`` including both endpoints

        - ``m`` - number of allowed samples or ``None`` if no such limit exists
          (default: ``None``)

        EXAMPLE:

        First, we construct a noise distribution with standard deviation 3.0::

            sage: from sage.crypto.lwe import DiscreteGaussianSampler
            sage: D = DiscreteGaussianSampler(3.0)

        Next, we construct our oracle::

            sage: from sage.crypto.lwe import LWE
            sage: lwe = LWE(n=20, q=next_prime(400), D=D); lwe
            LWE(20, 401, DiscreteGaussianSamplerRejection(3.000000, 53, 4), 'uniform', None)

        and sample 1000 samples::

            sage: L = [lwe() for _ in range(1000)]

        To test the oracle, we use the internal secret to evaluate the samples
        in the secret::

            sage: S = [ZZ(a.dot_product(lwe._LWE__s) - c) for (a,c) in L]

        However, while Sage represents finite field elements between 0 and q-1
        we rely on a balanced representation of those elements here. Hence, we
        fix the representation and recover the correct standard deviation of the
        noise::

            sage: sqrt(variance([e if e <= 200 else e-401 for e in S]).n())
            3.0...

        If ``m`` is not ``None`` the number of available samples is restricted::

            sage: from sage.crypto.lwe import LWE
            sage: lwe = LWE(n=20, q=next_prime(400), D=D, m=30)
            sage: _ = [lwe() for _ in range(30)]
            sage: lwe() # 31
            Traceback (most recent call last):
            ...
            IndexError: Number of available samples exhausted.
        """
        self.n  = ZZ(n)
        self.m =  m
        self.__i = 0
        self.K  = IntegerModRing(q)
        self.FM = FreeModule(self.K, n)
        self.D = D

        self.secret_dist = secret_dist
        if secret_dist == 'uniform':
            self.__s = random_vector(self.K, self.n)
        elif secret_dist == 'noise':
            self.__s = vector(self.K, self.n, [self.D() for _ in range(n)])
        else:
            try:
                lb, ub = map(ZZ,secret_dist)
                self.__s = vector(self.K, self.n, [randint(lb,ub) for _ in range(n)])
            except (IndexError, TypeError):
                raise TypeError("Parameter secret_dist=%s not understood."%(secret_dist))

    def _repr_(self):
        """
        EXAMPLE::

            sage: from sage.crypto.lwe import DiscreteGaussianSampler, LWE
            sage: D = DiscreteGaussianSampler(3.0)
            sage: lwe = LWE(n=20, q=next_prime(400), D=D); lwe
            LWE(20, 401, DiscreteGaussianSamplerRejection(3.000000, 53, 4), 'uniform', None)

            sage: lwe = LWE(n=20, q=next_prime(400), D=D, secret_dist=(-3, 3)); lwe
            LWE(20, 401, DiscreteGaussianSamplerRejection(3.000000, 53, 4), (-3, 3), None)
        """
        if isinstance(self.secret_dist, str):
            return "LWE(%d, %d, %s, '%s', %s)"%(self.n,self.K.order(),self.D,self.secret_dist, self.m)
#.........这里部分代码省略.........

class DegreeGrading( Grading_abstract ) :
    r"""
    This class implements a monomial grading for a polynomial ring
    `R[x_1, .., x_n]`.
    """
  
    def __init__( self, degrees ) :
        r"""
        INPUT:
            - ``degrees`` -- A list or tuple of `n` positive integers.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import *
            sage: g = DegreeGrading((1,2))
            sage: g = DegreeGrading([5,2,3])
        """
        
        self.__degrees = tuple(degrees)
        self.__module = FreeModule(ZZ, len(degrees))
        self.__module_basis = self.__module.basis()
        
    def ngens(self) :
        r"""
        The number of generators of the polynomial ring.
        
        OUTPUT:
            An integer.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import *
            sage: DegreeGrading((1,2)).ngens()
            2
            sage: DegreeGrading([5,2,3]).ngens()
            3
        """
        return len(self.__degrees)
     
    def gen(self, i) :
        r"""
        The number of generators of the polynomial ring.
        
        OUTPUT:
            An integer.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import *
            sage: DegreeGrading([5,2,3]).gen(0)
            5
            sage: DegreeGrading([5,2,3]).gen(3)
            Traceback (most recent call last):
            ...
            ValueError: Generator 3 does not exist.
        """
        if i < len(self.__degrees) :
            return self.__degrees[i]
        
        raise ValueError("Generator %s does not exist." % (i,))
    
    def gens(self) :
        r"""
        The gradings of the generators of the polynomial ring.
        
        OUTPUT:
            A tuple of integers.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import *
            sage: DegreeGrading((1,2)).gens()
            (1, 2)
            sage: DegreeGrading([5,2,3]).gens()
            (5, 2, 3)
        """
        return self.__degrees
                
    def index(self, x) :
        r"""
        The grading value of `x` with respect to this grading. 

        INPUT:
            - `x` -- A tuple of length `n`.

        OUTPUT:
            An integer.
                
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import *
            sage: g = DegreeGrading([5,2,3])
            sage: g.index((2,4,5))
            33
            sage: g.index((2,3))
            Traceback (most recent call last):
            ...
            ValueError: Tuple must have length 3.
        """
        ## TODO: We shouldn't need this.
        #if len(x) == 0 : return infinity
        
        if len(x) != len(self.__degrees) :
            raise ValueError( "Tuple must have length %s." % (len(self.__degrees),))
        
#.........这里部分代码省略.........

def modform_cusp_info(calc, S, l, precLimit):
	"""
	This goes through all the cusps and compares the space given by `(f|R)[S]`
	with the space of Elliptic modular forms expansion at those cusps.
	"""

	assert l == S.det()
	assert list(calc.curlS) == [S]

	D = calc.D
	HermWeight = calc.HermWeight
	reducedCurlFSize = calc.matrixColumnCount
	herm_modform_fe_expannsion = FreeModule(QQ, reducedCurlFSize)

	if not Integer(l).is_squarefree():
		# The calculation of the cusp expansion space takes very long here, thus
		# we skip them for now.
		return None

	for cusp in Gamma0(l).cusps():
		if cusp == Infinity: continue
		M = cusp_matrix(cusp)

		try:
			gamma, R, tM = solveR(M, S, space=CurlO(D))
		except Exception:
			print (M, S)
			raise
		R.set_immutable() # for caching, we need it hashable

		herm_modforms = herm_modform_fe_expannsion.echelonized_basis_matrix().transpose()
		ell_R_denom, ell_R_order, M_R = calcMatrixTrans(calc, R)
		CycloDegree_R = CyclotomicField(ell_R_order).degree()
		print "M_R[0] nrows, ell_R_denom, ell_R_order, Cyclo degree:", \
			M_R[0].nrows(), ell_R_denom, ell_R_order, CycloDegree_R

		# The maximum precision we can use is M_R[0].nrows().
		# However, that can be quite huge (e.g. 600).
		ce_prec = min(precLimit, M_R[0].nrows())

		ce = cuspExpansions(level=l, weight=2*HermWeight, prec=ce_prec)
		ell_M_denom, ell_M = ce.expansion_at(SL2Z(M))
		print "ell_M_denom, ell_M nrows:", ell_M_denom, ell_M.nrows()
		ell_M_order = ell_R_order # not sure here. just try the one from R. toCyclPowerBase would fail if this doesn't work
		# CyclotomicField(l / prod(l.prime_divisors())) should also work.

		# Transform to same denom.
		denom_lcm = int(lcm(ell_R_denom, ell_M_denom))
		ell_M = addRows(ell_M, denom_lcm / ell_M_denom)
		M_R = [addRows(M_R_i, denom_lcm / ell_R_denom) for M_R_i in M_R]
		ell_R_denom = ell_M_denom = denom_lcm
		print "new denom:", denom_lcm
		assert ell_R_denom == ell_M_denom

		# ell_M rows are the elliptic FE. M_R[i] columns are the elliptic FE.
		# We expect that M_R gives a higher precision for the ell FE. I'm not sure
		# if this is always true but we expect it here (maybe not needed, though).
		print "precision of M_R[0], ell_M, wanted:", M_R[0].nrows(), ell_M.ncols(), ce_prec
		assert ell_M.ncols() >= ce_prec
		prec = min(M_R[0].nrows(), ell_M.ncols())
		# cut to have same precision
		M_R = [M_R_i[:prec,:] for M_R_i in M_R]
		ell_M = ell_M[:,:prec]
		assert ell_M.ncols() == M_R[0].nrows() == prec

		print "M_R[0] rank, herm rank, mult rank:", \
			M_R[0].rank(), herm_modforms.rank(), (M_R[0] * herm_modforms).rank()
		ell_R = [M_R_i * herm_modforms for M_R_i in M_R]

		# I'm not sure on this. Seems to be true and it simplifies things in the following.
		assert ell_M_order <= ell_R_order, "{0}".format((ell_M_order, ell_R_order))
		assert ell_R_order % ell_M_order == 0, "{0}".format((ell_M_order, ell_R_order))

		# Transform to same Cyclomotic Field in same power base.
		ell_M2 = toCyclPowerBase(ell_M, ell_M_order)
		ell_R2 = toLowerCyclBase(ell_R, ell_R_order, ell_M_order)
		# We must work with the matrix. maybe we should transform hf_M instead to a
		# higher order field instead, if this ever fails (I'm not sure).
		assert ell_R2 is not None
		assert len(ell_M2) == len(ell_R2) # They should have the same power base & same degree now.
		print "ell_M2[0], ell_R2[0] rank with order %i:" % ell_M_order, ell_M2[0].rank(), ell_R2[0].rank()

		assert len(M_R) == len(ell_M2)
		for i in range(len(ell_M2)):
			ell_M_space = ell_M2[i].row_space()
			ell_R_space = ell_R2[i].column_space()
			merged = ell_M_space.intersection(ell_R_space)

			herm_modform_fe_expannsion_Ci = M_R[i].solve_right( merged.basis_matrix().transpose() )
			herm_modform_fe_expannsion_Ci_module = herm_modform_fe_expannsion_Ci.column_module()
			herm_modform_fe_expannsion_Ci_module += M_R[i].right_kernel()

			extra_check_on_herm_superspace(
				vs=herm_modform_fe_expannsion_Ci_module,
				D=D, B_cF=calc.B_cF, HermWeight=HermWeight
			)

			herm_modform_fe_expannsion = herm_modform_fe_expannsion.intersection( herm_modform_fe_expannsion_Ci_module )
			print "power", i, merged.dimension(), herm_modform_fe_expannsion_Ci_module.dimension(), \
				herm_modform_fe_expannsion.dimension()
#.........这里部分代码省略.........

class Lattice_class (SageObject):
    """
    A class representing a lattice $L$.

    NOTE
        We build this class as a sort of wrapper
        around \code{FreeModule(ZZ,n)}.
        This is reflecting the fact that
        a lattice is not a free module, but a pair
        consisting of a free module and a scalar product.
        In addition, we avoid in this way to add new
        items to the Sage category system, which we
        better leave to the specialists.

    EXAMPLES
        sage: L = Lattice_class( [2,1,2]); L
        The ZZ-lattice (ZZ^2, x^tGy), where G = 
        [2 1]
        [1 2]
        sage: L.is_even()
        True
        sage: L.gram_matrix()
        [2 1]
        [1 2]
        sage: L.dual_vectors()
        {(2/3, -1/3), (0, 0), (4/3, -2/3)}
        sage: L.representatives(2)
        {}
        sage: L.representatives(1)
        {(2/3, -1/3), (4/3, -2/3)}
        sage: L.values()          
        {0: {(0, 0)}, 1: {(2/3, -1/3), (4/3, -2/3)}}
        sage: L.det()                 
        3

        sage: g = lambda n: [1] if 1 == n else [1] + (n-1)*[0] + g(n-1) 
        sage: Z8 = Lattice_class( g(8))
        sage: a,A8 = Z8.ev()
        sage: M8 = A8.fqm()
        sage: M8.jordan_decomposition().genus_symbol()
        '2^2'
    """
    
    def __init__( self, q):
        """
        We initialize by a list of integers $[a_1,...,a_N]$. The
        lattice self is then $L = (L,\beta) = (G^{-1}\ZZ^n/\ZZ^n, G[x])$,
        where $G$ is the symmetric matrix
        $G=[a_1,...,a_n;*,a_{n+1},....;..;* ... * a_N]$,
        i.e.~the $a_j$ denote the elements above the diagonal of $G$.
        """
        self.__form = q
        # We compute the rank
        N = len(q)
        assert is_square( 1+8*N)
        n = Integer( (-1+isqrt(1+8*N))/2)
        self.__rank = n
        # We set up the Gram matrix
        self.__G = matrix( IntegerRing(), n, n)
        i = j = 0
        for a in q:
            self.__G[i,j] = self.__G[j,i] = Integer(a)
            if j < n-1:
                j += 1
            else:
                i += 1
                j = i
        # We compute the level
        Gi = self.__G**-1
        self.__Gi = Gi
        a = lcm( map( lambda x: x.denominator(), Gi.list()))
        I = Gi.diagonal()
        b =  lcm( map( lambda x: (x/2).denominator(), I))
        self.__level = lcm( a, b)
        # We define the undelying module and the ambient space
        self.__module = FreeModule( IntegerRing(), n)
        self.__space = self.__module.ambient_vector_space()
        # We compute a shadow vector
        self.__shadow_vector = self.__space([(a%2)/2 for a in self.__G.diagonal()])*Gi
        # We define a basis
        M = Matrix( IntegerRing(), n, n, 1)
        self.__basis = self.__module.basis()
        # We prepare a cache
        self.__dual_vectors = None
        self.__values = None
        self.__chi = {}


    def _latex_( self):
        return 'The ZZ-lattice $(ZZ^{%d}, x\'Gy)$, where $G = %s$' % (self.__rank, latex(self.__G))

    
    def _repr_( self):
        return 'The ZZ-lattice (ZZ^%d, x^tGy), where G = \n%r' % (self.__rank, self.__G)


    def rank( self):
        return self.__rank


#.........这里部分代码省略.........

class FreeAlgebraQuotient(UniqueRepresentation, Algebra, object):
    @staticmethod
    def __classcall__(cls, A, mons, mats, names):
        """
        Used to support unique representation.

        EXAMPLES::

            sage: H = sage.algebras.free_algebra_quotient.hamilton_quatalg(QQ)[0]  # indirect doctest
            sage: H1 = sage.algebras.free_algebra_quotient.hamilton_quatalg(QQ)[0]
            sage: H is H1
            True
        """
        new_mats = []
        for M in mats:
            M = M.parent()(M)
            M.set_immutable()
            new_mats.append(M)
        return super(FreeAlgebraQuotient, cls).__classcall__(cls, A, tuple(mons),
                                                  tuple(new_mats), tuple(names))

    Element = FreeAlgebraQuotientElement
    def __init__(self, A, mons, mats, names):
        """
        Returns a quotient algebra defined via the action of a free algebra
        A on a (finitely generated) free module. The input for the quotient
        algebra is a list of monomials (in the underlying monoid for A)
        which form a free basis for the module of A, and a list of
        matrices, which give the action of the free generators of A on this
        monomial basis.
        
        EXAMPLES:
        
        Quaternion algebra defined in terms of three generators::
        
            sage: n = 3
            sage: A = FreeAlgebra(QQ,n,'i')
            sage: F = A.monoid()
            sage: i, j, k = F.gens()
            sage: mons = [ F(1), i, j, k ]
            sage: M = MatrixSpace(QQ,4)
            sage: mats = [M([0,1,0,0, -1,0,0,0, 0,0,0,-1, 0,0,1,0]),  M([0,0,1,0, 0,0,0,1, -1,0,0,0, 0,-1,0,0]),  M([0,0,0,1, 0,0,-1,0, 0,1,0,0, -1,0,0,0]) ]
            sage: H3.<i,j,k> = FreeAlgebraQuotient(A,mons,mats)
            sage: x = 1 + i + j + k
            sage: x
            1 + i + j + k
            sage: x**128
            -170141183460469231731687303715884105728 + 170141183460469231731687303715884105728*i + 170141183460469231731687303715884105728*j + 170141183460469231731687303715884105728*k
        
        Same algebra defined in terms of two generators, with some penalty
        on already slow arithmetic.
        
        ::
        
            sage: n = 2
            sage: A = FreeAlgebra(QQ,n,'x')
            sage: F = A.monoid()
            sage: i, j = F.gens()
            sage: mons = [ F(1), i, j, i*j ]
            sage: r = len(mons)
            sage: M = MatrixSpace(QQ,r)
            sage: mats = [M([0,1,0,0, -1,0,0,0, 0,0,0,-1, 0,0,1,0]), M([0,0,1,0, 0,0,0,1, -1,0,0,0, 0,-1,0,0]) ]
            sage: H2.<i,j> = A.quotient(mons,mats)
            sage: k = i*j
            sage: x = 1 + i + j + k
            sage: x
            1 + i + j + i*j
            sage: x**128
            -170141183460469231731687303715884105728 + 170141183460469231731687303715884105728*i + 170141183460469231731687303715884105728*j + 170141183460469231731687303715884105728*i*j

        TEST::

            sage: TestSuite(H2).run()

        """
        if not is_FreeAlgebra(A):
            raise TypeError("Argument A must be an algebra.")
        R = A.base_ring()
#        if not R.is_field():  # TODO: why?
#            raise TypeError, "Base ring of argument A must be a field."
        n = A.ngens()
        assert n == len(mats)
        self.__free_algebra = A
        self.__ngens = n
        self.__dim = len(mons)
        self.__module = FreeModule(R,self.__dim)
        self.__matrix_action = mats
        self.__monomial_basis = mons # elements of free monoid
        Algebra.__init__(self, R, names, normalize=True)

    def __eq__(self, right):
        """
        Return True if all defining properties of self and right match up.

        EXAMPLES::

            sage: HQ = sage.algebras.free_algebra_quotient.hamilton_quatalg(QQ)[0]
            sage: HZ = sage.algebras.free_algebra_quotient.hamilton_quatalg(ZZ)[0]
            sage: HQ == HQ
            True
#.........这里部分代码省略.........

class JordanAlgebraSymmetricBilinear(JordanAlgebra):
    r"""
    A Jordan algebra given by a symmetric bilinear form `m`.
    """
    def __init__(self, R, form, names=None):
        """
        Initialize ``self``.

        TESTS::

            sage: m = matrix([[-2,3],[3,4]])
            sage: J = JordanAlgebra(m)
            sage: TestSuite(J).run()
        """
        self._form = form
        self._M = FreeModule(R, form.ncols())
        cat = MagmaticAlgebras(R).Commutative().Unital().FiniteDimensional().WithBasis()
        self._no_generic_basering_coercion = True # Remove once 16492 is fixed
        Parent.__init__(self, base=R, names=names, category=cat)

    def _repr_(self):
        """
        Return a string representation of ``self``.

        EXAMPLES::

            sage: m = matrix([[-2,3],[3,4]])
            sage: JordanAlgebra(m)
            Jordan algebra over Integer Ring given by the symmetric bilinear form:
            [-2  3]
            [ 3  4]
        """
        return "Jordan algebra over {} given by the symmetric bilinear" \
               " form:\n{}".format(self.base_ring(), self._form)

    def _element_constructor_(self, *args):
        """
        Construct an element of ``self`` from ``s``.

        Here ``s`` can be a pair of an element of `R` and an
        element of `M`, or an element of `R`, or an element of
        `M`, or an element of a(nother) Jordan algebra given
        by a symmetric bilinear form.

        EXAMPLES::

            sage: m = matrix([[0,1],[1,1]])
            sage: J = JordanAlgebra(m)
            sage: J(2)
            2 + (0, 0)
            sage: J((-4, (2, 5)))
            -4 + (2, 5)
            sage: J((-4, (ZZ^2)((2, 5))))
            -4 + (2, 5)
            sage: J(2, (-2, 3))
            2 + (-2, 3)
            sage: J(2, (ZZ^2)((-2, 3)))
            2 + (-2, 3)
            sage: J(-1, 1, 0)
            -1 + (1, 0)
            sage: J((ZZ^2)((1, 3)))
            0 + (1, 3)

            sage: m = matrix([[2]])
            sage: J = JordanAlgebra(m)
            sage: J(2)
            2 + (0)
            sage: J((-4, (2,)))
            -4 + (2)
            sage: J(2, (-2,))
            2 + (-2)
            sage: J(-1, 1)
            -1 + (1)
            sage: J((ZZ^1)((3,)))
            0 + (3)

            sage: m = Matrix(QQ, [])
            sage: J = JordanAlgebra(m)
            sage: J(2)
            2 + ()
            sage: J((-4, ()))
            -4 + ()
            sage: J(2, ())
            2 + ()
            sage: J(-1)
            -1 + ()
            sage: J((ZZ^0)(()))
            0 + ()
        """
        R = self.base_ring()
        if len(args) == 1:
            s = args[0]

            if isinstance(s, JordanAlgebraSymmetricBilinear.Element):
                if s.parent() is self:
                    return s
                return self.element_class(self, R(s._s), self._M(s._v))

            if isinstance(s, (list, tuple)):
                if len(s) != 2:
#.........这里部分代码省略.........

class ConvexHullPalp(ConvexHull):
    r"""
    Compute convex hull using PALP.

    Note: the points must be lattice points (ie integer coordinates) and
    generate the ambient vector space.
    """
    _name = 'PALP'

    def __init__(self, dim):
        from sage.modules.free_module import FreeModule
        self._free_module = FreeModule(ZZ, int(dim))

    def __eq__(self, other):
        return type(self) is type(other) and self._free_module == other._free_module

    def __call__(self, pts):
        filename = tmp_filename()

        pts = list(pts)
        n = len(pts)
        if n <= 2:
            return tuple(pts)
        d = len(pts[0])
        assert d == self._free_module.rank()

        # PALP only works with full dimension polyhedra!!
        ppts = [x-pts[0] for x in pts]
        U = self._free_module.submodule(ppts)
        d2 = U.rank()
        if d2 != d:
            # not full dim
            # we compute two matrices
            #  M1: small space -> big space  (makes decomposition)
            #  M2: big space -> small space  (i.e. basis of the module)
            # warning: matrices act on row vectors, i.e. left action
            from sage.matrix.constructor import matrix
            from sage.modules.free_module import FreeModule
            V2 = FreeModule(ZZ,d2)
            M1 = U.matrix()
            assert M1.nrows() == d2
            assert M1.ncols() == d
            M2 = matrix(QQ,d)
            M2[:d2,:] = M1
            i = d2
            U = U.change_ring(QQ)
            F = self._free_module.change_ring(QQ)
            for b in F.basis():
                if b not in U:
                    M2.set_row(i, b)
                    U = F.submodule(U.basis() + [b])
                    i += 1
            assert i == self._free_module.rank()
            M2 = (~M2)[:,:d2]
            assert M2.nrows() == d
            assert M2.ncols() == d2
            assert (M1*M2).is_one()
            pts2 = [p * M2 for p in ppts]
        else:
            pts2 = pts
            d2 = d

        with open(filename, "w") as output:
            output.write("{} {}\n".format(n,d2))
            for p in pts2:
                output.write(" ".join(map(str,p)))
                output.write("\n")

        args = ['poly.x', '-v', filename]
        try:
            palp_proc = Popen(args,
                    stdin=PIPE, stdout=PIPE,
                    stderr=None, cwd=str(SAGE_TMP))
        except OSError:
            raise RuntimeError("Problem with calling PALP")
        ans, err = palp_proc.communicate()
        ret_code = palp_proc.poll()

        if ret_code:
            raise RuntimeError("PALP return code is {} from input {}".format(ret_code, pts))
        a = ans.split('\n')
        try:
            dd,nn = a[0].split(' ')[:2]
            dd = int(dd)
            nn = int(nn)
            if dd > nn: dd,nn = nn,dd
        except (TypeError,ValueError):
            raise RuntimeError("PALP got wrong:\n{}".format(ans))
        if d2 != int(dd):
            raise RuntimeError("dimension changed... have d={} but PALP answered dd={} and nn={}".format(d2,dd,nn))
        n2 = int(nn)
        coords = []
        for i in xrange(1,d2+1):
            coords.append(map(ZZ,a[i].split()))
        new_pts = zip(*coords)

        if d2 != d:
            new_pts = [pts[0] + V2(p)*M1 for p in new_pts]

        t = [self._free_module(p) for p in new_pts]
#.........这里部分代码省略.........

#.........这里部分代码省略.........
                 bracket=None, latex_bracket=None, string_quotes=None, **kwds):
        """
        Initialize ``self``.

        EXAMPLES::

            sage: L = LieAlgebra(QQ, 'x,y', {('x','y'): {'x':1}})
            sage: TestSuite(L).run()
        """
        default = (names != tuple(index_set))
        if prefix is None:
            if default:
                prefix = 'L'
            else:
                prefix = ''
        if bracket is None:
            bracket = default
        if latex_bracket is None:
            latex_bracket = default
        if string_quotes is None:
            string_quotes = default

        #self._pos_to_index = dict(enumerate(index_set))
        self._index_to_pos = {k: i for i,k in enumerate(index_set)}
        if "sorting_key" not in kwds:
            kwds["sorting_key"] = self._index_to_pos.__getitem__

        cat = LieAlgebras(R).WithBasis().FiniteDimensional().or_subcategory(category)
        FinitelyGeneratedLieAlgebra.__init__(self, R, names, index_set, cat)
        IndexedGenerators.__init__(self, self._indices, prefix=prefix,
                                   bracket=bracket, latex_bracket=latex_bracket,
                                   string_quotes=string_quotes, **kwds)

        self._M = FreeModule(R, len(index_set))

        # Transform the values in the structure coefficients to elements
        def to_vector(tuples):
            vec = [R.zero()]*len(index_set)
            for k,c in tuples:
                vec[self._index_to_pos[k]] = c
            vec = self._M(vec)
            vec.set_immutable()
            return vec
        self._s_coeff = {(self._index_to_pos[k[0]], self._index_to_pos[k[1]]):
                         to_vector(s_coeff[k])
                         for k in s_coeff.keys()}

    # For compatibility with CombinatorialFreeModuleElement
    _repr_term = IndexedGenerators._repr_generator
    _latex_term = IndexedGenerators._latex_generator

    def structure_coefficients(self, include_zeros=False):
        """
        Return the dictionary of structure coefficients of ``self``.

        EXAMPLES::

            sage: L = LieAlgebra(QQ, 'x,y,z', {('x','y'): {'x':1}})
            sage: L.structure_coefficients()
            Finite family {('x', 'y'): x}
            sage: S = L.structure_coefficients(True); S
            Finite family {('x', 'y'): x, ('x', 'z'): 0, ('y', 'z'): 0}
            sage: S['x','z'].parent() is L
            True

        TESTS: