Skip to Main content Skip to Navigation
Conference papers

A comparison and a combination of SST and AGM algorithms for counting points of elliptic curves in characteristic 2

Abstract : Since the first use of a p-adic method for counting points of elliptic curves, by Satoh in 1999, several variants of his algorithm have been proposed. In the current state, the AGM algorithm, proposed by Mestre is thought to be the fastest in practice, and the algorithm by Satoh­-Skjernaa­-Taguchi has the best asymptotic complexity but requires precomputations. We present an amelioration of the SST algorithm, borrowing ideas from the AGM. We make a precise comparison between this modified SST algorithm and the AGM, thus demonstrating that the former is faster by a significant factor, even for small cryptographic sizes.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00514137
Contributor : Pierrick Gaudry <>
Submitted on : Wednesday, September 1, 2010 - 1:22:03 PM
Last modification on : Thursday, March 5, 2020 - 6:21:50 PM
Long-term archiving on: : Thursday, December 2, 2010 - 2:45:13 AM

File

sstagm.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Pierrick Gaudry. A comparison and a combination of SST and AGM algorithms for counting points of elliptic curves in characteristic 2. Asiacrypt, 2002, Queenstown, New Zealand. pp.621-628, ⟨10.1007/3-540-36178-2_20⟩. ⟨inria-00514137⟩

Share

Metrics

Record views

313

Files downloads

345