def cmp_ir(self,z):
     """ 
     returns -1 for left, 0 for in, and 1 for right from initial region
     cut line is on the north ray from L.
     """
     L = self.L
     x0 = self.x0
     if x0 > 0.5:
         if real(z) > real(L) and abs(z) < abs(L):
             return 0
         if real(z) < real(L):
             return -1
         if real(z) > real(L):
             return 1
     else:
         if imag(z) > imag(L):
             if real(z) > real(L):
                 return 1
             if real(z) < real(L):
                 return -1
         if real(z) < real(L) and real(z) > log(real(L)) + log(sqrt(1+tan(imag(z))**2)):
             return 0
         if real(z) > real(L):
             return 1
         if real(z) < real(L):
             return -1

    def calc_slog(self):
        RP = FormalPowerSeriesRing(RealField(self.iprec))
        ev = self.eigenvalues
        a1 = self.coeffs_1
        N = self.N

        #how can this be made picklable?
        class _SexpCoeffs1(FormalPowerSeries0):
            def coeffs(self,n):
               if n==0: return 0
               return sum([a1[k]*log(ev[k])**n for k in xrange(N)])/factorial(n)
        class _SexpCoeffs0(FormalPowerSeries0):
            def coeffs(self,n):
               if n==0: return 0
               return sum([a0[k]*log(ev[k])**n for k in xrange(N)])/factorial(n) 

        self.sexp_coeffs_1 = _SexpCoeffs1(RP,min_index=1)
        self.slog_coeffs_1 = self.sexp_coeffs_1.inv()

        if self.L != None:
            return self.L
        b = self.b
        iprec = self.iprec

        if b > (e**(1/e)).n(iprec):
            L = ComplexField(iprec)(0.5)
            for n in range(100):
                L = log(L)/log(b)
        else:
            L = RealField(iprec)(0)
            for n in range(100):
                L = b**L
            
        self.L = L
        return self

def _estimated_time(M2, M1, length, p):

    """
    Find the estimated time to extend congruences mod M1 to consistent congruences mod M2.

    INPUT:

    - ``M2`` -- an integer (the new modulus)

    - ``M1`` -- an integer (the old modulus)

    - ``length`` -- a list (the current length of the list of congruences mod ``M1``)

    - ``p`` --  a prime

    OUTPUT:

    - The estimated run time of the "CRT" step to combine consistent congruences.

    EXAMPLES::

        sage: sage.combinat.binary_recurrence_sequences._estimated_time(2**4*3**2*5*7*11*13*17, 2**4*3**2*5*7*11*13, 20, 7)
        106.211159309421

    """

    #The heuristic run time of the CRT step to go from modulus M1 to M2

    #length is the current length of cong

    Q = p * log(M2) #Size of our primes.
    NPrimes = log(M2/M1) / log(Q) #The number of primes

    return (length * (Q/p)**NPrimes).n()

    def cmp_ir(self,z):
        """ 
        returns -1 for left, 0 for in, and 1 for right from initial region
        cut line is on the north ray from pfp.

        Works only for real x0.
        """
        pfp = self.pfp
        x0 = self.x0
        if x0 > 0.5:
            print z,abs(z)
            if real(z) >= real(pfp) and abs(z) < abs(pfp):
                return 0
            if real(z) < real(pfp):
                return -1
            if real(z) > real(pfp):
                return 1
        else:
            if imag(z) > imag(pfp):
                if real(z) > real(pfp):
                    return 1
                if real(z) < real(pfp):
                    return -1
            if real(z) < real(pfp) and real(z) > log(real(pfp)) + log(sqrt(1+tan(imag(z))**2)):
                return 0
            if real(z) > real(pfp):
                return 1
            if real(z) < real(pfp):
                return -1

 def calc_prec():
     if self.prec != None:
         return self.prec
     iv0 = IntuitiveAbel(self.bsym,self.N-1,iprec=self.iprec,x0=self.x0sym)
     self.iv0 = iv0
     self.err = abs(iv0.sexp(0.5) - self.sexp(0.5))
     print "err:", self.err.n(20)
     self.prec = floor(-log(self.err)/log(2.0))

