curves_for_kirby.py

def find_Hilbert_roots(upper):
    """
    Examples of D s.t. D%4 == 0
    and the corresponding roots of 
    the Hilbert Class Polynomial

    D=4, root=2^6 * 3^3
    D=8, root=2^6 * 5^3
    D=12, root=0
    D=16, root=2^6 * 3^3
    D=28, root=-1 * 3^3 * 5^3
    D=32, root=2^6 * 5^3
    D=36, root=2^6 * 3^3
    D=44, root=-1 * 2^15
    D=48, root=0
    D=64, root=2^6 * 3^3
    D=72, root=2^6 * 5^3
    D=76, root=-1 * 2^15 * 3^3
    """
    for D in range(4,upper,4):
        K.<a> = QuadraticField(-D)
        Pd = hilbert_class_polynomial(K.discriminant())
        rs = Pd.roots()
        if rs:
            r = rs[0][0]
            if r:
                print(f'D={D}, root={factor(rs[0][0])}')
            else:
                print(f'D={D}, root={rs[0][0]}')

def special_prime(m, D):
    """
    #E = p + 1 - t
    t = ±x

    Need prime p s.t.
    4p = x^2 + Dy^2
    4p = 2^2 + Dy^2

    Pick y even to ensure p prime
    4p = 4 + D (2m)^2
    4p = 4 + 4Dm^2 
    p = 1 + Dm^2
    """
    assert D % 4 == 0
    while True:
        p = 1 + D*m^2
        if is_prime(p):
            return p
        m += 1

def special_curve(D, j_D):
    """
    Construct elliptic curve with j=j_D using 
    prime p s.t.

    4p = 4 + Dy^2

    for some integer y 
    """
    m = 2**32 # starting value for ~bit size of p
    p = special_prime(m, D)
    E = EllipticCurve(GF(p), j=j_D)
    assert E.order() == (p-1)

    return E, p

D = 76
j_D = -1 * 2^15 * 3^3
E, p = special_curve(D, j_D)