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 sage_residue_field_degrees_function(nf):
    """ Version of above which takes a sage number field
        Used by Artin representation code when the Artin field is not
        in the database.
    """
    D = nf.disc()
    return main_work(pari(nf),D,'sage')

 def f(l_min, l_max):
     from pymongo import Connection
     C = Connection(address).research
     C.authenticate(user, password)
     C = C.ellcurves
     for v in C.find({'level':{'$gte':level_min, '$lt':level_max},
                      'number':1,
                      'ap':{'$exists':False}}):
         E = pari('ellinit(%s,1)'%v['weq'])
         ap = dict([(str(p),int(E.ellap(p))) for p in P])
         C.update({'_id':v['_id']}, {'$set':{'ap':ap}})

 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 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 bounded_elements(N):
    """
    Return elements in maximal order of B that have reduced norm
    whose trace is at most N.

    EXAMPLES::

        sage: from sage.modular.hilbert.sqrt5 import bounded_elements
        sage: X = bounded_elements(3)
        sage: len(X)
        180
        sage: rnX = [a.reduced_norm() for a in X]
        sage: set([a.trace() for a in rnX])
        set([2, 3])
        sage: set([a.norm() for a in rnX])
        set([1])
        sage: X = bounded_elements(5)
        sage: len(X)
        1200
        sage: rnX = [a.reduced_norm() for a in X]
        sage: set([a.trace() for a in rnX])
        set([2, 3, 4, 5])
        sage: set([a.norm() for a in rnX])
        set([1, 4, 5])    
    """
    # Get our maximal order
    R = icosian_ring_gens_over_ZZ()
    
    # Compute Gram matrix of R
    G = gram_matrix_of_maximal_order(R)

    # Make PARI quadratic form
    from sage.all import pari
    qf = pari(G)

    # Get the vectors of norm up to N.
    # The 2 is because we had to scale by 2 to get
    # rid of denominator in Gram matrix. 
    Z = qfminim(qf, N)
    Z2 = Z[2].sage().transpose()

    # For each vector, make the corresponding element of B.
    # TODO: This step massively dominates the runtime, and can be
    # easily made trivial with careful thought.
    V = []
    for i in range(Z2.nrows()):
        w = Z2[i]
        V.append(sum(w[j]*R[j] for j in range(8)))
    return V

 def alpha(self, z):
     """
     INPUT:
         - z - an element of P^1(O_F/P).
     """
     W = self.ideal_basis(z)
     G = self.ideal_gram(W)
     from sage.all import pari
     qf = pari(G)
     t = self.pi.trace()
     c = qfminim(qf, t)
     #print "number of vectors", c[0]
     for r in c[2].sage().transpose():
         a = sum([W[i]*r[i] for i in range(8)])
         if a.reduced_norm() == self.pi:
             return a
     raise ValueError, "bug"

def modular_units_of_degree(G,deg,rational = True, verbose = False,qfminim_bound = 10**5):
    """
    Returns an iterator over all modular units on the curve X(G).
    
    INPUT:
        
    - ``G`` - a congruence subgroup
    - ``deg`` - int, the degree of modular unit to search for
    - ``rational`` - bool, true means modular unit should be defined over QQ
    - ``verbose`` - bool (default = false), wether or not to print progress
    - ``qfminim_bound`` - int (default - 10^5), given to pari's qfminim command, and is an upper bound on
                          how many vectors of short l2 norm are returned by pari
                          this function will raise an error if pari finds more short
                          vectors then it returns

    """
    if rational:
        L,D=rational_modular_unit_lattice(G)
    else:
        L,D=modular_unit_lattice(G)
    
    M = L.basis_matrix().change_ring(ZZ).LLL()
    
       
    GS_matrix=M*M.transpose()
    pari_gs=pari(GS_matrix)
    
    
    short_vectors=pari_gs.qfminim(deg**2*2,qfminim_bound)
    
    if verbose:
        print short_vectors[:2]
    
    count = 0
    for i in short_vectors[2]:
        count+=1
        if verbose and count%10000==0:
            print count
        v=vector(QQ,i.list())*M
        if v.norm(1)/2 == deg:
            yield L(v)
    assert short_vectors[0].sage() < 2*qfminim_bound

 def G_name(self):
     """
     More-or-less standardized name of the abstract group
     """
     import re
     wnf = WebNumberField.from_polredabs(self.polredabs())
     if not wnf.is_null():
         mygalstring = wnf.galois_string()
         if re.search('Trivial', mygalstring) is not None:
             return '$C_1$'
         # Have to remove dollar signs
         return mygalstring
     if self.polredabs().degree() < 12:
         # Let pari compute it for us now
         from sage.all import pari
         galt = int(list(pari('polgalois(' + str(self.polredabs()) + ')'))[2])
         from lmfdb.transitive_group import WebGaloisGroup
         tg = WebGaloisGroup.from_nt(self.polredabs().degree(), galt)
         return tg.display_short()
     return self._data["G-Name"]

    def __init__(self, number_field, mod_ideal = 1, mod_archimedean = None):
        if mod_archimedean == None:
            mod_archimedean = [0] * len(number_field.real_places())
        mod_ideal = number_field.ideal( mod_ideal )

        bnf = gp(number_field.pari_bnf())
        # Use PARI to compute ray class group
        bnr = bnf.bnrinit([mod_ideal, mod_archimedean],1)
        invariants = bnr[5][2]         # bnr.clgp.cyc
        invariants = tuple([ Integer(x) for x in invariants ])
        names = tuple([ "I%i"%i for i in range(len(invariants)) ])
        generators = bnr[5][3]         # bnr.gen = bnr.clgp[3]
        generators = [ number_field.ideal(pari(x)) for x in generators ]

        AbelianGroup_class.__init__(self, invariants, names)
        self.__number_field = number_field
        self.__bnr = bnr
        self.__pari_mod = bnr[2][1]
        self.__mod_ideal = mod_ideal
        self.__mod_arch = mod_archimedean
        self.__generators = generators

