def test_add_commutes(trials, verbose=False):
    r"""
    This is a simple demonstration of the :func:`random_testing` decorator and
    its recommended usage.

    We test that addition is commutative over rationals.

    EXAMPLES::

        sage: from sage.misc.random_testing import test_add_commutes
        sage: test_add_commutes(2, verbose=True, seed=0)
        a == -4, b == 0 ...
        Passes!
        a == -1/2, b == -1/95 ...
        Passes!
        sage: test_add_commutes(10)
        sage: test_add_commutes(1000) # long time
    """
    from sage.rings.all import QQ
    for _ in xrange(trials):
        a = QQ.random_element()
        b = QQ.random_element()
        if verbose:
            print "a == %s, b == %s ..." % (a, b)
        assert(a+b == b+a)
        if verbose:
            print "Passes!"

def is_possible_j(j, S=[]):
    r"""
    Tests if the rational `j` is a possible `j`-invariant of an
    elliptic curve with good reduction outside `S`.

    .. note::

        The condition used is necessary but not sufficient unless S
        contains both 2 and 3.

    EXAMPLES::

        sage: from sage.schemes.elliptic_curves.ell_egros import is_possible_j
        sage: is_possible_j(0,[])
        False
        sage: is_possible_j(1728,[])
        True
        sage: is_possible_j(-4096/11,[11])
        True
    """
    j = QQ(j)
    return (j.is_zero() and 3 in S) \
        or (j==1728)                \
        or (j.is_S_integral(S)      \
            and j.prime_to_S_part(S).is_nth_power(3) \
            and (j-1728).prime_to_S_part(S).abs().is_square())

    def __add__(self, other):
        r"""
        Return the subgroup of `\QQ` generated by this group and ``other``.

        INPUT:

        - ``other`` -- a discrete value group or a rational number

        EXAMPLES::

            sage: D = DiscreteValueGroup(1/2)
            sage: D + 1/3
            DiscreteValueGroup(1/6)
            sage: D + D
            DiscreteValueGroup(1/2)
            sage: D + 1
            DiscreteValueGroup(1/2)
            sage: DiscreteValueGroup(2/7) + DiscreteValueGroup(4/9)
            DiscreteValueGroup(2/63)

        """
        if not isinstance(other, DiscreteValueGroup):
            from sage.structure.element import is_Element
            if is_Element(other) and QQ.has_coerce_map_from(other.parent()):
                return self + DiscreteValueGroup(other, category=self.category())
            raise ValueError("`other` must be a DiscreteValueGroup or a rational number")
        if self.category() is not other.category():
            raise ValueError("`other` must be in the same category")
        return DiscreteValueGroup(self._generator.gcd(other._generator), category=self.category())

    def __add__(self, other):
        r"""
        Return the subsemigroup of `\QQ` generated by this semigroup and ``other``.

        INPUT:

        - ``other`` -- a discrete value (semi-)group or a rational number

        EXAMPLES::

            sage: from sage.rings.valuation.value_group import DiscreteValueSemigroup, DiscreteValueGroup
            sage: D = DiscreteValueSemigroup(1/2)
            sage: D + 1/3
            Additive Abelian Semigroup generated by 1/3, 1/2
            sage: D + D
            Additive Abelian Semigroup generated by 1/2
            sage: D + 1
            Additive Abelian Semigroup generated by 1/2
            sage: DiscreteValueGroup(2/7) + DiscreteValueSemigroup(4/9)
            Additive Abelian Semigroup generated by -2/7, 2/7, 4/9

        """
        if isinstance(other, DiscreteValueSemigroup):
            return DiscreteValueSemigroup(self._generators + other._generators)
        if isinstance(other, DiscreteValueGroup):
            return DiscreteValueSemigroup(self._generators + (other._generator, -other._generator))
        from sage.structure.element import is_Element
        if is_Element(other) and QQ.has_coerce_map_from(other.parent()):
            return self + DiscreteValueSemigroup(other)
        raise ValueError("`other` must be a DiscreteValueGroup, a DiscreteValueSemigroup or a rational number")

    def _element_constructor_(self, x):
        r"""
        Create an element in this group from ``x``.

        INPUT:

        - ``x`` -- a rational number

        TESTS::

            sage: from sage.rings.valuation.value_group import DiscreteValueSemigroup
            sage: DiscreteValueSemigroup([])(0)
            0
            sage: DiscreteValueSemigroup([])(1)
            Traceback (most recent call last):
            ...
            ValueError: `1` is not in Trivial Additive Abelian Semigroup.
            sage: DiscreteValueSemigroup([1])(1)
            1
            sage: DiscreteValueSemigroup([1])(-1)
            Traceback (most recent call last):
            ...
            ValueError: `-1` is not in Additive Abelian Semigroup generated by 1.

        """
        x = QQ.coerce(x)
        if x in self._generators or self._solve_linear_program(x) is not None:
            return x 

        raise ValueError("`{0}` is not in {1}.".format(x,self))

