Identifying supersingular elliptic curves

DOI Web Site 4 Citations

Description

<jats:title>Abstract</jats:title><jats:p>Given an elliptic curve <jats:italic>E</jats:italic> over a field of positive characteristic <jats:italic>p</jats:italic>, we consider how to efficiently determine whether <jats:italic>E</jats:italic> 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 <jats:italic>E</jats:italic> and a suitable non-residue in 𝔽<jats:sub><jats:italic>p</jats:italic><jats:sup>2</jats:sup></jats:sub>, determines the supersingularity of <jats:italic>E</jats:italic> in <jats:italic>O</jats:italic>(<jats:italic>n</jats:italic><jats:sup>3</jats:sup>log <jats:sup>2</jats:sup><jats:italic>n</jats:italic>) time and <jats:italic>O</jats:italic>(<jats:italic>n</jats:italic>) space, where <jats:italic>n</jats:italic>=<jats:italic>O</jats:italic>(log <jats:italic>p</jats:italic>) . Both these complexity bounds are significant improvements over existing methods, as we demonstrate with some practical computations.</jats:p>

Journal

Citations (4)*help

See more

Report a problem

Back to top