Is there a theorem to determine the elliptic curve parameters based on the group order?

Question

By Hasse's theorem we know that range of the group order of the elliptic curve. And similarly, there exist a theorem on the admissible order of elliptic curves. Suppose by the theorem on the admissible order of elliptic curve we know there exist a curve of desired order then how to determine the curve parameters. For example in case of simplified/short Weierstrass equation the value of the parameters $a,b$.

My question: is there a theorem to determine the curve parameters based on the group order? Does the form of the curve matter? The different forms of the curve are Weierstrass, Montgomery, and Edwards.

Answer 1

There is a method known as "Complex Multiplication". However, it is not simple at all, and tends to be overly expensive for most target orders. See this article for some details. There is also the (theoretical) concern that a curve constructed that way may have a special structure though could possibly be leveraged into an attack one day; generally speaking, cryptographers do not like special cases and prefer the immunity of the herd by relying on random values in big sets (unless there is a performance advantage to be had with the special structure, in which case to Hell with it, let's milk the precious clock cycles -- that's how modern curves tend to be defined in fields of prime order $2^m-c$ with a very small $c$).

CM has been used to define pairing-friendly curves (curves that have a demonstrated special structure which is on the verge of being a weakness, but also enables nifty three-way protocols).

Answer 2

There can be much simpler methods than CM for group orders of a specific form. For exemple if $p \equiv 2 \pmod 3$ and $b \not\equiv 0 \pmod p$, the curve $Y^2 = X^3 + b$ over $\mathbf{F}_p$ has $p+1$ points. (The proof of this is easy and left as an exercise.) Such methods are also used to easily construct "good enough" pairing-friendly curves.

As Thomas notes in the commants, the low embedding degree of those curves makes them simultaneously good for pairings and bad for elliptic-curve discrete-log based systems. Use with caution.