# Find special elliptic curves from j-invariant

Let $E$ be the elliptic curve defined over $GF(p)$ and $j$ be j-invariant of $E$, where $p$ is a big prime number. Also suppose $l$ be small prime number (for example $l<5000$) and $\#E$ denote number of points over $E$.

Given $j,p$ and $l$, is there deterministic method to find $E$ such that $l$ divide $\#E$?

Write down one elliptic curve $E/GF(p)$ with invariant $j(E)=j$. (There's a simple formula to do that.) Use a standard (poly-time) algorithm to compute $N(E,p):=\#E(GF(p))$. Assuming that $j\ne0$ and $j\ne1728$, then $E$ has a unique quadratic twist over $GF(p)$, so find a non-square in $GF(p)$ and use it to write down an equation for the twist, call it $E'$. Again use the poly-time algorithm, compute $N(E',p):=\#E'(GF(p))$. If either of the numbers $N(E,p)$ or $N(E',p)$ is divisible by $l$, you win. Otherwise there is no such curve over $GF(p)$ with the given $j$-invariant.
However, if you didn't mean to specify the value of $j$, but just want some elliptic curve defined over $GF(p)$ with $l\mid N(E,P)$, then what you need to do is find a point on the modular curve $X_1(l)$ that is defined over $GF(p)$.
• I think $N(E',p) = 2(p+1)-N(E,p) (p \not= 2)$ is simpler. – David Lampert Feb 22 '16 at 15:52
• @NoamD.Elkies I know the OP asked for "deterministic", but I assumed that he/she wanted "practical deterministic". If one doesn't specify $j$, is there a practical way to find an $\mathbb F_p$ point on $X_1(\ell)$ if, say, $\ell$ is in the $10^3$ to $10^4$ range? – Joe Silverman Feb 22 '16 at 19:14
• Probably practical but not easy . . . e.g. find equations for $X_0(\ell)$ and the auxiliary information to find the isogenies it parametrizes, then try lots of rational points until eventually (in $O(\ell)$ tries) one of them yields an isogeny whose kernel consists of rational points. – Noam D. Elkies Feb 23 '16 at 0:07