Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

   

 

A generic approach to searching for Jacobians


Author: Andrew V. Sutherland
Journal: Math. Comp. 78 (2009), 485-507
MSC (2000): Primary 11G20, 11Y16; Secondary 11M38, 14G50
Published electronically: May 20, 2008
MathSciNet review: 2448717
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We consider the problem of finding cryptographically suitable Jacobians. By applying a probabilistic generic algorithm to compute the zeta functions of low genus curves drawn from an arbitrary family, we can search for Jacobians containing a large subgroup of prime order. For a suitable distribution of curves, the complexity is subexponential in genus 2, and $ O(N^{1/12})$ in genus 3. We give examples of genus 2 and genus 3 hyperelliptic curves over prime fields with group orders over $ 180$ bits in size, improving previous results. Our approach is particularly effective over low-degree extension fields, where in genus 2 we find Jacobians over $ \mathbb{F}_{p^2}$ and trace zero varieties over $ \mathbb{F}_{p^3}$ with near-prime orders up to 372 bits in size. For $ p = 2^{61}-1$, the average time to find a group with 244-bit near-prime order is under an hour on a PC.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11G20, 11Y16, 11M38, 14G50

Retrieve articles in all journals with MSC (2000): 11G20, 11Y16, 11M38, 14G50


Additional Information

Andrew V. Sutherland
Affiliation: Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139-4307
Email: drew@math.mit.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-08-02143-1
PII: S 0025-5718(08)02143-1
Received by editor(s): August 15, 2007
Received by editor(s) in revised form: January 29, 2008
Published electronically: May 20, 2008
Article copyright: © Copyright 2008 by the author