2016/01/01 by François Morain, Charlotte Scribot, Benjamin Smith
Computer Science · Mathematics · #Algebraic Geometry and Number Theory #Coding theory and cryptography #Cryptography and Residue Arithmetic #Elliptic curve #Endomorphism #Finite field #Isogeny #Modulo #Quadratic equation #Schoof's algorithm #Supersingular elliptic curve #math.NT
paper · pdf · doi:10.1112/s1461157016000267
published as LMS J. Comput. Math. 19 (2016) 115-129 · To appear in the proceedings of ANTS-XII. Added acknowledgement of Drew Sutherland
openalex publication_date 2016/01/01 · arxiv created 2016/06/17 · openalex created_date 2016/06/24 · arxiv updated 2019/02/20 · openalex updated_date 2026/07/28
We present a specialized point-counting algorithm for a class of elliptic curves over \mathbbFp2 that includes reductions of quadratic ℚ -curves modulo inert primes and, more generally, any elliptic curve over \mathbbFp2 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.