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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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)$.

Improve this answer
$\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$
    – Noam D. Elkies
    Commented 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$
    – David Lampert
    Commented 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$
    – Joe Silverman
    Commented 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$
    – Joe Silverman
    Commented 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$
    – Noam D. Elkies
    Commented Feb 23, 2016 at 0:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .