Remote Access Mathematics of Computation
Green Open Access

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

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

American Mathematical Society