説明
<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>
収録刊行物
-
- LMS Journal of Computation and Mathematics
-
LMS Journal of Computation and Mathematics 15 317-325, 2012-09-01
Wiley