find the structure of an elliptic curve over a finite field

For the elliptic curves E1,E2,E3, and E4 defined below, determine the structure of the groups Ek(F13) by using the information given below together with a minimal amount of extra (hand) calculation. (Hint: Look at the 2-torsion and/or 3-torsion points of Ek.) Be sure to include enough calculation to justify your conclusions.

(a)Let E1: $y^2 = x^3 + x + 2$ and E2: $y^2 = x^ 3 + 1$, and use the fact that |E1(F13)|= |E2(F13)| = 12.

(b)Let E3: $y^2 = x^3 + 3$ and E4: $y^2 = x^3 + 3x + 5$, and use the fact that |E3(F13)|= |E4(F13)| = 9.

This is more of a research question, as we have not gone over this exact type of question in class. I have been unable to find any similar questions online to help me through this. By "structure", what exactly do they mean? Its order? What it is isomorphic to? Any points would be great!

when i calculate the points, (i've only done E1 so far) I don't obtain 9, which I should right? Also, I am computing the points, in order to see what the orders are. Am I going in the right direction? thanks!

• Hint: They tell you the number of elements in your group. For instance, $E_3(F13)$ is a group with $9$ elements. There are, up to isomorphism, only two groups with $9$ elements. It is either the cyclic group with $9$ elements, or the product of two cyclic groups with $3$ elements in each. Determine which one it is by examining things such as the order of elements in your group. – TomGrubb Dec 15 '15 at 5:56
• thank you! ill try starting with that – queence Dec 15 '15 at 18:29
• when i calculate the points, (i've only done E1 so far) I don't obtain 12, which I should right? Also, I am computing the points, in order to see what the orders are. Am I going in the right direction? thanks! @bburGsamohT – queence Dec 18 '15 at 16:34
• I will attempt $E_2$ and get back with you in a bit – TomGrubb Dec 18 '15 at 16:42
• To do $E_2$ (along the lines suggested by @bburGsamohT) you need to recall that an abelian group of order 12 is isomorphic to either $C_{12}$ or $C_6\times C_2$. The difference between these two groups is in their 2-torsion. The equation is in the simplified Weierstrass form so we know that 2-torsion points are those with $y=0$. Because $13\equiv1\pmod 6$ we know that A) $-1$ is a cubic residue modulo $13$, and B) cubing is a three-to-one mapping from $\Bbb{F}_{13}^*$. This tells you the number of 2-torsion points, and leaves you with a single possibility for the group structure. – Jyrki Lahtonen Dec 20 '15 at 9:12

For the structure, as pointed out by @bburGsamohT, you have just to see at the given numbers $12$ and $9$. I give you here a method to find directly the solutions in this particular case of the field $\mathbb F_{13}$.

The number $2$ is a primitive root modulo $13$ and you have the following values to be considered. $$\mathbb F_{13}=\{1,2,3,4,5,6,7,8,9,10,11,12\}\cup\{0\}$$ and, in correlative position, you have $$\mathbb F_{13}=\{2^{12},2^1,2^4,2^2,2^9,2^5,2^{11},2^3,2^8,2^{10},2^7,2^6\}\cup\{0\}$$ Both, $G(x)=x^3$ and $g(x)=x^2$ are not surjective; one has (always in correlative position)$$\text{cubes}\space G(x) \in\{2^{12},2^3,2^{12},2^6,2^3,2^3,2^9,2^9,2^{12},2^6,2^9,2^6\}\cup\{0\}$$ $$\text{squares}\space g(x)\in\{2^{12},2^2,2^8,2^4,2^1,2^6,2^{10},2^6,2^4,2^8,2^2,2^{12}\}\cup\{0\}$$

(Example:$7^3=(2^{11})^3=2^{33}=2^{2\cdot 13+7}=(2^2)^{13}\cdot2^7=2^{2+7}=2^9$; recall $a^p=a$).

Therefore $$G(\mathbb F_{13})=\{0,2^{12},2^3,2^6,2^9\}=\{0,1,8,12,5\}$$ and $$g(\mathbb F_{13})=\{0,2^12,2^2,2^8,2^4,2^1,2^6,2^{10}\}=\{0,1,4,9,3,2,12,10\}$$ We need some detail for $G$. one has $$\begin{cases} G^{-1}(\{13=0\})=\{0\}\\G^{-1}(\{1=2^{12}\})=\{2^{12},2^4,2^8\}\\G^{-1}(\{8=2^3\})=\{2^1,2^9,2^5\}\\G^{-1}(\{12=2^6\})=\{2^2,2^{10},2^6\}\\G^{-1}(\{5=2^9\})=\{2^{11},2^3,2^7\}\end{cases}$$ Therefore for $x^3$ in the equations $E_i; i=1,2,3,4$ there are at first the five possibilities $0,1,8,12,5$ each of them giving $1,3,3,3,3$ pre-images by $G$ respectively, so that all the $13$ cases to consider but we now have a way to act directly.

Try the equation $$E_2: y^2=x^3+1$$

$E_2:y^2=x^3+1\iff 2^{2m}=2^{3n}+1$ One has $$y^2= \begin{cases}0+1\\1+1\\8+1\\12+1\\5+1\end{cases}=\begin{cases}1\\2\\9\\13\\6\end{cases}$$ We can see that each element of $\{1,2,9,13=0,6\}$ excepting $6=2^5$ belongs to $g(\mathbb F_{13})$; thus one have to discard the set $G_{-1}({5})=\{7,8,11\}$ and counting the pre-images by $g$ of $1,2,9$ and $0$; this gives, quickly now $\{1,12\}$ for $1$, $\{5\}$ for $2$, $\{3,10\}$ for $9$ and $\{0\}$ for $0$. Hence there are six good values for $x$ each of them (because of the square $y^2$) gives two values for $y$. Thus there are $12$ solutions for $E_2: y^2=x^3+1$ as say the statement of the problem. For the other three equations you have to act similarly with $$E_1:2^{2m}=2^{3n}+2^n+2$$ $$E_3:2^{2m}=2^{3n}+2^4$$ $$E_4:2^{2m}=2^{3n}+2^4\cdot 2^n+2^9$$

FINAL NOTE.- You have to apply besides the addition of elliptic curves in order to determine the asked structure. You know the possibilities with $9$ and $12$ elements but not what of these applying here. The problem is really long.