def discrete_curve_2(nb_equipes, max_points=100):
    r"""
    """
    from sage.misc.functional import round
    from sage.functions.log import log
    from sage.rings.integer_ring import ZZ
    f = lambda p:(max_points-1)*(1-log(p)/log(nb_equipes))+1
    L = [ZZ(round(f(p=i))) for i in range(1,nb_equipes+1)]
    return L

 def _height(P, check=True):
     if check:
         assert P.curve() == self._E, "the point P must lie on the curve from which the height function was created"
     Q = n * P
     cQ = denominator(Q[0])
     uQ = self.lift(Q, prec=prec)
     si = self.__padic_sigma_square(uQ, prec=prec)
     nn = self._q.valuation()
     qEu = self._q / p ** nn
     return -(log(si*self._Csquare()/cQ) + log(uQ)**2/log(qEu)) / n**2

    def __init__(self, n, instance='key', m=None):
        """
        Construct LWE instance parameterised by security parameter ``n`` where
        all other parameters are chosen as in [CGW2013]_.

        INPUT:

        - ``n`` - security parameter (integer >= 89)
        - ``instance`` - one of

          - "key" - the LWE-instance that hides the secret key is generated
          - "encrypt" - the LWE-instance that hides the message is generated
            (default: ``key``)

        - ``m`` - number of allowed samples or ``None`` in which case ``m`` is
          chosen as in [CGW2013]_.  (default: ``None``)

        EXAMPLES::

            sage: from sage.crypto.lwe import UniformNoiseLWE
            sage: UniformNoiseLWE(89)
            LWE(89, 154262477, UniformSampler(0, 351), 'noise', 131)

            sage: UniformNoiseLWE(89, instance='encrypt')
            LWE(131, 154262477, UniformSampler(0, 497), 'noise', 181)
        """

        if n<89:
            raise TypeError("Parameter too small")

        n2 = n
        C  = 4/sqrt(2*pi)
        kk = floor((n2-2*log(n2, 2)**2)/5)
        n1 = floor((3*n2-5*kk)/2)
        ke = floor((n1-2*log(n1, 2)**2)/5)
        l  = floor((3*n1-5*ke)/2)-n2
        sk = ceil((C*(n1+n2))**(3/2))
        se = ceil((C*(n1+n2+l))**(3/2))
        q = next_prime(max(ceil((4*sk)**((n1+n2)/n1)), ceil((4*se)**((n1+n2+l)/(n2+l))), ceil(4*(n1+n2)*se*sk+4*se+1)))

        if kk<=0:
            raise TypeError("Parameter too small")

        if instance == 'key':
            D  = UniformSampler(0, sk-1)
            if m is None:
                m = n1
            LWE.__init__(self, n=n2, q=q, D=D, secret_dist='noise', m=m)
        elif instance == 'encrypt':
            D   = UniformSampler(0, se-1)
            if m is None:
                m = n2+l
            LWE.__init__(self, n=n1, q=q, D=D, secret_dist='noise', m=m)
        else:
            raise TypeError("Parameter instance=%s not understood."%(instance))

