Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-24T00:16:57.898Z Has data issue: false hasContentIssue false
  • English
  • Français

Identifying supersingular elliptic curves

Part of: Arithmetic algebraic geometry Computational number theory Curves

Published online by Cambridge University Press:  01 September 2012

Andrew V. Sutherland
Andrew V. Sutherland*
Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Avenue, MA 02139, Cambridge, USA (email: [email protected])

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.

MSC classification

Secondary: 11G07: Elliptic curves over local fields 11Y16: Algorithms; complexity 11G20: Curves over finite and local fields 14H52: Elliptic curves
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 15 , May 2012 , pp. 317 - 325
Copyright
Copyright © London Mathematical Society 2012

References

[1]Adleman, L. M., Manders, K. and Miller, G. L., ‘On taking roots in finite fields’, 18th Annual Symposium on Foundations of Computer Science (IEEE, 1977) 175–178.Google Scholar
[2]Bosma, W., Cannon, J. J., Fieker, C. and Steel, A. (eds), Handbook of Magma functions, 2.17 edn 2011 http://magma.maths.usyd.edu.au/magma/handbook/.Google Scholar
[3]Bröker, R., ‘Constructing supersingular elliptic curves’, J. Comb. Number Theory 1 (2009) no. 3, 269–273.Google Scholar
[4]Elkies, N. D., ‘Elliptic and modular curves over finite fields and related computational issues’, Comput. Perspect. Number Theory, Studies in Advanced Mathematics 7 (eds Buell, D. A. and Teitelbaum, J. T.; American Mathematical Society, 1998) 21–76.Google Scholar
[5]Fouquet, M. and Morain, F., ‘Isogeny volcanoes and the SEA algorithm’, Algorithmic Number Theory Symposium–ANTS V, Lecture Notes in Computer Science 2369 (eds Fieker, C. and Kohel, D. R.; Springer, 2002) 276–291.CrossRefGoogle Scholar
[6]T. Granlund and the GMP development team, ‘GNU Multiple Precision Arithmetic Library’, September 2010, version 5.0.1, available at http://gmplib.org/.Google Scholar
[7]Husemöller, D., Elliptic curves (Springer, 1987).CrossRefGoogle Scholar
[8]Kohel, D., ‘Endomorphism rings of elliptic curves over finite fields’, PhD Thesis, University of California at Berkeley, 1996.Google Scholar
[9]Lang, S., Elliptic functions, second ed. (Springer, 1987).CrossRefGoogle Scholar
[10]Menezes, A., Okamoto, T. and Vanstone, S. A., ‘Reducing elliptic curve logarithms in a finite field’, IEEE Trans. Inform. Theory 39 (1993) 1639–1646.CrossRefGoogle Scholar
[11]Miller, G. L., ‘Riemann’s hypothesis and tests for primality’, J. Comput. System Sci. 13 (1976) 300–317.CrossRefGoogle Scholar
[12]Pizer, A. K., ‘Ramanujan graphs and Hecke operators’, Bull. Amer. Math. Soc. 23 (1990) no. 1, 127–137.CrossRefGoogle Scholar
[13]Rück, H.-G., ‘A note on elliptic curves over finite fields’, Math. Comp. 49 (1987) 301–304.CrossRefGoogle Scholar
[14]Schönhage, A. and Strassen, V., ‘Schnelle Multiplikation großer Zahlen’, Computing 7 (1971) 281–292.CrossRefGoogle Scholar
[15]Schoof, R., ‘Elliptic curves over finite fields and the computation of square roots mod p’, Math. Comp. 44 (1985) 483–294.Google Scholar
[16]Schoof, R., ‘Counting points on elliptic curves over finite fields’, J. Théor. Nombres Bordeaux 7 (1995) 219–254.CrossRefGoogle Scholar
[17]Schoof, R., ‘Families of curves and weight distributions of codes’, Bull. Amer. Math. Soc. 32 (1995) no. 2, 171–183.CrossRefGoogle Scholar
[18]Shanks, D., ‘Five number-theoretic algorithms’, Proceedings of the 2nd Manitoba Conference on Numerical Mathematics, Congressus Numerantium VII (Utilitas Mathematica, 1973) 51–70.Google Scholar
[19]Silverman, J. H., The arithmetic of elliptic curves (Springer, 1986).CrossRefGoogle Scholar
[20]Stein, W. A.et al., ‘Sage mathematics software (version 4.6.2)’, The Sage development team, 2011, http://www.sagemath.org.Google Scholar
[21]Sutherland, A. V., ‘Computing Hilbert class polynomials with the Chinese remainder theorem’, Math. Comp. 80 (2011) 501–538.CrossRefGoogle Scholar
[22]Sutherland, A. V., ‘Structure computation and discrete logarithms in finite abelian p-groups’, Math. Comp. 80 (2011) 477–500.CrossRefGoogle Scholar
[23]Tonelli, A., ‘Bemerkung über die Auflösung quadratischer Congruenzen’, Göttinger Nachrichten (1891) 344–346.Google Scholar
[24]von zur Gathen, J. and Gerhard, J., Modern computer algebra, 2nd edn (Cambridge University Press, 2003).Google Scholar