Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T18:04:49.664Z Has data issue: false hasContentIssue false
  • English
  • Français

Constructing Isogenies between Elliptic Curves Over Finite Fields

Published online by Cambridge University Press:  01 February 2010

Steven D. Galbraith
Steven D. Galbraith
Affiliation:
Mathematics Department, Royal Holloway University of London, Egham, Surrey TW20 0EX

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.

Let E1 and E2 be ordinary elliptic curves over a finite field Fp such that #E1(Fp) = #E2(Fp). Tate's isogeny theorem states that there is an isogeny from E1 to E2 which is defined over Fp. The goal of this paper is to describe a probabilistic algorithm for constructing such an isogeny.

The algorithm proposed in this paper has exponential complexity in the worst case. Nevertheless, it is efficient in certain situations (that is, when the class number of the endomorphism ring is small). The significance of these results to elliptic curve cryptography is discussed.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 2 , 1999 , pp. 118 - 138
Copyright
Copyright © London Mathematical Society 1999

References

1.Atkin, A. O. L., ‘The number of points on an elliptic curve modulo a prime’, Preprint, 1988.Google Scholar
2.Atkin, A. O. L., ‘The number of points on an elliptic curve modulo a prime ’ Preprint, 1992.Google Scholar
3.Atkin, A. O. L. and Morain, F., ‘Finding suitable curves for the elliptic curve method of factorization’, Math. Comp. 60 (1993) 399–405.CrossRefGoogle Scholar
4.Bach, E., Analytic methods in the analysis and design of number-theoretic algorithms, Berkeley Doctoral Thesis, ACM Distinguished Dissertations (MIT Press, 1984)Google Scholar
5.Blake, I., Seroussi, G. and Smart, N. P., Elliptic curves in cryptography, LMS Lecture Notes 265 (Cambridge University Press, 1999).CrossRefGoogle Scholar
6.Cassels, J. W. S., Lectures on elliptic curves, LMS Student Texts 24 (Cambridge University Press, 1991)CrossRefGoogle Scholar
7.Cohen, H., A course in computational algebraic number theory, Grad. Texts in Math. 138 (Springer, New York, 1993).CrossRefGoogle Scholar
8.Couveignes, J.-M., ‘Computing l-isogenies using the p-torsion’, ANTS-II, Lecture Notes in Comput. Sci. 1122 (ed.Cohen, H., Springer, New York, 1996) 59–65.Google Scholar
9.Couveignes, J.-M. and Morain, F., ‘Schoof's algorithm and isogeny cycles’, ANTS-I, Lecture Notes in Comput. Sci. 877 (ed. Adleman, L. M., Springer, New York, 1994) 43–58.Google Scholar
10.Elkies, N., ‘Explicit isogenies’, Preprint, 1991.CrossRefGoogle Scholar
11.Elkies, N., ‘Elliptic and modular curves over finite fields and related computational issues’, Computational perspectives on number theory: proceedings of a conference in honor of A.O.L. Atkin (ed. Buell, D. A. and Teitelbaum, J. T., AMS, 1997) 21–76.CrossRefGoogle Scholar
12.Frey, G. and Rück, H.-G., ‘A remark concerning TO-divisibility and the discrete logarithm problem in the divisor class group of curves’, Math. Comp. 62 (1994) 865–874.Google Scholar
13.Galbraith, S. D. and McKee, J., ‘The probability that the number of points on an elliptic curve over a finite field is prime’, Preprint, 1999.Google Scholar
14.Kohel, D., ‘Endomorphism rings of elliptic curves over finite fields’, Berkeley PhD thesis, 1996.Google Scholar
15.Lang, S., Elliptic functions, 2nd edn, Grad. Texts in Math. 112 (Springer, New York, 1987).CrossRefGoogle Scholar
16.Lay, G.-J. and Zimmer, H. G., ‘Constructing elliptic curves with given group order over large finite fields’, ANTS-I, Lecture Notes in Comput. Sci. 877 (ed. Adleman, L. M., Springer, New York, 1994) 250–263.Google Scholar
17.Lenstra, H.W. JR., ‘Finding isomorphisms between finite fields’, Math. Comp. 56 (1991)329–347.CrossRefGoogle Scholar
18.Lenstra, H.W. JR., ‘Complex multiplication structure of elliptic curves’, J. Number Theory 56 (1996) 227–241.CrossRefGoogle Scholar
19.Lercier, R., ‘Computing isogenies in F2n‘ANTS-II’, ,Lecture Notes in Comput. Sci. 1122 (ed. Cohen, H., Springer, New York, 1996) 197–212.Google Scholar
20.Lercier, R. and Morain, F., ‘Algorithms for computing isogenies between elliptic curves’, Computational perspectives on number theory: proceedings of a conference in honor of A. O. L. Atkin (ed. Buell, D. A. and Teitelbaum, J. T., AMS, 1997) 77–96.CrossRefGoogle Scholar
21.Mestre, J.-F., ‘La methode des graphes. Exemples et applications’, Class numbers and fundamental units of algebraic number fields, Proc. Int. Conf., Katata, Japan (Nagoya University, 1986) 217–242.Google Scholar
22.Menezes, A., Okamoto, T. and Vanstone, S., ‘Reducing elliptic curve discrete log arithms to logarithms in a finite field’, IEEE Trans. Inform. Theory 39 (1993) 1639–1646.CrossRefGoogle Scholar
23.Moraiin, F., ‘Building cyclic elliptic curves modulo large primes’, ‘EUROCRYPT’91, Lecture Notes in Comput. Sci. 549 (Springer, New York, 1991) 328–336.Google Scholar
24.Mueller, V., ‘Ein algorithmus zur bestimmung der punktzahl elliptischer kurven über endlichen körpen der charakteristik grösser drei’, PhD. Thesis, Universität des Saarlandes, 1995.Google Scholar
25.Pollard, J., ‘Monte Carlo methods for index computation (mod p)’, Math. Comp. 32 (1978) 918–924.Google Scholar
26.Rück, H.-G., ‘On the discrete logarithm problem in the divisor class group of curves’, Math. Comp., to appear.Google Scholar
27.Satoh, T. and Araki, K., ‘Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves’, Comment. Math. Univ. St. Paul, 9l (1998) 81–92.Google Scholar
28.Schoof, R., ‘Elliptic curves over finite fields and the computation of square roots mod p’, Math. Comp. 44 (1985) 483–94.Google Scholar
29.Schoof, R., ‘Counting points on elliptic curves over finite fields’, J. Theor. Nombres Bordeaux 7 (1995) 219–254.CrossRefGoogle Scholar
30.Semaev, I., ‘Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p’ Math. Comp. 61 (1998) 353–356.CrossRefGoogle Scholar
31.Shimura, G., Introduction to the arithmetic theory of automorphic functions (Iwanami/Princeton, 1971).Google Scholar
32.Silverman, J. H., The arithmetic of elliptic curves, Grad. Texts in Math. 106 (Springer, New York, 1986).Google Scholar
33.Smart, N. P., ‘The discrete logarithm problem on elliptic curves of trace one’, J. Cryptology, to appear.Google Scholar
34.Tate, J., ‘Endomorphisms of abelian varieties over finite fields’, Invent. Math. 2 (1966) 134–144.CrossRefGoogle Scholar
35.Vélu, J., ‘Isogénies entre courbes elliptiques’, C. R. Acad. Sci. Paris Sér. I, 273 (1971) 238–241.Google Scholar