Skip to Main content Skip to Navigation
New interface
Conference papers

Finding secure curves with the Satoh-FGH algorithm and an early-abort strategy

Abstract : The use of elliptic curves in cryptography relies on the ability to count the number of points on a given curve. Before 1999, the SEA algorithm was the only efficient method known for random curves. Then Satoh proposed a new algorithm based on the canonical p-adic lift of the curve for p>=5. In an earlier paper, the authors extended Satoh's method to the case of characteristics two and three. This paper presents an implementation of the Satoh-FGH algorithm and its application to the problem of finding curves suitable for cryptography. By combining Satoh-FGH and an early-abort strategy based on SEA, we are able to find secure random curves in characteristic two in much less time than previously reported. In particular we can generate curves widely considered to be as secure as RSA-1024 in less than one minute each on a fast workstation.
Document type :
Conference papers
Complete list of metadata
Contributor : Pierrick Gaudry Connect in order to contact the contributor
Submitted on : Thursday, September 2, 2010 - 1:19:22 PM
Last modification on : Thursday, February 3, 2022 - 11:13:51 AM
Long-term archiving on: : Friday, December 3, 2010 - 2:37:03 AM


Files produced by the author(s)




Mireille Fouquet, Pierrick Gaudry, Robert Harley. Finding secure curves with the Satoh-FGH algorithm and an early-abort strategy. Eurocrypt, 2001, Innsbruck, Austria. pp.14-29, ⟨10.1007/3-540-44987-6_2⟩. ⟨inria-00514426⟩



Record views


Files downloads