def b(tableau, star=0):
    r"""
    The column projection operator corresponding to the Young tableau
    ``tableau`` (which is supposed to contain every integer from
    `1` to its size precisely once, but may and may not be standard).

    This is the signed sum (in the group algebra of the relevant
    symmetric group over `\QQ`) of all the permutations which
    preserve the column of ``tableau`` (where the signs are the usual
    signs of the permutations). It is called `b_{\text{tableau}}` in
    [EtRT]_, Section 4.2.

    EXAMPLES::

        sage: from sage.combinat.symmetric_group_algebra import b
        sage: b([[1,2]])
        [1, 2]
        sage: b([[1],[2]])
        [1, 2] - [2, 1]
        sage: b([])
        []
        sage: b([[1, 2, 4], [5, 3]])
        [1, 2, 3, 4, 5] - [1, 3, 2, 4, 5] - [5, 2, 3, 4, 1] + [5, 3, 2, 4, 1]

    With the `l2r` setting for multiplication, the unnormalized
    Young symmetrizer ``e(tableau)`` should be the product
    ``b(tableau) * a(tableau)`` for every ``tableau``. Let us check
    this on the standard tableaux of size 5::

        sage: from sage.combinat.symmetric_group_algebra import a, b, e
        sage: all( e(t) == b(t) * a(t) for t in StandardTableaux(5) )
        True
    """
    t = Tableau(tableau)
    if star:
        t = t.restrict(t.size()-star)

    cs = t.column_stabilizer().list()
    n = t.size()

    # This all should be over ZZ, not over QQ, but symmetric group
    # algebras don't seem to preserve coercion (the one over ZZ
    # doesn't coerce into the one over QQ even for the same n),
    # and the QQ version of this method is more important, so let
    # me stay with QQ.
    # TODO: Fix this.
    sgalg = SymmetricGroupAlgebra(QQ, n)
    one = QQ.one()
    P = permutation.Permutation

    # Ugly hack for the case of an empty tableau, due to the
    # annoyance of Permutation(Tableau([]).row_stabilizer()[0])
    # being [1] rather than [] (which seems to have its origins in
    # permutation group code).
    # TODO: Fix this.
    if len(tableau) == 0:
        return sgalg.one()

    cd = dict((P(v), v.sign()*one) for v in cs)
    return sgalg._from_dict(cd)

    def get_embedding(self,prec):
        r"""
        Returns an embedding of the quaternion algebra
        into the algebra of 2x2 matrices with coefficients in `\QQ_p`.

        INPUT:

        - prec -- Integer. The precision of the splitting.

        """
        if self.F == QQ and self.discriminant == 1:
            R =  Qp(self.p,prec)
            self._F_to_local = QQ.hom([R(1)])
            def iota(q):
                return q.change_ring(R)
            self._prec = prec
        else:
            I,J,K = self.local_splitting(prec)
            mats = [1,I,J,K]
            def iota(q):
                R=I.parent()
                try:
                    q = q.coefficient_tuple()
                except AttributeError:
                    q = q.list()
                return sum(self._F_to_local(a)*b for a,b in zip(q,mats))
        return iota

    def _coerce_map_from_(self, S):
        r"""
        Coercion from a parent ``S``.

        There is a coercion from ``S`` if ``S`` has a coerce map to `\Q`
        or if `S = \Q/m\Z` for `m` a multiple of `n`.

        TESTS::

            sage: G2 = QQ/(2*ZZ)
            sage: G3 = QQ/(3*ZZ)
            sage: G4 = QQ/(4*ZZ)
            sage: G2.has_coerce_map_from(QQ)
            True
            sage: G2.has_coerce_map_from(ZZ)
            True
            sage: G2.has_coerce_map_from(ZZ['x'])
            False
            sage: G2.has_coerce_map_from(G3)
            False
            sage: G2.has_coerce_map_from(G4)
            True
            sage: G4.has_coerce_map_from(G2)
            False
        """
        if QQ.has_coerce_map_from(S):
            return True
        if isinstance(S, QmodnZ) and (S.n / self.n in ZZ):
            return True

    def create_key(self, base, s):
        r"""
        Create a key which uniquely identifies a valuation.

        TESTS::

            sage: 3*ZZ.valuation(2) is 2*(3/2*ZZ.valuation(2)) # indirect doctest
            True
            
        """
        from sage.rings.all import infinity, QQ
        if s is infinity or s not in QQ or s <= 0:
            # for these values we can not return a TrivialValuation() in
            # create_object() because that would override that instance's
            # _factory_data and lead to pickling errors
            raise ValueError("s must be a positive rational")
        if base.is_trivial():
            # for the same reason we can not accept trivial valuations here
            raise ValueError("base must not be trivial")
        s = QQ.coerce(s)
        if s == 1:
            # we would override the _factory_data of base if we just returned
            # it in create_object() so we just refuse to do so
            raise ValueError("s must not be 1")

        if isinstance(base, ScaledValuation_generic):
            return self.create_key(base._base_valuation, s*base._scale)

        return base, s

    def random_element(self):
        r"""
        Return a random element of `\Q/n\Z`.

        The denominator is selected
        using the ``1/n`` distribution on integers, modified to return
        a positive value.  The numerator is then selected uniformly.

        EXAMPLES::

            sage: G = QQ/(6*ZZ)
            sage: G.random_element()
            47/16
            sage: G.random_element()
            1
            sage: G.random_element()
            3/5
        """
        if self.n == 0:
            return self(QQ.random_element())
        d = ZZ.random_element()
        if d >= 0:
            d = 2 * d + 1
        else:
            d = -2 * d
        n = ZZ.random_element((self.n * d).ceil())
        return self(n / d)

