On counting and generating curves over small finite fields (Q1827569)

It is well known that elliptic and other curve-based cryptosystems require the construction of curves over finite fields having points of large prime order on the Jacobians of the curves. In this paper the authors look for curves defined over a finite field \(\mathbb{F}_q\) having such points of large prime order when considered over an extension \(\mathbb{F}_{q^r}\). In the elliptic case, they prove that, under some number-theoretic conjectures, if \(\sqrt{(q)}>(r\log q)^{(2+\varepsilon)}\), then there are at least \(\Omega(q/r^{(1+\varepsilon)}\log q)\) non-isomorphic elliptic curves \(E\) over \(\mathbb{F}_q\) such that the quotient \(E(\mathbb{F}_q)/E(\mathbb{F}_{q^r})\) has prime order. Based on this result, they also present an algorithm that, given an integer \(n\), determines \(q\), \(r\) and \(\Omega(\log^3 n)\) pairs \((E,P)\), of non-isomorphic elliptic curves together with a point with large prime order on each curve. Thus, this method can be useful generating curves of cryptographic interest. The method seems to be extended to any hyperelliptic curve. The extension to the genus 2 case is also treated in the paper.