A. Sutherland. (2011)cite arxiv:1107.1140Comment: minor edits, 10 pages, to appear in the LMS Journal of Computation and Mathematics.
DOI: 10.1112/S1461157012001106
Zusammenfassung
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.
%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
}