def a(tableau, star=0):
    r"""
    The row projection operator corresponding to the Young tableau
    ``tableau`` (which is supposed to contain every integer from
    `1` to its size precisely once, but may and may not be standard).

    This is the sum (in the group algebra of the relevant symmetric
    group over `\QQ`) of all the permutations which preserve
    the rows of ``tableau``. It is called `a_{\text{tableau}}` in
    [EtRT]_, Section 4.2.

    REFERENCES:

    .. [EtRT] Pavel Etingof, Oleg Golberg, Sebastian Hensel, Tiankai
       Liu, Alex Schwendner, Dmitry Vaintrob, Elena Yudovina,
       "Introduction to representation theory",
       :arXiv:`0901.0827v5`.

    EXAMPLES::

        sage: from sage.combinat.symmetric_group_algebra import a
        sage: a([[1,2]])
        [1, 2] + [2, 1]
        sage: a([[1],[2]])
        [1, 2]
        sage: a([])
        []
        sage: a([[1, 5], [2, 3], [4]])
        [1, 2, 3, 4, 5] + [1, 3, 2, 4, 5] + [5, 2, 3, 4, 1] + [5, 3, 2, 4, 1]
    """
    t = Tableau(tableau)
    if star:
        t = t.restrict(t.size()-star)

    rs = t.row_stabilizer().list()
    n = t.size()

    # This all should be over ZZ, not over QQ, but symmetric group
    # algebras don't seem to preserve coercion (the one over ZZ
    # doesn't coerce into the one over QQ even for the same n),
    # and the QQ version of this method is more important, so let
    # me stay with QQ.
    # TODO: Fix this.
    sgalg = SymmetricGroupAlgebra(QQ, n)
    one = QQ.one()
    P = permutation.Permutation

    # Ugly hack for the case of an empty tableau, due to the
    # annoyance of Permutation(Tableau([]).row_stabilizer()[0])
    # being [1] rather than [] (which seems to have its origins in
    # permutation group code).
    # TODO: Fix this.
    if len(tableau) == 0:
        return sgalg.one()

    rd = dict((P(h), one) for h in rs)
    return sgalg._from_dict(rd)

    def some_elements(self):
        """
        Return some elements, for use in testing.

        TESTS::

            sage: L = (QQ/ZZ).some_elements()
            sage: len(L)
            92
        """
        return list(set(self(x) for x in QQ.some_elements()))

 def coeff(p, q):
     ret = QQ.one()
     last = 0
     for val in p:
         count = 0
         s = 0
         while s != val:
             s += q[last+count]
             count += 1
         ret /= factorial(count)
         last += count
     return ret

    def some_elements(self):
        r"""
        Return some typical elements in this group.

        EXAMPLES::

            sage: from sage.rings.valuation.value_group import DiscreteValueGroup
            sage: DiscreteValueGroup(-3/8).some_elements()
            [3/8, -3/8, 0, 42, 3/2, -3/2, 9/8, -9/8]

        """
        return [self._generator, -self._generator] + [x for x in QQ.some_elements() if x in self]

