# from the paper "Pairing Friendly Elliptic Curves of Prime Order"
#  input: the approximate desired bit length m of the curve
# output: p,n,b,y such that y^2 = x^3 + b has order n over F_p and G=(1,y) is a generator 
def search_embed_12(m):
    # let P(x) = 36x^4 + 36x^3 + 24x^2 + 6x + 1
    # find smallest x =~ 2^(m/4) such that ceil(log_2(P(-x))) = m
    # binary search for this! 
    limit_low = floor(2^((m/4) - 2))
    x = floor(2^(m/4))
    limit_high = ceil(2^((m/4) + 2))
    print "starting x at 2^(%d/4) = %d (aiming for %d) (x in [%d,%d]" % (m,x,m,limit_low,limit_high)
    while 1:
        a = ceil(log(36*(x-1)^4 - 36*(x-1)^3 + 24*(x-1)^2 - 6*(x-1) + 1, 2))
        b = ceil(log(36*x^4 - 36*x^3 + 24*x^2 - 6*x + 1, 2))

        if (a == m-1) and (b == m):
            break

        if b >= m:
            limit_high = x-1
            x = limit_low + floor((limit_high - limit_low)/2)
        else:
            limit_low = x+1
            x = limit_low + ceil((limit_high - limit_low)/2)
            
        print "currently x=%d in [%d,%d] result=%d" % (x,limit_low, limit_high, b)
        #print "currentl x=%d\n" % x
    print "ceil(log_2(P(-(%d-1))) = %d (substituted x=%d)" % (x,a,x)
    print "ceil(log_2(P(-(%d)))) = %d (substituted x=%d)" % (x,b,x)

    while 1:
        t = 6*x^2 + 1
        p = 36*x^4 - 36*x^3 + 24*x^2 - 6*x + 1
        n = p + 1 - t
        if is_prime(p) and is_prime(n):
            break
        p = 36*x^4 + 36*x^3 + 24*x^2 + 6*x + 1
        n = p + 1 - t
        if is_prime(p) and is_prime(n):
            break
        x = x + 1

    b = 0
    while 1:
        while 1:
            b = b + 1
            if kronecker(b+1, p)==1:
                break;

        y = mod(b+1, p).sqrt()
        print "calculated b = %d such that %d^2 = b+1 (mod %d)" % (b, y, p)

        E = EllipticCurve(GF(p),[0,0,0,0,b])
        G = E([1,y,1])

        if n*G == E([0,1,0]):
            break;

    print "E: ", E
    print "G: ", G
    print "should have %d points" % n
   
    return [E,G]