0
$\begingroup$

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$?

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
5
  • 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$ Feb 22, 2016 at 15:45
  • 2
    $\begingroup$ I think $N(E',p) = 2(p+1)-N(E,p) (p \not= 2)$ is simpler. $\endgroup$ Feb 22, 2016 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$ Feb 22, 2016 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$ Feb 22, 2016 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$ Feb 23, 2016 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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