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.
Type de document :
Article dans une revue
LMS Journal of Computation and Mathematics, London Mathematical Society, 2016, 19 (A), pp.15. <10.1112/S1461157016000267>
Liste complète des métadonnées


https://hal.inria.fr/hal-01320388
Contributeur : Benjamin Smith <>
Soumis le : vendredi 17 juin 2016 - 10:52:07
Dernière modification le : samedi 18 février 2017 - 01:13:08

Fichiers

qcsea.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

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>

Partager

Métriques

Consultations de
la notice

246

Téléchargements du document

80