On the elliptic curves \(y^{2}=x^{3} - c\) with embedding degree one (Q555157)

This paper determines when the elliptic curves \(y^2=x^3-c\), defined over a prime field \(F_p\), \(p\equiv 1 \bmod 3\), can have embedding degree \(k=1\) (the embedding degree is the smallest integer \(k\) such that \(n\mid p^k-1\), where \(n\) is the largest prime divisor of \( \sharp E(F_p))\). Curves with small embedding degree are useful in pairing-based cryptography. To find the conditions to have \(k=1\), the paper computes \( \sharp E(F_p)\) (in terms of characters and Jacobi sums) when \(p\equiv 1 \bmod 3\) (if \(p\equiv 2 \bmod 3\), that cardinal is always \(p+1\)). Theorem 1 gives explicit formulas for \( \sharp E(F_p)\) according to the values of \( \chi_2(c)\), \(\chi_3(c)\), \(\chi_6(c)\), where \(\chi_2\), \(\chi_3\), \(\chi_6\) are quadratic, cubic and sextic characters on \(F_p\). As a corollary, the elliptic curve \(y^2=x^3-1\) over \(F_p\), with \(p=27A^2+1\), has embedding degree 1. The conjecture of \textit{P. T. Bateman} and \textit{R. A. Horn} [Math. Comput. 16, 363--367 (1962; Zbl 0105.03302)] shows that there are (conjecturally) infinitely many primes of this form. Table 1 gives, for different cryptographic security levels, the minimum bit length of \(p\) and \(n\) for an efficient and secure implementation. Finally, the paper provides several examples of such values.