Mathematics – Number Theory
Scientific paper
2007-08-23
Math. Comp. 78 (2009), 485-507
Mathematics
Number Theory
22 pages, to appear in Mathematics of Computation
Scientific paper
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 F_{p^2) and trace zero varieties over 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.
No associations
LandOfFree
A Generic Approach to Searching for Jacobians does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Generic Approach to Searching for Jacobians, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Generic Approach to Searching for Jacobians will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-521790