%0 Generic %1 sutherland2011identifying %A Sutherland, Andrew V. %D 2011 %K curves elliptic identifying supersingular %R 10.1112/S1461157012001106 %T Identifying supersingular elliptic curves %U http://arxiv.org/abs/1107.1140 %X 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.

@misc{sutherland2011identifying, 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.}, added-at = {2013-12-23T07:33:05.000+0100}, author = {Sutherland, Andrew V.}, biburl = {https://www.bibsonomy.org/bibtex/2ed88a14294e5e9bcea3cf2df375ac861/aeu_research}, description = {Identifying supersingular elliptic curves}, doi = {10.1112/S1461157012001106}, interhash = {326ac7a061688ac2555a391619418282}, intrahash = {ed88a14294e5e9bcea3cf2df375ac861}, keywords = {curves elliptic identifying supersingular}, note = {cite arxiv:1107.1140Comment: minor edits, 10 pages, to appear in the LMS Journal of Computation and Mathematics}, timestamp = {2013-12-23T08:22:34.000+0100}, title = {Identifying supersingular elliptic curves}, url = {http://arxiv.org/abs/1107.1140}, year = 2011 }