Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Computing cardinalities of Q-curve reductions over finite fields

Abstract : We present a specialized point-counting algorithm for a class of elliptic curves over F_{p^2} that includes reductions of quadratic Q-curves modulo inert primes and, more generally, any elliptic curve over F_{p^2} 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.
Complete list of metadatas
Contributor : Benjamin Smith <>
Submitted on : Monday, June 6, 2016 - 2:29:50 PM
Last modification on : Thursday, November 21, 2019 - 6:32:53 PM


Files produced by the author(s)


  • HAL Id : hal-01320388, version 2
  • ARXIV : 1605.07749


François Morain, Charlotte Scribot, Benjamin Smith. Computing cardinalities of Q-curve reductions over finite fields. 2016. ⟨hal-01320388v2⟩



Record views


Files downloads