Constructing elliptic curves over finite fields using double eta-quotients (Q2483709): Difference between revisions

For several applications (cryptography, factorizing, prime proving) one needs elliptic curves \(E\) over a finite field \(\mathbb F\), where e.g. \(| \mathbb F| \) and/or \(| E(\mathbb F)| \) have large prime factors. Usually this is accomplished by reducing a global elliptic curve with complex multiplication by \(\mathfrak o\), which in turn is obtained from the ring class field \(K\) of the imaginary quadratic order \(\mathfrak o\). The known methods to construct \(K\) by singular values of modular functions may fail for special types of discriminants, or yield minimal polynomials with too large coefficients. For their new approach, the authors investigate a class of modular functions for \(\Gamma_0 (N)\) (\(N=p_1 p_2\) with primes \(p_1,p_2\)), so-called double eta quotients \[ \mathfrak w_{p_1,p_2} (z) = \frac {\eta(z/p_1) \eta(z/p_2)} {\eta(z) \eta(z/N)}, \] where \(\eta\) denotes Dedekind's eta-function. These yield an explicit construction of the ring class field (without restrictions on the discriminant) and class polynomials with rather small coefficients. In general, these double eta quotients do no longer generate an extension field of \(\mathbb C (j)\) of genus \(0\), but the authors suggest a way how to use the modular polynomial giving the algebraic relation between \(\mathfrak w_{p_1,p_2}\) and \(j\) (with coefficients from \(\mathbb Z\)) to obtain the \(j\)-invariant of the elliptic curve over \(\mathbb F\). The paper concludes with a numerical example of cryptographic size.