Constructing an elliptic curve of prescribed order over a fixed field

Definitions and mathematical statement

Given an integer $n$ and a prime power $q$, the task is to construct an elliptic curve $E/{\mathbb{F}}_q$ with \[ \#E({\mathbb{F}}_q)=n \] whenever such a curve exists. An elliptic curve is a smooth projective genus-one curve with a rational origin; its order counts all rational points, including the origin. For example a general Weierstrass output can use \[ y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6, \qquad a_i\in{\mathbb{F}}_q, \] with nonzero discriminant and its point at infinity. The general form does not exclude characteristics two or three.

Writing $t=q+1-n$, the necessary Hasse condition is $t^2\le4q$. The supplied summary says additional divisibility/admissibility conditions determine the realizable orders, but does not list them; the Hasse condition alone is not silently made a complete existence criterion. Nonpositive $n$ cannot be group cardinalities.

A fully specified constructive problem must define the representation of ${\mathbb{F}}_q$, input encoding, output representation, feasibility handling, and complexity requirements. The source does not demand polynomial time or a uniform performance guarantee for all $q,n$. It asks for construction for every feasible pair, rather than only choosing a convenient field for a prescribed order.

Short English statement

Construct an elliptic curve of a given feasible order over the fixed finite field. Feasibility and practical efficiency are separate issues.

The supplied summary labels the problem solved in principle, citing Deuring's existence theory and the complex-multiplication method, with Atkin--Morain and Sutherland improvements. It qualifies efficient CM construction by tractable/small-class-number settings. Its implementation claims name Magma, SageMath, and "PARI/GP ECFFT" without exact versions or references; those are not independently verified here. The solved label does not establish a uniform efficient algorithm for every input, and the source's current primary-literature audit remains required.

Sources

• Local UnsolvedMath registry, permanent ID 8800044, source code catalogue entry, "Constructing an elliptic curve of prescribed order over a fixed field," proposed by Everett Howe. Dataset curation and metadata: Ulam AI and UnsolvedMath Contributors, CC BY 4.0.
• IPAM, Workshop on Number Theory and Cryptography --- Open Problems (2006), Attachment 6237, PDF page 2, schedule locator https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule; pdf-and-legacy-ppt visual-audit extraction, accessed 2026-07-29.
• Deuring, Atkin--Morain, and Sutherland are named in the supplied summary without complete primary citations or an exact admissibility/complexity theorem.
• Source provenance reports inspection of 17 PDFs and two legacy PPT decks among 19 surviving attachments, excluding repetitions and solved definitions; this is supplied provenance, not a new inspection claimed here.
• Current primary-literature status audit and redistribution terms NEEDS_REVIEW for the publicly accessible author/publisher copy, separately from the dataset licence.