def notpvec(A,p):
    Ap = []
    for a in A:
        ap, aprime = pnotp(a,p)
        Ap.extend([aprime]*euler_phi(ap))
    Ap.sort(reverse=True)
    return Ap

 def from_cyclo(cls, n):
     if euler_phi(n) > 23:
         return cls('none')  # Forced to fail
     pol = pari.polcyclo(n)
     R = PolynomialRing(ZZ, 'x')
     coeffs = R(pol.polredabs()).coefficients(sparse=False)
     return cls.from_coeffs(coeffs)

 def compute(self, save=True):
     emf_logger.debug("in compute for WebChar number {0} of modulus {1}".format(self.number, self.modulus))
     c = self.character
     changed = False
     if self.conductor == 0:
         self.conductor = c.conductor()
         changed = True
     if self.order == 0:
         self.order = c.multiplicative_order()
         changed = True
     if self.latex_name == "":
         self.latex_name = "\chi_{" + str(self.modulus) + "}(" + str(self.number) + ", \cdot)"
         changed = True
     if self._values_algebraic == {} or self._values_float == {}:
         changed = True
         for i in range(self.modulus):
             self.value(i, value_format="float")
             self.value(i, value_format="algebraic")
     if self.modulus_euler_phi == 0:
         changed = True
         self.modulus_euler_phi = euler_phi(self.modulus)
     if changed and save:
         self.save_to_db()
     else:
         emf_logger.debug("Not saving.")

 def compute(self, save=True):
     emf_logger.debug('in compute for WebChar number {0} of modulus {1}'.format(self.number, self.modulus))
     c = self.character
     changed = False
     if self.conductor == 0:            
         self.conductor = c.conductor()
         changed = True
     if self.order == 0:
         self.order = c.multiplicative_order()
         changed = True
     if self.latex_name == '':
         self.latex_name = "\chi_{" + str(self.modulus) + "}(" + str(self.number) + ", \cdot)"
         changed = True
     if self._values_algebraic == {} or self._values_float == {}:
         changed = True
         for i in range(self.modulus):
             self.value(i,value_format='float')
             self.value(i,value_format='algebraic')
     if self.modulus_euler_phi == 0:
         changed = True
         self.modulus_euler_phi = euler_phi(self.modulus)
     if changed and save and False:  # temporary hack to prevent fatal error when save_to_db fails
         self.save_to_db()
     else:            
         emf_logger.debug('Not saving.')

 def check_character_values(self, rec, verbose=False):
     """
     The x's listed in values and values_gens should be coprime to the modulus N in the label.
     For x's that appear in both values and values_gens, the value should be the same.
     """
     # TIME about 3000s for full table
     N = Integer(rec['modulus'])
     v2, u2 = N.val_unit(2)
     if v2 == 1:
         # Z/2 doesn't contribute generators, but 2 divides N
         adjust2 = -1
     elif v2 >= 3:
         # Z/8 and above requires two generators
         adjust2 = 1
     else:
         adjust2 = 0
     if N == 1:
         # The character stores a value in the case N=1
         ngens = 1
     else:
         ngens = len(N.factor()) + adjust2
     vals = rec['values']
     val_gens = rec['values_gens']
     val_gens_dict = dict(val_gens)
     if len(vals) != min(12, euler_phi(N)) or len(val_gens) != ngens:
         if verbose:
             print "Length failure", len(vals), euler_phi(N), len(val_gens), ngens
         return False
     if N > 2 and (vals[0][0] != N-1 or vals[1][0] != 1 or vals[1][1] != 0 or vals[0][1] not in [0, rec['order']//2]):
         if verbose:
             print "Initial value failure", N, rec['order'], vals[:2]
         return False
     if any(N.gcd(g) > 1 for g, gval in val_gens+vals):
         if verbose:
             print "gcd failure", [g for g, gval in val_gens+vals if N.gcd(g) > 1]
         return False
     for g, val in vals:
         if g in val_gens_dict and val != val_gens_dict[g]:
             if verbose:
                 print "Mismatch failure", g, val, val_gens_dict[g]
             return False
     return True

def degree_cusp(i,N):
    """
    Function DegreeCusp in Mark his code 
    
    returns the degree over Q of the cusp $q^(i/n)\zeta_n^j$ on X_1(N)
    """
    i = ZZ(i); N = ZZ(N)
    d = euler_phi(gcd(i,N))
    if i == 0 or 2*i == N:
        return ceil(d/2)
    return d

    def dbd(self, d):
        """
        Return matrix of <d>.

        INPUT:

            - `d` -- integer

        OUTPUT:

            - a matrix modulo 2

        EXAMPLES::

            sage: from mdsage import *
            sage: C = KamiennyCriterion(29)
            sage: C.dbd(2)
            22 x 22 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
            sage: C.dbd(2)^14==1
            True
            sage: C.dbd(2)[0]
            (0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1)
        """
        d=ZZ(d)
        if self.verbose: tm = cputime(); mem = get_memory_usage(); print "dbd start"
        try: return self._dbd[d % self.p]
        except AttributeError: pass
        # Find generators of the integers modulo p:
        gens = Integers(self.p).unit_gens()
        orders = [g.multiplicative_order() for g in gens]
        # Compute corresponding <z> operator on integral cuspidal modular symbols
        
        X = [self.M.diamond_bracket_operator(z).matrix() for z in gens]
        if self.verbose: print "time and mem", cputime(tm), get_memory_usage(mem), "create d"
        X = [x.restrict(self.S_integral, check=False) for x in X]
        if self.verbose: print "time and mem", cputime(tm), get_memory_usage(mem), "restrict d"
        
        X = [matrix_modp(x) for x in X]
        if self.verbose: print "time and mem", cputime(tm), get_memory_usage(mem), "mod d"
        # Take combinations to make list self._dbd of all dbd's such that
        # self._dbd[d] = <d>
        from itertools import product
        v = [None] * self.p
        for ei in product(*[range(i) for i in orders]):
            di = prod(g**e for e,g in zip(ei,gens)).lift()
            m = prod(g**e for e,g in zip(ei,X))
            v[di] = m
        if self.verbose: print "time and mem", cputime(tm), get_memory_usage(mem), "mul"

        assert v.count(None) == (self.p-euler_phi(self.p))
        self._dbd = v
        if self.verbose: print "time and mem", cputime(tm), get_memory_usage(mem), "bdb finnished"
        return v[d % self.p]

def parse_field_string(F):  # parse Q, Qsqrt2, Qsqrt-4, Qzeta5, etc
    if F == "Q":
        return "1.1.1.1"
    if F == "Qi":
        return "2.0.4.1"
    # Change unicode dash with minus sign
    F = F.replace(u"\u2212", "-")
    # remove non-ascii characters from F
    F = F.decode("utf8").encode("ascii", "ignore")
    fail_string = str(F + " is not a valid field label or name or polynomial, or is not ")
    if len(F) == 0:
        return "Entry for the field was left blank.  You need to enter a field label, field name, or a polynomial."
    if F[0] == "Q":
        if F[1:5] in ["sqrt", "root"]:
            try:
                d = ZZ(str(F[5:])).squarefree_part()
            except ValueError:
                return fail_string
            if d % 4 in [2, 3]:
                D = 4 * d
            else:
                D = d
            absD = D.abs()
            s = 0 if D < 0 else 2
            return "2.%s.%s.1" % (s, str(absD))
        if F[1:5] == "zeta":
            try:
                d = ZZ(str(F[5:]))
            except ValueError:
                return fail_string
            if d < 1:
                return fail_string
            if d % 4 == 2:
                d /= 2  # Q(zeta_6)=Q(zeta_3), etc)
            if d == 1:
                return "1.1.1.1"
            deg = euler_phi(d)
            if deg > 23:
                return "%s is not " % F
            adisc = CyclotomicField(d).discriminant().abs()  # uses formula!
            return "%s.0.%s.1" % (deg, adisc)
        return fail_string
    # check if a polynomial was entered
    F = F.replace("X", "x")
    if "x" in F:
        F1 = F.replace("^", "**")
        # print F
        F1 = poly_to_field_label(F1)
        if F1:
            return F1
        return str(F + " is not ")
    return F

def id_dirichlet(fun, N, n):
    N = Integer(N)
    if N == 1:
        return (1, 1)
    p2 = valuation(N, 2)
    N2 = 2 ** p2
    Nodd = N / N2
    Nfact = list(factor(Nodd))
    # print "n = "+str(n)
    # for j in range(20):
    #    print "chi(%d) = e(%d/%d)"%(j+2, fun(j+2,n), n)
    plist = [z[0] for z in Nfact]
    ppows = [z[0] ** z[1] for z in Nfact]
    ppows2 = list(ppows)
    idems = [1 for z in Nfact]
    proots = [primitive_root(z) for z in ppows]
    # Get CRT idempotents
    if p2 > 0:
        ppows2.append(N2)
    for j in range(len(plist)):
        exps = [1 for z in idems]
        if p2 > 0:
            exps.append(1)
        exps[j] = proots[j]
        idems[j] = crt(exps, ppows2)
    idemvals = [fun(z, n) for z in idems]
    # now normalize to right root of unity base
    idemvals = [idemvals[j] * euler_phi(ppows[j]) / n for j in range(len(idemvals))]
    ans = [Integer(mod(proots[j], ppows[j]) ** idemvals[j]) for j in range(len(proots))]
    ans = crt(ans, ppows)
    # There are cases depending on 2-part of N
    if p2 == 0:
        return (N, ans)
    if p2 == 1:
        return (N, crt([1, ans], [2, Nodd]))
    if p2 == 2:
        my3 = crt([3, 1], [N2, Nodd])
        if fun(my3, n) == 0:
            return (N, crt([1, ans], [4, Nodd]))
        else:
            return (N, crt([3, ans], [4, Nodd]))
    # Final case 2^3 | N

    my5 = crt([5, 1], [N2, Nodd])
    test1 = fun(my5, n) * N2 / 4 / n
    test1 = Integer(mod(5, N2) ** test1)
    minusone = crt([-1, 1], [N2, Nodd])
    test2 = (fun(minusone, n) * N2 / 4 / n) % (N2 / 4)
    if test2 > 0:
        test1 = Integer(mod(-test1, N2))
    return (N, crt([test1, ans], [N2, Nodd]))

def parse_field_string(F):  # parse Q, Qsqrt2, Qsqrt-4, Qzeta5, etc
    if F == "Q":
        return "1.1.1.1"
    if F == "Qi":
        return "2.0.4.1"
    fail_string = str(F + " is not a valid field label or name or polynomial, or is not ")
    if len(F) == 0:
        return "Entry for the field was left blank.  You need to enter a field label, field name, or a polynomial."
    if F[0] == "Q":
        if F[1:5] in ["sqrt", "root"]:
            try:
                d = ZZ(str(F[5:])).squarefree_part()
            except ValueError:
                return fail_string
            if d % 4 in [2, 3]:
                D = 4 * d
            else:
                D = d
            absD = D.abs()
            s = 0 if D < 0 else 2
            return "2.%s.%s.1" % (s, str(absD))
        if F[1:5] == "zeta":
            try:
                d = ZZ(str(F[5:]))
            except ValueError:
                return fail_string
            if d < 1:
                return fail_string
            if d % 4 == 2:
                d /= 2  # Q(zeta_6)=Q(zeta_3), etc)
            if d == 1:
                return "1.1.1.1"
            deg = euler_phi(d)
            if deg > 20:
                return fail_string
            adisc = CyclotomicField(d).discriminant().abs()  # uses formula!
            return "%s.0.%s.1" % (deg, adisc)
        return fail_string
    # check if a polynomial was entered
    F = F.replace("X", "x")
    if "x" in F:
        F = F.replace("^", "**")
        # print F
        F = poly_to_field_label(F)
        if F:
            return F
        return fail_string
    return F

def _dir_knowl_data(label, orbit=False):
    modulus, number = label.split('.')
    modulus = int(modulus)
    numbers = label_to_number(modulus, number, all=True)
    if numbers == 0:
        return "Invalid label for Dirichlet character: %s" % label
    if isinstance(numbers, list):
        number = numbers[0]
        def conrey_link(i):
            return "<a href='%s'> %s.%s</a>" % (url_for("characters.render_Dirichletwebpage", modulus=modulus, number=i), modulus, i)
        if len(numbers) <= 2:
            numbers = map(conrey_link, numbers)
        else:
            numbers = [conrey_link(numbers[0]), '&#8230;', conrey_link(numbers[-1])]
    else:
        number = numbers
        numbers = None
    args={'type': 'Dirichlet', 'modulus': modulus, 'number': number}
    webchar = make_webchar(args)
    if orbit and modulus <= 10000:
        inf = "Dirichlet Character Orbit %d.%s\n" % (modulus, webchar.orbit_label)
    else:
        inf = r"Dirichlet Character \(\chi_{%d}(%d, \cdot)\)" % (modulus, number) + "\n"
    inf += "<div><table class='chardata'>\n"
    def row_wrap(header, val):
        return "<tr><td>%s: </td><td>%s</td></tr>\n" % (header, val)
    inf += row_wrap('Conductor', webchar.conductor)
    inf += row_wrap('Order', webchar.order)
    inf += row_wrap('Degree', euler_phi(webchar.order))
    inf += row_wrap('Parity', "Even" if webchar.parity == 1 else "Odd")
    if numbers:
        inf += row_wrap('Characters', ",&nbsp;".join(numbers))
    if modulus <= 10000:
        if not orbit:
            inf += row_wrap('Orbit Label', '%d.%s' % (modulus, webchar.orbit_label))
        inf += row_wrap('Orbit Index', webchar.orbit_index)
    inf += '</table></div>\n'
    if numbers is None:
        inf += '<div align="right">\n'
        inf += '<a href="%s">%s home page</a>\n' % (str(url_for("characters.render_Dirichletwebpage", modulus=modulus, number=number)), label)
        inf += '</div>\n'
    return inf

 def init_dynamic_properties(self, embeddings=False):
     if self.number is not None:            
         emf_logger.debug('number: {0}'.format(self.number))
         self.character = DirichletCharacter_conrey(DirichletGroup_conrey(self.modulus),self.number)
         if not self.number == 1:
             self.sage_character = self.character.sage_character()
         else:
             self.sage_character = trivial_character(self.modulus)
         self.name = "Character nr. {0} of modulus {1}".format(self.number,self.modulus)
         if embeddings:
             from lmfdb.modular_forms.elliptic_modular_forms.backend.emf_utils import dirichlet_character_conrey_galois_orbit_embeddings
             emb = dirichlet_character_conrey_galois_orbit_embeddings(self.modulus,self.number)
             self.set_embeddings(emb)
         c = self.character
         if self.conductor == 0:            
             self.conductor = c.conductor()
         if self.order == 0:
             self.order = c.multiplicative_order()
         if self.modulus_euler_phi == 0:
             self.modulus_euler_phi = euler_phi(self.modulus)
         if self.latex_name == '':
             self.latex_name = "\chi_{" + str(self.modulus) + "}(" + str(self.number) + ", \cdot)"

    def dirichlet_group(self, prime_bound=10000):
        f = self.conductor()
        if f == 1:  # To make the trivial case work correctly
            return [1]
        if euler_phi(f) > dir_group_size_bound:
            return []
        # Can do quadratic fields directly
        if self.degree() == 2:
            if is_odd(f):
                return [1, f-1]
            f1 = f/4
            if is_odd(f1):
                return [1, f-1]
            # we now want f with all powers of 2 removed
            f1 = f1/2
            if is_even(f1):
                raise Exception('Invalid conductor')
            if (self.disc()/8) % 4 == 3:
                return [1, 4*f1-1]
            # Finally we want congruent to 5 mod 8 and -1 mod f1
            if (f1 % 4) == 3:
                return [1, 2*f1-1]
            return [1, 6*f1-1]

        from dirichlet_conrey import DirichletGroup_conrey
        G = DirichletGroup_conrey(f)
        K = self.K()
        S = Set(G[1].kernel()) # trivial character, kernel is whole group

        for P in K.primes_of_bounded_norm_iter(ZZ(prime_bound)):
            a = P.norm() % f
            if gcd(a,f)>1:
                continue
            S = S.intersection(Set(G[a].kernel()))
            if len(S) == self.degree():
                return list(S)

        raise Exception('Failure in dirichlet group for K=%s using prime bound %s' % (K,prime_bound))

def run(num_bits,k):
    """
    Description:
    
        Runs the Dupont-Enge-Morain method multiple times until a valid curve is found
    
    Input:
    
        num_bits - number of bits
        k - an embedding degree
    
    Output:
    
        (q,t,r,k,D) - an elliptic curve;
                      if no curve is found, the algorithm returns (0,0,0,k,0)
    
    """
    j,r,q,t = 0,0,0,0
    num_generates = 512
    h = num_bits/(euler_phi(k))
    tried = [(0,0)] # keep track of random values tried for efficiency
    for i in range(0,num_generates):
        D = 0
        y = 0
        while (D,y) in tried: # find a pair that we have not tried
            D = -randint(1, 1024) # pick a small D so that the CM method is fast
            D = fundamental_discriminant(D)
            m = 0.5*(h - log(-D).n()/(2*log(2)).n())
            if m < 1:
                m = 1
            y = randint(floor(2**(m-1)), floor(2**m))
        tried.append((D,y))
        q,t,r,k,D = method(num_bits,k,D,y) # run DEM
        if q != 0 and t != 0 and r != 0 and k != 0 and D != 0: # found an answer, so output it
            assert is_valid_curve(q,t,r,k,D), 'Invalid output'
            return q,t,r,k,D
    return 0,0,0,k,0 # found nothing

 def check_char_degree(self, rec, verbose=False):
     """
     check that char_degree = euler_phi(order)
     """
     # TIME about 20s for full table
     return self._test_equality(rec['char_degree'], euler_phi(rec['order']), verbose)

def Phi(d):
    """
    Function Phi in Mark his code
    """
    d = ZZ(d)
    return euler_phi(d) / d

    def set_twist_info(self, prec=10,insert_in_db=True):
        r"""
        Try to find forms of lower level which get twisted into self.
        OUTPUT:

        -''[t,l]'' -- tuple of a Bool t and a list l. The list l contains all tuples of forms which twists to the given form.
        The actual minimal one is the first element of this list.
             t is set to True if self is minimal and False otherwise


        EXAMPLES::



        """
        if(len(self._twist_info) > 0):
            return self._twist_info
        N = self.level()
        k = self.weight()
        if(is_squarefree(ZZ(N))):
            self._twist_info = [True, None ]
            return [True, None]

        # We need to check all square factors of N
        twist_candidates = list()
        KF = self.base_ring()
        # check how many Hecke eigenvalues we need to check
        max_nump = self._number_of_hecke_eigenvalues_to_check()
        maxp = max(primes_first_n(max_nump))
        for d in divisors(N):
            if(d == 1):
                continue
            # we look at all d such that d^2 divdes N
            if(not ZZ(d ** 2).divides(ZZ(N))):
                continue
            D = DirichletGroup(d)
            # check possible candidates to twist into f
            # g in S_k(M,chi) wit M=N/d^2
            M = ZZ(N / d ** 2)
            if(self._verbose > 0):
                wmf_logger.debug("Checking level {0}".format(M))
            for xig in range(euler_phi(M)):
                (t, glist) = _get_newform(M,k, xig)
                if(not t):
                    return glist
                for g in glist:
                    if(self._verbose > 1):
                        wmf_logger.debug("Comparing to function {0}".format(g))
                    KG = g.base_ring()
                    # we now see if twisting of g by xi in D gives us f
                    for xi in D:
                        try:
                            for p in primes_first_n(max_nump):
                                if(ZZ(p).divides(ZZ(N))):
                                    continue
                                bf = self.as_factor().q_eigenform(maxp + 1, names='x')[p]
                                bg = g.q_expansion(maxp + 1)[p]
                                if(bf == 0 and bg == 0):
                                    continue
                                elif(bf == 0 and bg != 0 or bg == 0 and bf != 0):
                                    raise StopIteration()
                                if(ZZ(p).divides(xi.conductor())):
                                    raise ArithmeticError("")
                                xip = xi(p)
                                # make a preliminary check that the base rings match with respect to being
                                # real or not
                                try:
                                    QQ(xip)
                                    XF = QQ
                                    if(KF != QQ or KG != QQ):
                                        raise StopIteration
                                except TypeError:
                                    # we have a  non-rational (i.e. complex) value of the character
                                    XF = xip.parent()
                                    if((KF.absolute_degree() == 1 or KF.is_totally_real()) and (KG.absolute_degre() == 1 or KG.is_totally_real())):
                                        raise StopIteration
                            ## it is diffcult to compare elements from diferent rings in general but we make some checcks
                            # is it possible to see if there is a larger ring which everything can be
                            # coerced into?
                                ok = False
                                try:
                                    a = KF(bg / xip)
                                    b = KF(bf)
                                    ok = True
                                    if(a != b):
                                        raise StopIteration()
                                except TypeError:
                                    pass
                                try:
                                    a = KG(bg)
                                    b = KG(xip * bf)
                                    ok = True
                                    if(a != b):
                                        raise StopIteration()
                                except TypeError:
                                    pass
                                if(not ok):  # we could coerce and the coefficients were equal
                                    return "Could not compare against possible candidates!"
                                # otherwise if we are here we are ok and found a candidate
                            twist_candidates.append([M, g.q_expansion(prec), xi])
#.........这里部分代码省略.........

 def check_hecke_ring_character_values_and_an(self, rec, verbose=False):
     """
     check that hecke_ring_character_values has the correct format, depending on whether hecke_ring_cyclotomic_generator is set or not
     check that an has length 100 and that each entry is either a list of integers of length hecke_ring_rank (if hecke_ring_cyclotomic_generator=0) or a list of pairs
     check that ap has length pi(maxp) and that each entry is formatted correctly (as for an)
     """
     # TIME about 4000s for full table
     an = rec['an']
     if len(an) != 100:
         if verbose:
             print "Length an", len(an)
         return False
     ap = rec['ap']
     maxp = rec['maxp']
     if len(ap) != prime_pi(maxp):
         if verbose:
             print "Length ap", len(ap), prime_pi(maxp)
         return False
     if maxp < 997:
         if verbose:
             print "Maxp", maxp
         return False
     m = rec['hecke_ring_cyclotomic_generator']
     d = rec['hecke_ring_rank']
     def check_val(val):
         if not isinstance(val, list):
             return False
         if m == 0:
             return len(val) == d and all(isinstance(c, integer_types) for c in val)
         else:
             for pair in val:
                 if len(pair) != 2:
                     return False
                 if not isinstance(pair[0], integer_types):
                     return False
                 e = pair[1]
                 if not (isinstance(e, integer_types) and 0 <= 2*e < m):
                     return False
             return True
     if not all(check_val(a) for a in an):
         if verbose:
             for n, a in enumerate(an, 1):
                 if not check_val(a):
                     print "Check an failure (m=%s, d=%s)"%(m, d), n, a
         return False
     if not all(check_val(a) for a in ap):
         if verbose:
             for p, a in zip(prime_range(maxp), ap):
                 if not check_val(a):
                     print "Check ap failure (m=%s, d=%s)"%(m, d), p, a
         return False
     for p, a in zip(prime_range(100), ap):
         if a != an[p-1]:
             if verbose:
                 print "Match failure", p, a, an[p-1]
             return False
     if rec['char_orbit_index'] != 1:
         if rec.get('hecke_ring_character_values') is None:
             if verbose:
                 print "No hecke_ring_character_values"
             return False
         N = rec['level']
         total_order = 1
         for g, val in rec['hecke_ring_character_values']:
             total_order *= mod(g, N).multiplicative_order()
             if not check_val(val):
                 if verbose:
                     print "Bad character val (m=%s, d=%s)"%(m, d), g, val
                 return False
         success = (total_order == euler_phi(N))
         if not success and verbose:
             print "Generators failed", total_order, euler_phi(N)
         return success
     return True

def nf_string_to_label(F):  # parse Q, Qsqrt2, Qsqrt-4, Qzeta5, etc
    if F == 'Q':
        return '1.1.1.1'
    if F == 'Qi' or F == 'Q(i)':
        return '2.0.4.1'
    # Change unicode dash with minus sign
    F = F.replace(u'\u2212', '-')
    # remove non-ascii characters from F
    F = F.decode('utf8').encode('ascii', 'ignore')
    if len(F) == 0:
        raise ValueError("Entry for the field was left blank.  You need to enter a field label, field name, or a polynomial.")
    if F[0] == 'Q':
        if '(' in F and ')' in F:
            F=F.replace('(','').replace(')','')
        if F[1:5] in ['sqrt', 'root']:
            try:
                d = ZZ(str(F[5:])).squarefree_part()
            except (TypeError, ValueError):
                d = 0
            if d == 0:
                raise ValueError("After {0}, the remainder must be a nonzero integer.  Use {0}5 or {0}-11 for example.".format(F[:5]))
            if d == 1:
                return '1.1.1.1'
            if d % 4 in [2, 3]:
                D = 4 * d
            else:
                D = d
            absD = D.abs()
            s = 0 if D < 0 else 2
            return '2.%s.%s.1' % (s, str(absD))
        if F[1:5] == 'zeta':
            if '_' in F:
                F = F.replace('_','')
            try:
                d = ZZ(str(F[5:]))
            except ValueError:
                d = 0
            if d < 1:
                raise ValueError("After {0}, the remainder must be a positive integer.  Use {0}5 for example.".format(F[:5]))
            if d % 4 == 2:
                d /= 2  # Q(zeta_6)=Q(zeta_3), etc)
            if d == 1:
                return '1.1.1.1'
            deg = euler_phi(d)
            if deg > 23:
                raise ValueError('%s is not in the database.' % F)
            adisc = CyclotomicField(d).discriminant().abs()  # uses formula!
            return '%s.0.%s.1' % (deg, adisc)
        raise ValueError('It is not a valid field name or label, or a defining polynomial.')
    # check if a polynomial was entered
    F = F.replace('X', 'x')
    if 'x' in F:
        F1 = F.replace('^', '**')
        # print F
        from lmfdb.number_fields.number_field import poly_to_field_label
        F1 = poly_to_field_label(F1)
        if F1:
            return F1
        raise ValueError('%s does not define a number field in the database.'%F)
    # Expand out factored labels, like 11.11.11e20.1
    if not re.match(r'\d+\.\d+\.[0-9e_]+\.\d+',F):
        raise ValueError("It must be of the form d.r.D.n, such as 2.2.5.1.")
    parts = F.split(".")
    def raise_power(ab):
        if ab.count("e") == 0:
            return ZZ(ab)
        elif ab.count("e") == 1:
            a,b = ab.split("e")
            return ZZ(a)**ZZ(b)
        else:
            raise ValueError("Malformed absolute discriminant.  It must be a sequence of strings AeB for A and B integers, joined by _s.  For example, 2e7_3e5_11.")
    parts[2] = str(prod(raise_power(c) for c in parts[2].split("_")))
    return ".".join(parts)

def nf_string_to_label(F):  # parse Q, Qsqrt2, Qsqrt-4, Qzeta5, etc
    if F == "Q":
        return "1.1.1.1"
    if F == "Qi":
        return "2.0.4.1"
    # Change unicode dash with minus sign
    F = F.replace(u"\u2212", "-")
    # remove non-ascii characters from F
    F = F.decode("utf8").encode("ascii", "ignore")
    fail_string = str(F + " is not a valid field label or name or polynomial, or is not ")
    if len(F) == 0:
        raise ValueError(
            "Entry for the field was left blank.  You need to enter a field label, field name, or a polynomial."
        )
    if F[0] == "Q":
        if F[1:5] in ["sqrt", "root"]:
            try:
                d = ZZ(str(F[5:])).squarefree_part()
            except ValueError:
                d = 0
            if d == 0:
                raise ValueError(
                    "After {0}, the remainder must be a nonzero integer.  Use {0}5 or {0}-11 for example.".format(F[:5])
                )
            if d % 4 in [2, 3]:
                D = 4 * d
            else:
                D = d
            absD = D.abs()
            s = 0 if D < 0 else 2
            return "2.%s.%s.1" % (s, str(absD))
        if F[1:5] == "zeta":
            try:
                d = ZZ(str(F[5:]))
            except ValueError:
                d = 0
            if d < 1:
                raise ValueError(
                    "After {0}, the remainder must be a positive integer.  Use {0}5 for example.".format(F[:5])
                )
            if d % 4 == 2:
                d /= 2  # Q(zeta_6)=Q(zeta_3), etc)
            if d == 1:
                return "1.1.1.1"
            deg = euler_phi(d)
            if deg > 23:
                raise ValueError("%s is not in the database." % F)
            adisc = CyclotomicField(d).discriminant().abs()  # uses formula!
            return "%s.0.%s.1" % (deg, adisc)
        return fail_string
    # check if a polynomial was entered
    F = F.replace("X", "x")
    if "x" in F:
        F1 = F.replace("^", "**")
        # print F
        from lmfdb.number_fields.number_field import poly_to_field_label

        F1 = poly_to_field_label(F1)
        if F1:
            return F1
        raise ValueError("%s is not in the database." % F)
    # Expand out factored labels, like 11.11.11e20.1
    parts = F.split(".")
    if len(parts) != 4:
        raise ValueError("It must be of the form <deg>.<real_emb>.<absdisc>.<number>, such as 2.2.5.1.")

    def raise_power(ab):
        if ab.count("e") == 0:
            return ZZ(ab)
        elif ab.count("e") == 1:
            a, b = ab.split("e")
            return ZZ(a) ** ZZ(b)
        else:
            raise ValueError(
                "Malformed absolute discriminant.  It must be a sequence of strings AeB for A and B integers, joined by _s.  For example, 2e7_3e5_11."
            )

    parts[2] = str(prod(raise_power(c) for c in parts[2].split("_")))
    return ".".join(parts)