def rotation_matrix_angle(r, check=False):
    r"""
    Return the angle of the rotation matrix ``r`` divided by ``2 pi``.

    EXAMPLES::

        sage: from flatsurf.geometry.matrix_2x2 import rotation_matrix_angle

        sage: def rot_matrix(p, q):
        ....:     z = QQbar.zeta(q) ** p
        ....:     c = z.real()
        ....:     s = z.imag()
        ....:     return matrix(AA, 2, [c,-s,s,c])
        sage: [rotation_matrix_angle(rot_matrix(i, 5)) for i in range(1,5)]
        [1/5, 2/5, 3/5, 4/5]
        sage: [rotation_matrix_angle(rot_matrix(i,7)) for i in range(1,7)]
        [1/7, 2/7, 3/7, 4/7, 5/7, 6/7]

    Some random tests::

        sage: for _ in range(100):
        ....:     r = QQ.random_element(x=0,y=500)
        ....:     r -= r.floor()
        ....:     m = rot_matrix(r.numerator(), r.denominator())
        ....:     assert rotation_matrix_angle(m) == r

    .. NOTE::

        This is using floating point arithmetic and might be wrong.
    """
    e0,e1 = r.change_ring(CDF).eigenvalues()
    m0 = (e0.log() / 2 / CDF.pi()).imag()
    m1 = (e1.log() / 2 / CDF.pi()).imag()
    r0 = RR(m0).nearby_rational(max_denominator=10000)
    r1 = RR(m1).nearby_rational(max_denominator=10000)
    if r0 != -r1:
        raise RuntimeError
    r0 = r0.abs()
    if r[0][1] > 0:
        return QQ.one() - r0
    else:
        return r0

    if check:
        e = r.change_ring(AA).eigenvalues()[0]
        if e.minpoly() != ZZ['x'].cyclotomic_polynomial()(r.denominator()):
            raise RuntimeError
        z = QQbar.zeta(r.denominator())
        if z**r.numerator() != e:
            raise RuntimeError

    return r

    def __classcall__(cls, generator):
        r"""
        Normalizes ``generator`` to a positive rational so that this is a
        unique parent.

        TESTS::

            sage: from sage.rings.valuation.value_group import DiscreteValueGroup
            sage: DiscreteValueGroup(1) is DiscreteValueGroup(-1)
            True

        """
        generator = QQ.coerce(generator)
        generator = generator.abs()
        return super(DiscreteValueGroup, cls).__classcall__(cls, generator)