def residue_field_degrees_function(K):
    """ Given a sage field, returns a function that has
            input: a prime p
            output: the residue field degrees at the prime p
    """
    k1 = pari(K)
    D = K.disc()

    def decomposition(p):
        if not ZZ(p).divides(D):
            #dec = k1.idealprimedec(p)
#  ar = ArtinRepresentation(1,29,1)
            print 'decomposing prime...***'
            try:
                print 'TRYING GP2'
                dec = gp2.idealprimedec(k1, p)
            except:
                dec = gp.idealprimedec(k1, p)
            dec = [z[3] for z in dec]
            return dec
        else:
            raise ValueError("Expecting a prime not dividing D")
    return decomposition

def polredabs(pol):
    return sagepol(pari(pol).polredabs()) if pol.base_ring()==QQ else pol

 def from_polynomial(cls, pol):
     pol = PolynomialRing(QQ, 'x')(str(pol))
     pol *= pol.denominator()
     R = pol.parent()
     pol = R(pari(pol).polredbest().polredabs())
     return cls.from_coeffs([int(c) for c in pol.coefficients(sparse=False)])

 def zk(self):
     if self.haskey('zk'):
         zkstrings = self._data['zk']
         return [str(u) for u in zkstrings]
     return list(pari(self.poly()).nfbasis())

