Check if Two Elliptic Curves have the Same Number of Points

Question

Given two elliptic curves $E_1$, $E_2$ over $F_q$. Assume that the two curves’ order is unknown. Is there a way to tell if they have equal order without counting it?

Meaning, if $N_i(A_i,B_i,q)$ is the order of Curve $E_i$ ($A_i, B_i$ are the curve’s parameters in the standard form), how can one tell if $N1=N_2$ without knowing $N_1$,$N_2$.

One direction is related to Isogenies. If the two curves are Isogenous, then over finite fields they will have the same order. I also saw that the $l$-Modular polynomial is zeroed over the $j$-invariant of two curves if they have an $l$-isogeny. Meaning $\Phi_l(j(E_1),j(E_2))=0$ in this case.

But if I follow this direction, which options of $l$ I have to check? And how is computing the Modular polynomial for all $l$ options done?

Answer 1

I will say some words on the question. However, as it comes, it is too general and slightly unclear. So the answer is Yes and No. Here are the two parts.

Yes: In very special cases, we can already predict the order of an elliptic curve. For instance, the following result of Gauss gives full information on the order of an elliptic curve of the shape: $$ E(B)\text{ over }\Bbb F_p\ :\qquad y^2 = x^3+B\ ,\qquad\text{ where $p$ prime is two modulo three.} $$ Then there are $p+1$ $\Bbb F_p$-rational points on the above curve for every $B\ne 0$, so that $E(B)$ is not degenerated. So for instance for the prime $p=101$, we have $p+1=102$ points on all $E(B)$ for $B\ne 0$. Some curves used in cryptography are members of special families.

No: In some cases it is from the human perspective a pure luck that two elliptic curves defined over the same field have the same number of elements. So if the human eye is missing a hint on the way some curves $E_1$ and $E_2$ are constructed, there will be no chance to claim same order without counting. For instance, for $p=101$ there is the following statistic of the number of elliptic curves $E(A,B)$ defined by $y^2=x^3+Ax+B$ realizing a specific order $N$, i.e. $\# E(A,B)=N$: $$ \begin{array}{|c|c|} \hline N & \# \text{ of }(A,B)\\\hline\hline 82 & 25\\\hline 83 & 50\\\hline 84 & 300\\\hline 85 & 100\\\hline 86 & 100\\\hline 87 & 250\\\hline 88 & 300\\\hline 89 & 100\\\hline 90 & 400\\\hline 91 & 150\\\hline 92 & 500\\\hline 93 & 200\\\hline 94 & 200\\\hline 95 & 200\\\hline 96 & 600\\\hline 97 & 150\\\hline 98 & 200\\\hline 99 & 400\\\hline 100 & 375\\\hline 101 & 100\\\hline 102 & 700\\\hline 103 & 100\\\hline 104 & 375\\\hline 105 & 400\\\hline 106 & 200\\\hline 107 & 150\\\hline 108 & 600\\\hline 109 & 200\\\hline 110 & 200\\\hline 111 & 200\\\hline 112 & 500\\\hline 113 & 150\\\hline 114 & 400\\\hline 115 & 100\\\hline 116 & 300\\\hline 117 & 250\\\hline 118 & 100\\\hline 119 & 100\\\hline 120 & 300\\\hline 121 & 50\\\hline 122 & 25\\\hline \end{array} $$ Now somewhere in the list is the number $N=91$ with the "complicated factorization" $91=7\cdot 13$, which is unknown. But this information is hard to use or connect with two individual curves among the many of them realizing this order. For instance $y^2=x^3+3x+6$ and $y^2=x^3+3x+7$. Why should these curves have the same rank?