Computing cardinalities of Q-curve reductions over finite fields

We present a specialized point-counting algorithm for a class of elliptic curves over F_p2 that includes reductions of quadratic Q-curves modulo inert primes and, more generally, any elliptic curve over F_p2 with a low-degree isogeny to its Galois conjugate curve. These curves have interesting cryptographic applications. Our algorithm is a variant of the Schoof-Elkies-Atkin (SEA) algorithm, but with a new, lower-degree endomorphism in place of Frobenius. While it has the same asymptotic asymptotic complexity as SEA, our algorithm is much faster in practice.