def render_field_webpage(args):
    data = None
    C = base.getDBConnection()
    info = {}
    bread = [("Global Number Fields", url_for(".number_field_render_webpage"))]

    if "label" in args:
        label = clean_input(args["label"])
        nf = WebNumberField(label)
        data = {}
    if nf.is_null():
        bread.append(("Search results", " "))
        label2 = re.sub(r"[<>]", "", args["label"])
        if "You need to enter a field" in label2:
            info["err"] = label2
        else:
            info["err"] = "No such field: %s in the database" % label2
        info["label"] = args["label_orig"] if "label_orig" in args else args["label"]
        return search_input_error(info, bread)

    info["wnf"] = nf
    data["degree"] = nf.degree()
    data["class_number"] = nf.class_number()
    t = nf.galois_t()
    n = nf.degree()
    data["is_galois"] = nf.is_galois()
    data["is_abelian"] = nf.is_abelian()
    if nf.is_abelian():
        conductor = nf.conductor()
        data["conductor"] = conductor
        dirichlet_chars = nf.dirichlet_group()
        if len(dirichlet_chars) > 0:
            data["dirichlet_group"] = [
                '<a href = "%s">$\chi_{%s}(%s,&middot;)$</a>'
                % (url_character(type="Dirichlet", modulus=data["conductor"], number=j), data["conductor"], j)
                for j in dirichlet_chars
            ]
            data["dirichlet_group"] = r"$\lbrace$" + ", ".join(data["dirichlet_group"]) + r"$\rbrace$"
        if data["conductor"].is_prime() or data["conductor"] == 1:
            data["conductor"] = "\(%s\)" % str(data["conductor"])
        else:
            data["conductor"] = "\(%s=%s\)" % (str(data["conductor"]), latex(data["conductor"].factor()))
    data["galois_group"] = group_display_knowl(n, t, C)
    data["cclasses"] = cclasses_display_knowl(n, t, C)
    data["character_table"] = character_table_display_knowl(n, t, C)
    data["class_group"] = nf.class_group()
    data["class_group_invs"] = nf.class_group_invariants()
    data["signature"] = nf.signature()
    data["coefficients"] = nf.coeffs()
    D = nf.disc()
    ram_primes = D.prime_factors()
    data["disc_factor"] = nf.disc_factored_latex()
    if D.abs().is_prime() or D == 1:
        data["discriminant"] = "\(%s\)" % str(D)
    else:
        data["discriminant"] = "\(%s=%s\)" % (str(D), data["disc_factor"])
    npr = len(ram_primes)
    ram_primes = str(ram_primes)[1:-1]
    if ram_primes == "":
        ram_primes = r"\textrm{None}"
    data["frob_data"], data["seeram"] = frobs(nf.K())
    data["phrase"] = group_phrase(n, t, C)
    zk = pari(nf.K()).nf_subst("a")
    zk = list(zk.nf_get_zk())
    Ra = PolynomialRing(QQ, "a")
    zk = [latex(Ra(x)) for x in zk]
    zk = ["$%s$" % x for x in zk]
    zk = ", ".join(zk)
    grh_label = (
        '<small>(<a title="assuming GRH" knowl="nf.assuming_grh">assuming GRH</a>)</small>' if nf.used_grh() else ""
    )
    # Short version for properties
    grh_lab = nf.short_grh_string()
    pretty_label = field_pretty(label)
    if label != pretty_label:
        pretty_label = "%s: %s" % (label, pretty_label)

    info.update(data)
    info.update(
        {
            "label": pretty_label,
            "label_raw": label,
            "polynomial": web_latex_split_on_pm(nf.K().defining_polynomial()),
            "ram_primes": ram_primes,
            "integral_basis": zk,
            "regulator": web_latex(nf.regulator()),
            "unit_rank": nf.unit_rank(),
            "root_of_unity": web_latex(nf.K().primitive_root_of_unity()),
            "fund_units": nf.units(),
            "grh_label": grh_label,
        }
    )

    bread.append(("%s" % info["label_raw"], " "))
    info["downloads_visible"] = True
    info["downloads"] = [("worksheet", "/")]
    info["friends"] = []
    if nf.can_class_number():
        info["friends"].append(("L-function", "/L/NumberField/%s" % label))
    info["friends"].append(("Galois group", "/GaloisGroup/%dT%d" % (n, t)))
#.........这里部分代码省略.........

