def _anihilate_pol(k, M):
    '''
    k: The weight of an element c, where c is a construction
    for generators of M_{det^* sym(10)} and an instance of
    ConstDivision.
    M: an instance of Sym10EvenDiv or Sym10OddDiv.
    Return a polynomial pl such that the subspace of M anihilated by pl(T(2))
    is equal to the subspace of holomorphic modular forms.
    '''
    R = PolynomialRing(QQ, names="x")
    x = R.gens()[0]
    if k % 2 == 0:
        # Klingen-Eisenstein series
        f = CuspForms(1, k + 10).basis()[0]
        return x - f[2] * (1 + QQ(2) ** (k - 2))
    elif k == 13:
        # Kim-Ramakrishnan-Shahidi lift
        f = CuspForms(1, 12).basis()[0]
        a = f[2]
        return x - f[2] ** 3 + QQ(2) ** 12 * f[2]
    else:
        chrply = M.hecke_charpoly(2)
        dim = hilbert_series_maybe(10)[k]
        l = [(a, b) for a, b in chrply.factor() if a.degree() == dim]
        if len(l) > 1 or l[0][1] != 1:
            raise RuntimeError
        else:
            return l[0][0]

def EllipticCurve_from_hoeij_data(line):
    """Given a line of the file "http://www.math.fsu.edu/~hoeij/files/X1N/LowDegreePlaces" 
    that is actually corresponding to an elliptic curve, this function returns the elliptic
    curve corresponding to this
    """
    Rx=PolynomialRing(QQ,'x')
    x = Rx.gen(0)
    Rxy = PolynomialRing(Rx,'y')
    y = Rxy.gen(0)
    
    N=ZZ(line.split(",")[0].split()[-1])
    x_rel=Rx(line.split(',')[-2][2:-4])
    assert x_rel.leading_coefficient()==1
    y_rel=line.split(',')[-1][1:-5]
    K = QQ.extension(x_rel,'x')
    x = K.gen(0)

    y_rel=Rxy(y_rel).change_ring(K)
    y_rel=y_rel/y_rel.leading_coefficient()
    if y_rel.degree()==1:
        y = - y_rel[0]
    else:
        #print "needing an extension!!!!"
        L = K.extension(y_rel,'y')
        y = L.gen(0)
        K = L
    #B=L.absolute_field('s')
    #f1,f2 = B.structure()
    #x,y=f2(x),f2(y)
    r = (x**2*y-x*y+y-1)/x/(x*y-1)
    s = (x*y-y+1)/x/y
    b = r*s*(r-1)
    c = s*(r-1)
    E=EllipticCurve([1-c,-b,-b,0,0])
    return N,E,K

    def theta_sym(self, j=2):
        '''
        Returns an image as a vector valued (Sym_{j} j:even) Fourier expansion
        of the generalized Theta operator associated with
        the Rankin-cohen operator {F, G}_{Sym_{j}}.

        [Reference]
        Ibukiyama, Vector valued Siegel modular forms of symmetric
        tensor weight of small degrees, COMMENTARI MATHEMATICI
        UNIVERSITATIS SANCTI PAULI VOL 61, NO 1, 2012.

        Boecherer, Nagaoka,
        On p-adic properties of Siegel modular forms, arXiv, 2013.
        '''
        R = PolynomialRing(QQ, "r1, r2, r3")
        (r1, r2, r3) = R.gens()
        S = PolynomialRing(R, "u1, u2")
        (u1, u2) = S.gens()
        pl = (r1 * u1 ** 2 + r2 * u1 * u2 + r3 * u2 ** 2) ** (j // 2)
        pldct = pl.dict()
        formsdict = {}
        for (_, i), ply in pldct.iteritems():
            formsdict[i] = sum([v * self._differential_operator_monomial(a, b, c)
                                for (a, b, c), v in ply.dict().iteritems()])
        forms = [x for _, x in
                 sorted([(i, v) for i, v in formsdict.iteritems()],
                        key=lambda x: x[0])]
        return SymWtGenElt(forms, self.prec, self.base_ring)

def main1():
    S = PolynomialRing(GF(Integer(13)), names=('x',))
    (x,) = S.gens()
    R = S.quotient(x**Integer(2) - Integer(3), names=('alpha',))
    (alpha,) = R.gens()
    print((Integer(2) + Integer(3) * alpha)
          * (Integer(1) + Integer(2) * alpha))

def to_polredabs(K):
    """

    INPUT: 

    * "K" - a number field
    
    OUTPUT:

    * "phi" - an isomorphism K -> L, where L = QQ['x']/f and f a polynomial such that f = polredabs(f)
    """
    R = PolynomialRing(QQ,'x')
    x = R.gen(0)
    if K == QQ:
        L = QQ.extension(x,'w')
        return QQ.hom(L)
    L = K.absolute_field('a')
    m1 = L.structure()[1]
    f = L.absolute_polynomial()
    g = pari(f).polredabs(1)
    g,h = g[0].sage(locals={'x':x}),g[1].lift().sage(locals={'x':x})
    if debug:
        print 'f',f
        print 'g',g
        print 'h',h
    M = QQ.extension(g,'w')
    m2 = L.hom([h(M.gen(0))])
    return m2*m1

def test_karatsuba_multiplication(base_ring, maxdeg1, maxdeg2,
        ref_mul=lambda f, g: f._mul_generic(g), base_ring_random_elt_args=[],
        numtests=10, verbose=False):
    """
    Test univariate karatsuba multiplication against other multiplication algorithms.

    EXAMPLES:

    First check that random tests are reproducible::

        sage: import sage.rings.tests
        sage: sage.rings.tests.test_karatsuba_multiplication(ZZ, 6, 5, verbose=True, seed=42)
        test_karatsuba_multiplication: ring=Univariate Polynomial Ring in x over Integer Ring, threshold=2
          (2*x^6 - x^5 - x^4 - 3*x^3 + 4*x^2 + 4*x + 1)*(4*x^4 + x^3 - 2*x^2 - 20*x + 3)
          (16*x^2)*(x^2 - 41*x + 1)
          (-x + 1)*(x^2 + 2*x + 8)
          (-x^6 - x^4 - 8*x^3 - x^2 - 4*x + 3)*(-x^3 - x^2)
          (2*x^2 + x + 1)*(x^4 - x^3 + 3*x^2 - x)
          (-x^3 + x^2 + x + 1)*(4*x^2 + 76*x - 1)
          (6*x + 1)*(-5*x - 1)
          (-x^3 + 4*x^2 + x)*(-x^5 + 3*x^4 - 2*x + 5)
          (-x^5 + 4*x^4 + x^3 + 21*x^2 + x)*(14*x^3)
          (2*x + 1)*(12*x^3 - 12)

    Test Karatsuba multiplication of polynomials of small degree over some common rings::

        sage: for C in [QQ, ZZ[I], ZZ[I, sqrt(2)], GF(49, 'a'), MatrixSpace(GF(17), 3)]:
        ....:     sage.rings.tests.test_karatsuba_multiplication(C, 10, 10)

    Zero-tests over ``QQbar`` are currently very slow, so we test only very small examples::

        sage.rings.tests.test_karatsuba_multiplication(QQbar, 3, 3, numtests=2)

    Larger degrees (over ``ZZ``, using FLINT)::

        sage: sage.rings.tests.test_karatsuba_multiplication(ZZ, 1000, 1000, ref_mul=lambda f,g: f*g, base_ring_random_elt_args=[1000])

    Some more aggressive tests::

        sage: for C in [QQ, ZZ[I], ZZ[I, sqrt(2)], GF(49, 'a'), MatrixSpace(GF(17), 3)]:
        ....:     sage.rings.tests.test_karatsuba_multiplication(C, 10, 10) # long time
        sage: sage.rings.tests.test_karatsuba_multiplication(ZZ, 10000, 10000, ref_mul=lambda f,g: f*g, base_ring_random_elt_args=[100000])

    """
    from sage.all import randint, PolynomialRing
    threshold = randint(0, min(maxdeg1,maxdeg2))
    R = PolynomialRing(base_ring, 'x')
    if verbose:
        print "test_karatsuba_multiplication: ring={}, threshold={}".format(R, threshold)
    for i in range(numtests):
        f = R.random_element(randint(0, maxdeg1), *base_ring_random_elt_args)
        g = R.random_element(randint(0, maxdeg2), *base_ring_random_elt_args)
        if verbose:
            print "  ({})*({})".format(f, g)
        if ref_mul(f, g) -  f._mul_karatsuba(g, threshold) != 0:
            raise ValueError("Multiplication failed")
    return

 def eu(p):
     """
     local euler factor
     """
     f = rho.local_factor(p)
     co = [ZZ(round(x)) for x in f.coefficients(sparse=False)]
     R = PolynomialRing(QQ, "T")
     T = R.gens()[0]
     return sum( co[n] * T**n for n in range(len(co)))

def _pair_gens_r_s():
    rnames = "r11, r12, r22, s11, s12, s22"
    unames = "u1, u2"
    RS_ring = PolynomialRing(QQ, names=rnames)
    (r11, r12, r22, s11, s12, s22) = RS_ring.gens()
    (u1, u2) = PolynomialRing(RS_ring, names=unames).gens()
    r = r11 * u1 ** 2 + 2 * r12 * u1 * u2 + r22 * u2 ** 2
    s = s11 * u1 ** 2 + 2 * s12 * u1 * u2 + s22 * u2 ** 2
    return (RS_ring.gens(), (u1, u2), (r, s))

def _hecke_pol_krs_lift():
    '''Return the Hecke polynomial of KRS lift of weight det^{13}Sym(10) at 2.
    '''
    R = PolynomialRing(QQ, names="x")
    x = R.gens()[0]
    f = CuspForms(1, 12).basis()[0]
    a = f[2]
    b = QQ(2) ** 11
    return ((1 - (a ** 3 - 3 * a * b) * x + b ** 3 * x ** 2) *
            (1 - a * b * x + b ** 3 * x ** 2))

def _hecke_pol_klingen(k, j):
    '''k: even.
    F: Kligen-Eisenstein series of determinant weight k whose Hecke field is
    the rational filed. Return the Hecke polynomial of F at 2.
    '''
    f = CuspForms(1, k + j).basis()[0]
    R = PolynomialRing(QQ, names="x")
    x = R.gens()[0]
    pl = QQ(1) - f[2] * x + QQ(2) ** (k + j - 1) * x ** 2
    return pl * pl.subs({x: x * QQ(2) ** (k - 2)})

 def polredabs(self):
     if "polredabs" in self._data.keys():
         return self._data["polredabs"]
     else:
         pol = PolynomialRing(QQ, 'x')(self.polynomial())
         pol *= pol.denominator()
         R = pol.parent()
         from sage.all import pari
         pol = R(pari(pol).polredabs())
         self._data["polredabs"] = pol
         return pol

def G_poly(l, m):
    '''The polynomial G of y1, y2 and y3 given in Proposition 3.7, [Kat].
    '''
    R = PolynomialRing(QQ, names="y1, y2, y3")
    y1, y2, y3 = R.gens()
    return sum(binomial(2 * n + l - QQ(5) / QQ(2), n) * y3 ** n *
               sum((-y2) ** nu * (2 * y1) ** (m - 2 * n - 2 * nu) *
                   binomial(l + m - nu - QQ(5) / QQ(2), m - 2 * n - nu) *
                   binomial(m - 2 * n - nu, nu)
                   for nu in range((m - 2 * n) // 2 + 1))
               for n in range(m // 2 + 1))

 def _hecke_tp_charpoly(self, p, var='x', algorithm='linbox'):
     a = p ** (self.wt - 2) + 1
     N = self.klingeneisensteinAndCuspForms()
     S = CuspForms(1, self.wt)
     m = S.dimension()
     R = PolynomialRing(QQ, names=var)
     x = R.gens()[0]
     f = R(S.hecke_matrix(p).charpoly(var=var, algorithm=algorithm))
     f1 = f.subs({x: a ** (-1) * x}) * a ** m
     g = R(N.hecke_matrix(p).charpoly(var=var, algorithm=algorithm))
     return R(g / f1)

 def test_cusp_sp_wt28_hecke_charpoly(self):
     R = PolynomialRing(QQ, names="x")
     x = R.gens()[0]
     pl = (x ** Integer(7) - Integer(599148384) * x ** Integer(6) +
           Integer(85597740037545984) * x ** Integer(5) +
           Integer(4052196666582552432082944) * x ** Integer(4) -
           Integer(992490558368877866775830593536000) * x ** Integer(3) -
           Integer(7786461340613962559507216233894458163200) * x ** Integer(2) +
           Integer(2554655965904300151500968857660777576875950080000) * x +
           Integer(2246305351725266922462270484154998253269432286576640000))
     S = CuspFormsDegree2(28)
     self.assertTrue(R(S.hecke_charpoly(2)) == pl)

 def _get_Rgens(self):
     d = self.dim
     if self.single_generator:
         if self.hecke_ring_power_basis and self.field_poly_root_of_unity != 0:
             R = PolynomialRing(QQ, self._nu_var)
         else:
             R = PolynomialRing(QQ, 'beta')
         beta = R.gen()
         return [beta**i for i in range(d)]
     else:
         R = PolynomialRing(QQ, ['beta%s' % i for i in range(1,d)])
         return [1] + [g for g in R.gens()]

def pol_string_to_list(pol, deg=None, var=None):
    if var is None:
        from lmfdb.hilbert_modular_forms.hilbert_field import findvar
        var = findvar(pol)
        if not var:
            var = 'a'
    pol = PolynomialRing(QQ, var)(str(pol))
    if deg is None:
        fill = 0
    else:
        fill = deg - pol.degree() - 1
    return [str(c) for c in pol.coefficients(sparse=False)] + ['0']*fill

def dict_to_pol(dct, bd=global_prec, base_ring=QQ):
    R = PolynomialRing(base_ring, "u1, u2, q1, q2")
    (u1, u2, q1, q2) = R.gens()
    S = R.quotient(u1 * u2 - 1)
    (uu1, uu2, qq1, qq2) = S.gens()

    l = PrecisionDeg2(bd)
    if not hasattr(dct, "__getitem__"):
        return dct
    return sum([dct[(n, r, m)] * uu1 ** r * qq1 ** n * qq2 ** m
                if r > 0 else dct[(n, r, m)]
                * uu2 ** (-r) * qq1 ** n * qq2 ** m for n, r, m in l])

 def polredabs(self):
     if "polredabs" in self._data.keys():
         return self._data["polredabs"]
     else:
         pol = PolynomialRing(QQ, 'x')(map(str,self.polynomial()))
         # Need to map because the coefficients are given as unicode, which does not convert to QQ
         pol *= pol.denominator()
         R = pol.parent()
         from sage.all import pari
         pol = R(pari(pol).polredabs())
         self._data["polredabs"] = pol
         return pol

def _to_polynomial(f, val1):
    prec = f.prec.value
    R = PolynomialRing(QQ if f.base_ring == ZZ else f.base_ring,
                       names="q1, q2")
    q1, q2 = R.gens()
    I = R.ideal([q1 ** (prec + 1), q2 ** (prec + 1)])
    S = R.quotient_ring(I)
    res = sum([sum([f.fc_dct.get((n, r, m), 0) * QQ(val1) ** r
                    for r in range(-int(floor(2 * sqrt(n * m))), int(floor(2 * sqrt(n * m))) + 1)])
               * q1 ** n * q2 ** m
               for n in range(prec + 1)
               for m in range(prec + 1)])
    return S(res)

def coeffs_to_poly(c_string):
    """Given a string of coefficients, returns the polynomial with those coefficients

    INPUT:
        c_string -- string, a a comma-separated string (with no spaces) of rational numbers

    OUTPUT:
        The polynomial with these coefficients
    """
    R = PolynomialRing(QQ, names=('x',))
    (x,) = R._first_ngens(1)
    tup = eval(c_string)
    return sum([tup[i]*x**i for i in range(0,len(tup))])