cm_method.sage

def cm_method(q,t):
    """
    Given a prime power q and integer t with |t| <= 2sqrt(q),
    returns an Elliptic curve over GF(q) with q + 1 - t points.
    """
    n = q + 1 - t
    d = t^2 - 4*q
    K = QuadraticField(d)
    j = K.hilbert_class_polynomial().any_root()
    E = EllipticCurve_from_j(GF(q)(j))
    while E.count_points() != n:
        if d == -3:
            E = E.sextic_twist(randint(1,q-1))
        elif d == -4:
            E = E.quartic_twist(randint(1,q-1))
        else:
            E = E.quadratic_twist()
    return E