7
$\begingroup$

I accept that my question seems so vague and broad, and I already looked into some similar questions in MO. But I would like to learn specifically about some open problems and conjectures regarding elliptic curves in finite fields. Also if there is something about their isogeny in particular it is highly welcomed. If you can provide also a reference to where the problem was formulated I would be glad. To clarify, both theoretical and computational open problems are welcomed.

$\endgroup$
2
  • $\begingroup$ Too broad! I guess that when it comes to questions there are computational ones and theoretical ones. Are you interested in the computational ones? For example people use elliptic curves over finite fields in cryptography so an interesting open problem is solving the discrete log problem on an elliptic curve quickly. $\endgroup$
    – eric
    Dec 5, 2015 at 14:19
  • $\begingroup$ @eric Both computational and theoretical are highly welcomed. And yes discrete log problem is a famous one. Any other theoretical or computational open problems or conjectures? $\endgroup$
    – terett
    Dec 5, 2015 at 14:21

1 Answer 1

7
$\begingroup$

We know that, given an elliptic curve over a finite field $\mathbb{F}_q$, there exists integers $m,n$ with $m|n$ such that the group of rational points is a product of a cyclic group of order $m$ and a cyclic group of order $n$. I believe it is still open to deterministically, in polynomial time, compute $m,n$ (a big obstacle is to do it without factoring the gcd of $mn$ and $q-1$). Even if that's solved, I know it's an open problem to, again deterministically, in polynomial time, compute two points of order $m,n$ (or one point if $m=1$) that generate the group of rational points. (NB polynomial time means polynomial in $\log q$).

Another question which just occurred to me is, given two elliptic curves over the same finite field with the same number of rational points, deterministically, in polynomial time, compute an isogeny between them. The proof of Tate's theorem seems horribly inefficient from a computational point of view.

$\endgroup$
2
  • $\begingroup$ Thanks for the two computational open problems. Do there exist also some theoretical problems? $\endgroup$
    – terett
    Dec 5, 2015 at 15:28
  • 2
    $\begingroup$ @terett A different proof of Tate's isogeny theorem (specially one that worked only with elliptic curves) would be interesting. $\endgroup$ Dec 5, 2015 at 18:17

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.