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)$.

  • 1
    $\begingroup$ Note, though, that "find a non-square in GF(p)" is a notorious example of a problem that's very easily in RP but not known to be in P. (The OP didn't actually specify polynomial time, but if any deterministic algorithm is acceptable then one could even try all elliptic curves mod p . . .) $\endgroup$ – Noam D. Elkies Feb 22 '16 at 15:45
  • 2
    $\begingroup$ I think $N(E',p) = 2(p+1)-N(E,p) (p \not= 2)$ is simpler. $\endgroup$ – David Lampert Feb 22 '16 at 15:52
  • $\begingroup$ @DavidLampert Good point, I did know that, but it slipped my mind. Of course, the main point is that the likely answer is that there are no such curves. $\endgroup$ – Joe Silverman Feb 22 '16 at 19:11
  • $\begingroup$ @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? $\endgroup$ – Joe Silverman Feb 22 '16 at 19:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Feb 23 '16 at 0:07

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.