def ConstantFormsSpaceFunctor(group):
    r"""
    Construction functor for the space of constant forms.

    When determining a common parent between a ring
    and a forms ring or space this functor is first
    applied to the ring.

    EXAMPLES::

        sage: from sage.modular.modform_hecketriangle.functors import (ConstantFormsSpaceFunctor, FormsSpaceFunctor)
        sage: ConstantFormsSpaceFunctor(4) == FormsSpaceFunctor("holo", 4, 0, 1)
        True
        sage: ConstantFormsSpaceFunctor(4)
        ModularFormsFunctor(n=4, k=0, ep=1)
    """
    return FormsSpaceFunctor("holo", group, QQ.zero(), ZZ.one())

    def _compute_padic_splitting(self,prec):
        verbose('Entering compute_padic_splitting')
        prime = self.p
        if self.seed is not None:
            self.magma.eval('SetSeed(%s)'%self.seed)
        R = Qp(prime,prec+10) #Zmod(prime**prec) #
        B_magma = self.Gn._B_magma
        a,b = self.Gn.B.invariants()
        if self._matrix_group:
            self._II = matrix(R,2,2,[1,0,0,-1])
            self._JJ = matrix(R,2,2,[0,1,1,0])
            goodroot = self.F.gen().minpoly().change_ring(R).roots()[0][0]
            self._F_to_local = self.F.hom([goodroot])
        else:
            verbose('Calling magma pMatrixRing')
            if self.F == QQ:
                _,f = self.magma.pMatrixRing(self.Gn._O_magma,prime*self.Gn._O_magma.BaseRing(),Precision = 20,nvals = 2)
                self._F_to_local = QQ.hom([R(1)])
            else:
                _,f = self.magma.pMatrixRing(self.Gn._O_magma,sage_F_ideal_to_magma(self.Gn._F_magma,self.ideal_p),Precision = 20,nvals = 2)
                try:
                    self._goodroot = R(f.Image(B_magma(B_magma.BaseRing().gen(1))).Vector()[1]._sage_())
                except SyntaxError:
                    raise SyntaxError("Magma has trouble finding local splitting")
                self._F_to_local = None
                for o,_ in self.F.gen().minpoly().change_ring(R).roots():
                    if (o - self._goodroot).valuation() > 5:
                        self._F_to_local = self.F.hom([o])
                        break
                assert self._F_to_local is not None
            verbose('Initializing II,JJ,KK')
            v = f.Image(B_magma.gen(1)).Vector()
            self._II = matrix(R,2,2,[v[i+1]._sage_() for i in xrange(4)])
            v = f.Image(B_magma.gen(2)).Vector()
            self._JJ = matrix(R,2,2,[v[i+1]._sage_() for i in xrange(4)])
            v = f.Image(B_magma.gen(3)).Vector()
            self._KK = matrix(R,2,2,[v[i+1]._sage_() for i in xrange(4)])
            self._II , self._JJ = lift_padic_splitting(self._F_to_local(a),self._F_to_local(b),self._II,self._JJ,prime,prec)
        self.Gn._F_to_local = self._F_to_local
        if not self.use_shapiro():
            self.Gpn._F_to_local = self._F_to_local

        self._KK = self._II * self._JJ
        self._prec = prec
        return self._II, self._JJ, self._KK

    def _mul_(self, other, switch_sides=False):
        r"""
        Return the semigroup generated by ``other`` times the generators of this
        semigroup.

        INPUT:

        - ``other`` -- a rational number

        EXAMPLES::

            sage: from sage.rings.valuation.value_group import DiscreteValueSemigroup
            sage: D = DiscreteValueSemigroup(1/2)
            sage: 1/2 * D
            Additive Abelian Semigroup generated by 1/4
            sage: D * (1/2)
            Additive Abelian Semigroup generated by 1/4
            sage: D * 0
            Trivial Additive Abelian Semigroup

        """
        other = QQ.coerce(other)
        return DiscreteValueSemigroup([g*other for g in self._generators])

    def __call__(self, Q, P):
        """
        Compute and return the :class:`ReductionData` corresponding to
        the genus 2 curve `y^2 + Q(x) y = P(x)`.

        EXAMPLES::

            sage: x = polygen(QQ)
            sage: genus2reduction(x^3 - 2*x^2 - 2*x + 1, -5*x^5)
            Reduction data about this proper smooth genus 2 curve:
                    y^2 + (x^3 - 2*x^2 - 2*x + 1)*y = -5*x^5
            A Minimal Equation (away from 2):
                    y^2 = x^6 - 240*x^4 - 2550*x^3 - 11400*x^2 - 24100*x - 19855
            Minimal Discriminant (away from 2):  56675000
            Conductor (away from 2): 1416875
            Local Data:
                    p=2
                    (potential) stable reduction:  (II), j=1
                    p=5
                    (potential) stable reduction:  (I)
                    reduction at p: [V] page 156, (3), f=4
                    p=2267
                    (potential) stable reduction:  (II), j=432
                    reduction at p: [I{1-0-0}] page 170, (1), f=1

        ::

            sage: genus2reduction(x^2 + 1, -5*x^5)
            Reduction data about this proper smooth genus 2 curve:
                    y^2 + (x^2 + 1)*y = -5*x^5
            A Minimal Equation (away from 2):
                    y^2 = -20*x^5 + x^4 + 2*x^2 + 1
            Minimal Discriminant (away from 2):  48838125
            Conductor: 32025
            Local Data:
                    p=3
                    (potential) stable reduction:  (II), j=1
                    reduction at p: [I{1-0-0}] page 170, (1), f=1
                    p=5
                    (potential) stable reduction:  (IV)
                    reduction at p: [I{1-1-2}] page 182, (5), f=2
                    p=7
                    (potential) stable reduction:  (II), j=4
                    reduction at p: [I{1-0-0}] page 170, (1), f=1
                    p=61
                    (potential) stable reduction:  (II), j=57
                    reduction at p: [I{2-0-0}] page 170, (2), f=1

        Verify that we fix :trac:`5573`::

            sage: genus2reduction(x^3 + x^2 + x,-2*x^5 + 3*x^4 - x^3 - x^2 - 6*x - 2)
            Reduction data about this proper smooth genus 2 curve:
                    y^2 + (x^3 + x^2 + x)*y = -2*x^5 + 3*x^4 - x^3 - x^2 - 6*x - 2
            A Minimal Equation (away from 2):
                    y^2 = x^6 + 18*x^3 + 36*x^2 - 27
            Minimal Discriminant (away from 2):  1520984142
            Conductor: 954
            Local Data:
                    p=2
                    (potential) stable reduction:  (II), j=1
                    reduction at p: [I{1-0-0}] page 170, (1), f=1
                    p=3
                    (potential) stable reduction:  (I)
                    reduction at p: [II] page 155, (1), f=2
                    p=53
                    (potential) stable reduction:  (II), j=12
                    reduction at p: [I{1-0-0}] page 170, (1), f=1
        """
        R = PolynomialRing(QQ, 'x')
        P = R(P)
        Q = R(Q)
        if P.degree() > 6:
            raise ValueError("P (=%s) must have degree at most 6"%P)
        if Q.degree() >=4:
            raise ValueError("Q (=%s) must have degree at most 3"%Q)

        res = pari.genus2red([P,Q])

        conductor = ZZ(res[0])
        minimal_equation = R(res[2])

        minimal_disc = QQ(res[2].poldisc()).abs()
        if minimal_equation.degree() == 5:
            minimal_disc *= minimal_equation[5]**2
        # Multiply with suitable power of 2 of the form 2^(2*(d-1) - 12)
        b = 2 * (minimal_equation.degree() - 1)
        k = QQ((12 - minimal_disc.valuation(2), b)).ceil()
        minimal_disc >>= 12 - b*k
        minimal_disc = ZZ(minimal_disc)

        local_data = {}
        for red in res[3]:
            p = ZZ(red[0])

            t = red[1]
            data = "(potential) stable reduction:  (%s)" % roman_numeral[int(t[0])]
            t = t[1]
            if len(t) == 1:
                data += ", j=%s" % t[0].lift()
            elif len(t) == 2:
#.........这里部分代码省略.........