Identifying supersingular elliptic curves

Abstract

Given an elliptic curve E over a field of positive characteristic p, we consider how to efficiently determine whether E is ordinary or supersingular. We analyze the complexity of several existing algorithms and then present a new approach that exploits structural differences between ordinary and supersingular isogeny graphs. This yields a simple algorithm that, given E and a suitable non-residue in F_p^2, determines the supersingularity of E in O(n^3 log^2 n) time and O(n) space, where n=O(log p). Both these complexity bounds are significant improvements over existing methods, as we demonstrate with some practical computations.

corrected a typo, 10 pages

References in corpus (2)

• Computing Hilbert class polynomials with the Chinese Remainder Theorem
• Structure computation and discrete logarithms in finite abelian p-groups

Cited by in corpus (8)

• Isogeny volcanoes
• $\ell$-adic images of Galois for elliptic curves over $\mathbb{Q}$
• On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average
• On the evaluation of modular polynomials
• On the Distribution of Atkin and Elkies Primes
• Higher-degree supersingular group actions
• Computing cardinalities of Q-curve reductions over finite fields
• Computing the endomorphism ring of an elliptic curve over a number field