def bkz_runtime_k_sieve(k, n):
    """
    Runtime estimation given ‘k‘ and assuming sieving is used to realise the SVP oracle.
    For small ‘k‘ we use estimates based on experiments. For ‘k ě 90‘ we use the asymptotics.
    """
    repeat = _sage_const_3 *log(n, _sage_const_2 ) - _sage_const_2 *log(k, _sage_const_2 ) + log(log(n, _sage_const_2 ), _sage_const_2 )
    if k < _sage_const_90 :
        return RR(_sage_const_0p45 *k + _sage_const_12p31 ) + repeat
    else:
        # we simply pick the same additive constant 12.31 as above
        return RR(_sage_const_0p3366 *k + _sage_const_12p31 ) + repeat

    def slog(self,z,n=None):
        slog = self.slog
        b = self.b

        if n == None:
            n = self.N
        if self.cmp_ir(z) == -1:
            return slog(b**z)-1
        if self.cmp_ir(z) == +1:
            return slog(log(z)/log(b))+1
        return self.slog_1t(z)

    def sexp_0(self,t):
        #convergence radius 1
        t = self._in_prec(t)
        sexp = self.sexp_0
        b = self.b

        #development point -1 convergence radius 1
        if real(t)>1:
            return b**(sexp(t-1))
        if real(t)<0:
            #sage bug, log(z,b) does not work for complex z
            return log(sexp(t+1))/log(b)
	return self.sexp_0_raw(t)

    def sexp_1(self,t):
        t = self._in_prec(t)
        sexp = self.sexp_1
        b = self.b
        IM = self.IM
        N = self.N

        #development point 0 convergence radius 2
        if real(t)>1:
            return b**(sexp(t-1))
        if real(t)<0:
            #sage bug, log(z,b) does not work for complex z
            return log(sexp(t+1))/log(b)
	return self.sexp_1_raw(t)

 def log(self,workprec=Infinity):
     from sage.functions.log import log
     from sage.functions.other import floor
     if workprec is Infinity:
         raise ApproximationError("unable to compute log to infinite precision")
     parent = self.parent()
     pow = parent(-1)
     res = parent(0)
     t = parent(1) - self
     iter = workprec + floor(log(workprec)/log(parent._p)) + 1
     for i in range(1,iter):
         pow *= t
         res += pow / parent(i)
         res = res.truncate(workprec)
     return res

def _prec_for_solve_diff_eqn_families(M, p):
    #UPDATE THIS with valuation of K[0]-1 and K[1]
    r"""
        A helper function for determining the (relative) precision of the input
        to solve_diff_eqn required in order obtain an answer with (relative)
        precision ``M``. The parameter ``p`` is the prime and ``k`` is the weight.

        Given input precision `M_\text{in}`, the output has precision

        .. MATH::

            M = M_\text{in} - \lceil\log_p(M_\text{in}) - 3.

    """
    # Do we need the weight?
    # A good guess to begin:
    if M < 1:
        raise ValueError("Desired precision M(=%s) must be at least 1."%(M))
    cp = (p - 2) / (p - 1)
    Min = ZZ(3 + M + ceil(ZZ(M).log(p)))
    # It looks like usually there are no iterations
    # For low M, there can be 1 or 2
    while M > Min*cp - ceil(log((Min * cp),p)) - 3: #THINK ABOUT THIS MORE
        Min += 1
        #print("An iteration in _prec_solve_diff_eqn")
    return Min

    def L_invariant(self, prec=20):
        r"""
        Returns the *mysterious* `\mathcal{L}`-invariant associated
        to an elliptic curve with split multiplicative reduction.

        One
        instance where this constant appears is in the exceptional
        case of the `p`-adic Birch and Swinnerton-Dyer conjecture as
        formulated in [MTT]_. See [Col]_ for a detailed discussion.

        INPUT:

        - ``prec`` - the `p`-adic precision, default is 20.

        REFERENCES:

        [MTT]_

        .. [Col] Pierre Colmez, Invariant `\mathcal{L}` et derivees de
           valeurs propres de Frobenius, preprint, 2004.

        EXAMPLES::

            sage: eq = EllipticCurve('130a1').tate_curve(5)
            sage: eq.L_invariant(prec=10)
            5^3 + 4*5^4 + 2*5^5 + 2*5^6 + 2*5^7 + 3*5^8 + 5^9 + O(5^10)
        """
        if not self.is_split():
            raise RuntimeError("The curve must have split multiplicative "
                               "reduction")
        qE = self.parameter(prec=prec)
        n = qE.valuation()
        u = qE / self._p ** n
        # the p-adic logarithm of Iwasawa normalised by log(p) = 0
        return log(u) / n

