An extension of Satoh's algorithm and its implementation
By M. Fouquet, P. Gaudry, R. Harley. 2000
70 citations recorded by the source corpus.
We describe a fast algorithm for counting points on elliptic curves defined over finite fields of small characteristic, following Satoh. Our main contribution is an extension to characteristics two and three. We give a detailed description with the optimisations necessary for an efficient implementation. Finally we give the number of points we have computed on a ``random'' curve defined over the field Fq with q=2^8009.
View Paper: https://www.semanticscholar.org/paper/b43ac622ea951127c6b785e92f643c362bbb6abb
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Darrel Hankerson
- Scott A. Vanstone
- Alfred J. Menezes
- Antoine Joux
- Dan Boneh
- Kiran S. Kedlaya
- Florian Hess
- Hugo Krawczyk
Citations in the corpus
- Counting Points on Hyperelliptic Curves using Monsky-Washnitzer Cohomology (2001, methodology): “For fields of fixed (or at least small) characteristic, an algorithm given by Satoh [9] has smaller asymptotic running time than Schoof’s algorithm; an implementation is described in detail in [3].”
- A One Round Protocol for Tripartite Diffie–Hellman (2000, methodology): “Since their invention, these p-adic methods have been implemented by many people, e.g., see [ 11 ], [20], [15] and [25].”
- Guide to Elliptic Curve Cryptography (2004, methodology): “It was extended to elliptic curves over binary fields by Fouquet, Gaudry and Harley [146] and Skjernaa [436].”