**Abelian varieties with prescribed embedding degree**

*David Freeman and Peter Stevenhagen and Marco Streng*

**Abstract: **We present an algorithm that, on input of a CM-field $K$, an integer $k \ge 1$, and a prime $r \equiv 1 \bmod k$, constructs a $q$-Weil number $\pi \in \O_K$ corresponding to
an ordinary, simple abelian variety $A$ over the field $\F$ of $q$ elements that has an $\F$-rational point of order $r$ and embedding degree $k$ with respect to $r$. We then discuss how CM-methods over $K$ can be used to explicitly construct $A$.

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

**Date: **received 3 Feb 2008

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

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

**Version: **20080211:105601 (All versions of this report)

**Short URL: **ia.cr/2008/061

[ Cryptology ePrint archive ]