On finite fields for pairing based cryptography (Q2470809)

From the text: ``Here, we improve our previous bound [J. Cryptology 19, No. 4, 553--562 (2006; Zbl 1133.14303)] on the number of finite fields over which elliptic curves of cryptographic interest with a given embedding degree and small complex multiplication discriminant may exist. We also give some heuristic arguments which lead to a lower bound which in some cases is close to our upper bound.'' Denote by \(Q_k(x,y,z)\) the number of prime powers \(q\leq x\) for which there exist a prime \(\ell\geq y\) and an integer \(t\) satisfying (1) \(| t|\leq 2q^{1/2},\;t\neq 0,1,2, \;\ell\mid q+1-t\), and \(\ell\mid\Phi_k\), where \(\Phi_k\) denotes the \(k\)th cyclotomic polynomial, and (2) \(t^2-4q=-r^2s\), with square-free positive integers \(s\leq z\). In the paper cited above it was shown that for any fixed integer \(k\geq 2\) and positive real numbers \(x, y, z\) the bound \[ Q_k(x,y,z)\leq x^{3/2+o(1)}y^{-1}z \] holds as \(x\to\infty\). In this paper it is proved that the following bound holds \[ Q_k(x,y,z)\ll \varphi(k) x^{3/2} y^{-1} z^{1/2}\frac{\log x}{\log\log x} \] provided that \(x\) is large enough.