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 𝔽p2, determines the supersingularity of E in O(n3log 2n) 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.