def render_field_webpage(args):
    data = None
    C = base.getDBConnection()
    info = {}
    bread = [('Global Number Fields', url_for(".number_field_render_webpage"))]

    # This function should not be called unless label is set.
    label = clean_input(args['label'])
    nf = WebNumberField(label)
    data = {}
    if nf.is_null():
        bread.append(('Search results', ' '))
        info['err'] = 'There is no field with label %s in the database' % label
        info['label'] = args['label_orig'] if 'label_orig' in args else args['label']
        return search_input_error(info, bread)

    info['wnf'] = nf
    data['degree'] = nf.degree()
    data['class_number'] = nf.class_number()
    t = nf.galois_t()
    n = nf.degree()
    data['is_galois'] = nf.is_galois()
    data['is_abelian'] = nf.is_abelian()
    if nf.is_abelian():
        conductor = nf.conductor()
        data['conductor'] = conductor
        dirichlet_chars = nf.dirichlet_group()
        if len(dirichlet_chars)>0:
            data['dirichlet_group'] = ['<a href = "%s">$\chi_{%s}(%s,&middot;)$</a>' % (url_for('characters.render_Dirichletwebpage',modulus=data['conductor'], number=j), data['conductor'], j) for j in dirichlet_chars]
            data['dirichlet_group'] = r'$\lbrace$' + ', '.join(data['dirichlet_group']) + r'$\rbrace$'
        if data['conductor'].is_prime() or data['conductor'] == 1:
            data['conductor'] = "\(%s\)" % str(data['conductor'])
        else:
            data['conductor'] = "\(%s=%s\)" % (str(data['conductor']), latex(data['conductor'].factor()))
    data['galois_group'] = group_display_knowl(n, t, C)
    data['cclasses'] = cclasses_display_knowl(n, t, C)
    data['character_table'] = character_table_display_knowl(n, t, C)
    data['class_group'] = nf.class_group()
    data['class_group_invs'] = nf.class_group_invariants()
    data['signature'] = nf.signature()
    data['coefficients'] = nf.coeffs()
    nf.make_code_snippets()
    D = nf.disc()
    ram_primes = D.prime_factors()
    data['disc_factor'] = nf.disc_factored_latex()
    if D.abs().is_prime() or D == 1:
        data['discriminant'] = "\(%s\)" % str(D)
    else:
        data['discriminant'] = "\(%s=%s\)" % (str(D), data['disc_factor'])
    npr = len(ram_primes)
    ram_primes = str(ram_primes)[1:-1]
    if ram_primes == '':
        ram_primes = r'\textrm{None}'
    data['frob_data'], data['seeram'] = frobs(nf)
    data['phrase'] = group_phrase(n, t, C)
    zk = nf.zk()
    Ra = PolynomialRing(QQ, 'a')
    zk = [latex(Ra(x)) for x in zk]
    zk = ['$%s$' % x for x in zk]
    zk = ', '.join(zk)
    grh_label = '<small>(<a title="assuming GRH" knowl="nf.assuming_grh">assuming GRH</a>)</small>' if nf.used_grh() else ''
    # Short version for properties
    grh_lab = nf.short_grh_string()
    if 'Not' in str(data['class_number']):
        grh_lab=''
        grh_label=''
    pretty_label = field_pretty(label)
    if label != pretty_label:
        pretty_label = "%s: %s" % (label, pretty_label)

    info.update(data)
    if nf.degree() > 1:
        gpK = nf.gpK()
        rootof1coeff = gpK.nfrootsof1()[2]
        rootofunity = Ra(str(pari("lift(%s)" % gpK.nfbasistoalg(rootof1coeff))).replace('x','a'))
    else:
        rootofunity = Ra('-1')

    info.update({
        'label': pretty_label,
        'label_raw': label,
        'polynomial': web_latex_split_on_pm(nf.poly()),
        'ram_primes': ram_primes,
        'integral_basis': zk,
        'regulator': web_latex(nf.regulator()),
        'unit_rank': nf.unit_rank(),
        'root_of_unity': web_latex(rootofunity),
        'fund_units': nf.units(),
        'grh_label': grh_label
    })

    bread.append(('%s' % info['label_raw'], ' '))
    info['downloads_visible'] = True
    info['downloads'] = [('worksheet', '/')]
    info['friends'] = []
    if nf.can_class_number():
        # hide ones that take a lond time to compute on the fly
        # note that the first degree 4 number field missed the zero of the zeta function
        if abs(D**n) < 50000000:
            info['friends'].append(('L-function', "/L/NumberField/%s" % label))
#.........这里部分代码省略.........

def h(d, prec=53):
    RF = RealField(prec)
    kappa = lambda d: RF(1) / 3 if d == 3 else (RF(1) / 2 if d == 4 else 1)
    return RF(pari("qfbclassno(%s,1)" % (-d))) * kappa(d)

def has_modular_unit_of_degree(G,deg,rational = True, verbose = False,qfminim_bound = 10**5,l2_step=0):
    """
    Returns True,v if the modular curve X(G) has a modular unit v of degree equal to deg, and false,None otherwise.
    
    INPUT:
        
    - ``G`` - a congruence subgroup
    - ``deg`` - int, the degree of modular unit to search for
    - ``rational`` - bool, true means modular unit should be defined over QQ
    - ``verbose`` - bool (default = false), wether or not to print progress
    - ``qfminim_bound`` - int (default - 10^5), given to pari's qfminim command, and is an upper bound on
                          how many vectors of short l2 norm are returned by pari
                          this function will raise an error if pari finds more short
                          vectors then it returns
    - ``l2_step`` - int (default = 0) If l2_step>0 this function first searches the modular units with l2 norm equal to l2_step
                                      then 2*l2_step, 3*l2_step, e.t.c. instead of searching all vectors with l2 norm 2*deg^2.
                                      The l2 norm of a modular unit with divisor n1*c1 + ... + nk*ck is the l2 norm of (n1,...nk). 
    """
    if rational:
        L,D=rational_modular_unit_lattice(G)
    else:
        L,D=modular_unit_lattice(G)
    
    M = L.basis_matrix().change_ring(ZZ).LLL()
    for v in M:
        if v.norm(1)/2 == deg:
            return True,L(v)
       
    GS_matrix=M*M.transpose()
    pari_gs=pari(GS_matrix)
    
    
    #just to speed up positive results
    if l2_step > 0:
        for l2 in range(l2_step,deg**2*2-l2_step+1,l2_step):
            short_vectors=pari_gs.qfminim(l2,qfminim_bound)
            if verbose:
                print short_vectors[:2]
            
            count = 0
            for i in short_vectors[2]:
                count+=1
                if verbose and count%10000==0:
                    print count
                v=vector(QQ,i.list())*M
                if v.norm(1)/2 == deg:
                    return True,L(v)
    
    
    short_vectors=pari_gs.qfminim(deg**2*2,qfminim_bound)
    
    if verbose:
        print short_vectors[:2]
    
    count = 0
    for i in short_vectors[2]:
        count+=1
        if verbose and count%10000==0:
            print count
        v=vector(QQ,i.list())*M
        if v.norm(1)/2 == deg:
            return True,L(v)
    assert short_vectors[0].sage() < 2*qfminim_bound
    return False,None

