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.
[Math] What are some open problems regarding elliptic curves in finite fields
elliptic-curvesfinite-fieldsopen-problemsreference-request
Related Solutions
$\newcommand\F{\mathbf{F}}$ $\newcommand\Z{\mathbf{Z}}$ $\newcommand\SL{\mathrm{SL}}$
Because of the existence of the Weil paring, elliptic curves with such a subgroup only exist when $p \equiv 1 \mod \ N$.
Let $S_N$ denote the set of elliptic curves over $\F_p$ such that $E[N]$ is defined over $\F_p$. It will be slightly easier to assume that $N \ge 3$. In this case, $Y(N)$ is a fine moduli space, and an $\F_p$-point on $Y(N)$ corresponds to a pair $(E,\alpha:E[N] \simeq \Z/N\Z \times \Z/N \Z)$ defined over $\F_p$. Given an elliptic curve $E \in S_N$, how many points does it contribute to $Y(N)$? For a curve $E$ whose automorphism group is $\Z/2\Z$, We see that out of the $|\SL_2(\Z/N\Z)|$ possible choices of $\alpha$ (technical remark, we have fixed a Weil pairing so that $Y(N)$ is connected), $(E,\alpha) \simeq (E,\alpha')$ only if $\alpha' = \alpha$ or $\alpha' = [-1] \alpha$. Thus $E$ contributes $|\SL_2(\Z/N\Z)|/2$ points to $Y(N)(\F_p)$. In general, $E$ may have slightly more automorphisms, and we deduce that (for $N \ge 3$): $$|Y(N)(\F_p)| = |\SL_2(\Z/N\Z)| \sum_{E \in S_N} \frac{1}{|\mathrm{Aut}(E)|}.$$ Note that the quantity on the right is very close to $|\SL_2(\Z/N\Z)| \cdot |S_N|/2$, one only has to worry about the elliptic curves with $j = 0$ or $j = 1728$, and this can be done by hand if one wants to cross all the i's and dot all the t's.
Suppose that $X(N)$ has $c_N$ cusps and genus $g_N$ (there are some explicit slightly unpleasant formulas for these numbers, which can be found (for example) in Shimura's book. All the cusps are defined over $\F_p$ (with $p \equiv 1 \mod N$) so by the Riemann hypothesis for finite fields, $$|Y(N)(\F_p) - (1+p) + c_N| = |X(N)(\F_p) - (1+p)| \le 2 g_N \sqrt{p}.$$ If $g_N = 0$ (which only happens if $N \le 5$), this leads to an exact formula for $|S_N|$. In general, at least for large $p$, we see that $$|S_N| \sim \frac{2p}{|\SL_2(\Z/N \Z)|}.$$
To make this all completely explicit for $N = 3$ (for example), one gets, presuming I have not made a horrible computational error which is quite possible: $$S_3 = \begin{cases} (p+11)/12, & p \equiv 1 \mod \ 12, \\\ (p+5)/12, & p \equiv 7 \mod \ 12. \end{cases}$$ (note that $p \equiv 1 \mod 3$):
Of course, "exact formulas" will only exist for $N \le 5$. Some related and slightly more difficult counting problems are also nicely explained by Lenstra here (See 1.10):
https://openaccess.leidenuniv.nl/bitstream/1887/3826/1/346_086.pdf
Douglas Ulmer wrote up expository notes for his short course at PArk City on precisely this topic:
http://arxiv.org/abs/1101.1939
This might be a good place to start.
Best Answer
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.