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 :
Journal articles
Liste complète des métadonnées

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-01320388
Contributor : Benjamin Smith <>
Submitted on : Friday, June 17, 2016 - 10:52:07 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:27 PM

Files

qcsea.pdf
Files produced by the author(s)

Licence


Copyright

Identifiers

Citation

François Morain, Charlotte Scribot, Benjamin Smith. Computing cardinalities of Q-curve reductions over finite fields. LMS Journal of Computation and Mathematics, London Mathematical Society, 2016, 19 (A), pp.15. ⟨10.1112/S1461157016000267⟩. ⟨hal-01320388v3⟩

Share

Metrics

Record views

433

Files downloads

179