def params_str(d, keyword_width=None):
    """
    Return string of key,value pairs as a string "key0: value0, key1: value1"
    :param d:  report dictionary
    :keyword_width:keys are printed with this width
    """
    if d is None:
        return
    s = []
    for k in d:
        v = d[k]
        if keyword_width:
            fmt = u"%%%ds" % keyword_width
            k = fmt % k
        if ZZ(_sage_const_1 )/_sage_const_2048  < v < _sage_const_2048  or v == _sage_const_0 :
            try:
                s.append(u"%s: %9d" % (k, ZZ(v)))
            except TypeError:
                if v < _sage_const_2p0  and v >= _sage_const_0p0 :
                    s.append(u"%s: %9.7f" % (k, v))
                else:
                    s.append(u"%s: %9.4f" % (k, v))
        else:
            t = u"«2^%.1f" % log(v, _sage_const_2 ).n()
            s.append(u"%s: %9s" % (k, t))
    return u", ".join(s)

    def calc_prec(self):
        if self.prec != None:
            return self.prec

        mp0 = MatrixPowerSexp(self.bsym,self.N-1,iprec=self.iprec,x0=self.x0sym)

        sexp_precision=RR(1)*log(abs(self.sexp_1(0.5)-mp0.sexp_1(0.5)),2.0)
        self.prec = (-sexp_precision).floor()
        print "sexp precision: " , self.prec

        cprec = self.prec+ceil(log(self.N)/log(2.0))

        #self.eigenvalues = [ ev.n(cprec) for ev in self.eigenvalues ]
        #self.IM = self.IM.n(cprec)
        #self.b = self.bsym.n(cprec)
        return self

    def Dini(a=1, b=1, name="Dini's surface"):
        r"""
        Returns Dini's surface, with parametrization

        .. MATH::

            \begin{aligned}
              x(u, v) & = a \cos(u)\sin(v); \\
              y(u, v) & = a \sin(u)\sin(v); \\
              z(u, v) & = u + \log(\tan(v/2)) + \cos(v).
            \end{aligned}

        INPUT:

        - ``a, b`` -- surface parameters.

        - ``name`` -- string. Name of the surface.

        EXAMPLES::

            sage: dini = surfaces.Dini(a=3, b=4); dini
            Parametrized surface ('Dini's surface') with equation (3*cos(u)*sin(v), 3*sin(u)*sin(v), 4*u + 3*cos(v) + 3*log(tan(1/2*v)))
            sage: dini.plot()  # not tested -- known bug (see #10132)

        """

        u, v = var("u, v")
        dini_eq = [a * cos(u) * sin(v), a * sin(u) * sin(v), a * (cos(v) + log(tan(v / 2))) + b * u]
        coords = ((u, 0, 2 * pi), (v, 0, 2 * pi))

        return ParametrizedSurface3D(dini_eq, coords, name)

    def super(self,x):
        """
        Development point is x0-1
        """
        if isinstance(x,float) and self.iprec != None:
           x = RealField(self.iprec)(x)
            
        super = self.super
        super_raw = self.super_raw
        b = self.b
        c = self.c

        xt = x - c
        if real(xt)<-0.5:
            return log(super(x+1))/log(b)
        if real(xt)>0.5:
            return b**(super(x-1))
        return super_raw(x)

 def calc_prec(self):
     if self.prec != None:
         return self.prec
     iv0 = IntuitiveTetration(self.bsym,self.N-1,iprec=self.iprec,x0=self.x0sym)
     self.iv0 = iv0
     d = lambda x: self.slog(x) - iv0.slog(x)
     maximum = find_maximum_on_interval(d,0,1,maxfun=20)
     minimum = find_minimum_on_interval(d,0,1,maxfun=20)
     print "max:", maximum[0].n(20), 'at:', maximum[1]
     print "min:", minimum[0].n(20), 'at:', minimum[1]
     self.err = max( abs(maximum[0]), abs(minimum[0]))
     print "slog err:", self.err.n(20)
     self.prec = floor(-self.err.log(2))
     
     self.sexp_err = abs(iv0.sexp(0.5) - self.sexp(0.5))
     print "sexp err:", self.sexp_err.n(20)
     self.sexp_prec = floor(-log(self.sexp_err)/log(2.0))
     return self