Skip to Main content Skip to Navigation
Journal articles

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

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 : Thursday, March 5, 2020 - 6:33:31 PM

Files

qcsea.pdf
Files produced by the author(s)

Licence


Copyright

Identifiers

Collections

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

509

Files downloads

257