#.........这里部分代码省略.........
                loc_alg += '<td><a href="%s">%s</a><td>$%s$<td>$%d$<td>$%d$<td>$%d$<td>%s<td>$%s$'%(myurl,lab,mm[1],mm[2],mm[3],mm[4],mm[5],show_slope_content(mm[8],mm[6],mm[7]))
                for mm in mydat[1:]:
                    lab = mm[0]
                    if mm[3]*mm[2]==1:
                        lab = r'$\Q_{%s}$'%str(p)
                    loc_alg += '<tr><td><a href="%s">%s</a><td>$%s$<td>$%d$<td>$%d$<td>$%d$<td>%s<td>$%s$'%(myurl,lab,mm[1],mm[2],mm[3],mm[4],mm[5],show_slope_content(mm[8],mm[6],mm[7]))
        loc_alg += '</tbody></table>'

    ram_primes = str(ram_primes)[1:-1]
    if ram_primes == '':
        ram_primes = r'\textrm{None}'
    data['phrase'] = group_phrase(n, t)
    zk = nf.zk()
    Ra = PolynomialRing(QQ, 'a')
    zk = [latex(Ra(x)) for x in zk]
    zk = ['$%s$' % x for x in zk]
    zk = ', '.join(zk)
    grh_label = '<small>(<a title="assuming GRH" knowl="nf.assuming_grh">assuming GRH</a>)</small>' if nf.used_grh() else ''
    # Short version for properties
    grh_lab = nf.short_grh_string()
    if 'Not' in str(data['class_number']):
        grh_lab=''
        grh_label=''
    pretty_label = field_pretty(label)
    if label != pretty_label:
        pretty_label = "%s: %s" % (label, pretty_label)

    info.update(data)
    if nf.degree() > 1:
        gpK = nf.gpK()
        rootof1coeff = gpK.nfrootsof1()
        rootofunityorder = int(rootof1coeff[1])
        rootof1coeff = rootof1coeff[2]
        rootofunity = web_latex(Ra(str(pari("lift(%s)" % gpK.nfbasistoalg(rootof1coeff))).replace('x','a'))) 
        rootofunity += ' (order $%d$)' % rootofunityorder
    else:
        rootofunity = web_latex(Ra('-1'))+ ' (order $2$)'

    info.update({
        'label': pretty_label,
        'label_raw': label,
        'polynomial': web_latex_split_on_pm(nf.poly()),
        'ram_primes': ram_primes,
        'integral_basis': zk,
        'regulator': web_latex(nf.regulator()),
        'unit_rank': nf.unit_rank(),
        'root_of_unity': rootofunity,
        'fund_units': nf.units(),
        'grh_label': grh_label,
        'loc_alg': loc_alg
    })

    bread.append(('%s' % info['label_raw'], ' '))
    info['downloads_visible'] = True
    info['downloads'] = [('worksheet', '/')]
    info['friends'] = []
    if nf.can_class_number():
        # hide ones that take a lond time to compute on the fly
        # note that the first degree 4 number field missed the zero of the zeta function
        if abs(D**n) < 50000000:
            info['friends'].append(('L-function', "/L/NumberField/%s" % label))
    info['friends'].append(('Galois group', "/GaloisGroup/%dT%d" % (n, t)))
    if 'dirichlet_group' in info:
        info['friends'].append(('Dirichlet character group', url_for("characters.dirichlet_group_table",
                                                           modulus=int(conductor),
                                                           char_number_list=','.join(

 def conductor(self):
     bnr = self.parent().group().bnr()
     pari_cond = pari(bnr.bnrconductorofchar(self.list()))
     finite, arch = pari_cond
     return self.number_field().ideal(finite)