Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-15T13:40:27.237Z Has data issue: false hasContentIssue false

Identifying supersingular elliptic curves

Published online by Cambridge University Press:  01 September 2012

Andrew V. Sutherland*
Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Avenue, MA 02139, Cambridge, USA (email: drew@math.mit.edu)

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © London Mathematical Society 2012