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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-01320388
Contributor : Benjamin Smith <>
Submitted on : Monday, June 6, 2016 - 2:29:50 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:27 PM

Files

qcsea.pdf
Files produced by the author(s)

Identifiers

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

Citation

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

Share

Metrics

Record views

61

Files downloads

12