**Constructing pairing-friendly genus 2 curves over prime fields with ordinary Jacobians**

*David Freeman*

**Abstract: **We provide the first explicit construction of genus 2 curves over finite fields whose Jacobians are ordinary, have large prime-order subgroups, and have small embedding degree. Our algorithm works for arbitrary embedding degrees $k$ and prime subgroup orders $r$. The resulting abelian surfaces are defined over prime fields $\F_q$ with $q \approx r^4$. We also provide an algorithm for constructing genus 2 curves over prime fields $\F_q$ with ordinary Jacobians $J$ having the property that $J[r] \subset J(\F_{q})$ or $J[r] \subset J(\F_{q^k})$ for any even $k$.

**Category / Keywords: **public-key cryptography / pairing-friendly curves, embedding degree, genus 2 curves, hyperelliptic curves, CM method, complex multiplication

**Date: **received 16 Feb 2007

**Contact author: **dfreeman at math berkeley edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20070220:101614 (All versions of this report)

**Short URL: **ia.cr/2007/057

[ Cryptology ePrint archive ]