# A Memory Efficient Version of Satoh’s Algorithm

• Frederik Vercauteren
• Bart Preneel
• Joos Vandewalle
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)

## Abstract

In this paper we present an algorithm for counting points on elliptic curves over a finite field $$\mathbb{F}_{p^n }$$ of small characteristic, based on Satoh's algorithm. The memory requirement of our algorithm is O(n2), where Satoh's original algorithm needs O(n 3) memory. Furthermore, our version has the same run time complexity of O(n n+ε) bit operations, but is faster by a constant factor. We give a detailed description of the algorithm in characteristic 2 and show that the amount of memory needed for the generation of a secure 200-bit elliptic curve is within the range of current smart card technology.

## Keywords

elliptic curve finite field order counting Satoh’s algorithm

## References

1. 1.
A.O.L. Atkin. The number of points on an elliptic curve modulo a prime. Series of e-mails to the NMBRTHRY mailing list, 1992.Google Scholar
2. 2.
J.M. Couveignes. Quelques calculs en théorie des nombres. PhD thesis, Université de Bordeaux, 1994.Google Scholar
3. 3.
J.M. Couveignes. Computing l-isogenies with the p-torsion. ANTS-II, Lecture Notes in Comp. Sci., 1122:59–65, 1996.Google Scholar
4. 4.
J.A. Csirik. Counting the number of points on an elliptic curve on a low-memory device. 1998. Preprint.Google Scholar
5. 5.
M. Deuring. Die Typen der Multiplikatorenringe elliptischer Funktionenkörper. Abh. Math. Sem. Univ. Hamburg, 14:197–272, 1941.
6. 6.
N. Elkies. Elliptic and modular curves over finite fields and related computational issues. Computational Perspectives on Number Theory, pages 21–76, 1998.Google Scholar
7. 7.
M. Fouquet, P. Gaudry, and R. Harley. On Satoh’s algorithm and its implementation. J. Ramanujan Math. Soc., 15:281–318, 2000.
8. 8.
H. Hasse. Beweis des Analogons der Riemannschen Vermutung für die Artinschen und F. K. Smidtschen Kongruenzzetafunctionen in gewissen elliptischen Fällen. Ges. d. Wiss. Nachrichten. Math.-Phys. Klasse, pages 253–262, 1933.Google Scholar
9. 9.
R. Lercier. Algorithmique des courbes elliptiques dans les corps finis. PhD thesis, L'École Polytechnique, Laboratoire D'Informatique, CNRS, Paris, June 1997.Google Scholar
10. 10.
J. Lubin, J.P. Serre, and J. Tate. Elliptic curves and formal groups. Lecture notes prepared in connection with the seminars held at the Summer Institute on Algebraic Geometry, Whitney Estate, Woods Hole, Massachusetts, 1964.Google Scholar
11. 11.
T. Satoh. The canonical lift of an ordinary elliptic curve over a finite field and its point counting. J. Ramanujan Math. Soc., 15:247–270, 2000.
12. 12.
R. Schoof. Elliptic curves over finite fields and the computation of square roots mod p. Math. Comput., 44:483–494, 1985.
13. 13.
J.P. Serre. Local Fields, volume 67 of Graduate Texts in Mathematics. Springer-Verlag, 1979.Google Scholar
14. 14.
B. Skjernaa. Satoh’s algorithm in characteristic 2. Preprint, 2000.Google Scholar
15. 15.
J. Vélu. Isogénies entre courbes elliptiques. C.R. Acad. Sc. Paris, 273:238–241, 1971.

## Authors and Affiliations

• Frederik Vercauteren
• 1
• Bart Preneel
• 1
• Joos Vandewalle
• 1
1. 1.Dept. Elektrotechniek-ESAT/COSICK.U. LeuvenLeuven-HeverleeBelgium