Choosing a field for an elliptic curve of prescribed order

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

An elliptic curve over $\mathbb F_q$ is a smooth projective genus-one curve equipped with an $\mathbb F_q$-rational identity point. The number $\#E(\mathbb F_q)$ includes that identity. A prime power is $q=p^a$ for a prime $p$ and an integer $a\ge1$. A negative fundamental discriminant $\Delta_0$ is the discriminant of the full ring of integers $\mathcal O_K$ of the imaginary quadratic field $K=\mathbb Q(\sqrt{\Delta_0})$. Its Hilbert class polynomial is the monic polynomial whose roots are the $j$-invariants of the complex elliptic curves, up to isomorphism, with endomorphism ring $\mathcal O_K$. Here $O((\log n)^2)$ means a bound $C(\log n)^2$ for an absolute constant $C$ and all sufficiently large positive integers $n$.

Statement recorded in the supplied source.

Given a positive integer $n$, construct a prime power $q$ and an elliptic curve $E/\mathbb F_q$ with $\#E(\mathbb F_q)=n$, allowing the field size to be chosen rather than prescribed. Seek an efficient construction by choosing $q$ so that, for $t=q+1-n$, the discriminant $t^2-4q=f^2\Delta_0$, with $f\in\mathbb Z_{>0}$, has a negative fundamental discriminant $\Delta_0$ satisfying $|\Delta_0|=O((\log n)^2)$, permitting use of the Hilbert class polynomial for $\Delta_0$. The displayed discriminant size is the source's intended construction target. [S2]

Short English statement

Choose the finite field as well as the elliptic curve to realize a prescribed group order, using a small fundamental CM discriminant for efficiency.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 8800045 (AMR-087-0045). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Everett W. Howe, Low-genus curves over finite fields: Problems and variations, IPAM Number Theory and Cryptography: Open Problems workshop (9--13 October 2006), PDF pages 7--8, "The Bröker-Stevenhagen approach. https://helper.ipam.ucla.edu/publications/SCWS1/SCWS1_6237.pdf.