Exercise 5.8.2 (Isomorphisms between elliptic curves on $\mathbb{Z}_p$)

Proof. Here we take ${\mathbb{Z}}_p={𝔽}_p=\mathbb{Z}∕\mathit{p\mathbb{Z}}$ as the field with $p$ elements, so we consider

as a subset of ${(\mathbb{Z}∕\mathit{p\mathbb{Z}})}^2$ (where $A,B$ in $\mathbb{Z}∕\mathit{p\mathbb{Z}}$), and $E_f({\mathbb{Z}}_p)$ is the additive group ${𝒞}_f({\mathbb{Z}}_p)\cup \{O\}$, where $O$ is the point at infinity of the curve, and the neutral element of $E_f({\mathbb{Z}}_p)$.

(a)

If $(x,y)\in {𝒞}_f({\mathbb{Z}}_p)$, then $y^2=x^3-\mathit{Ax}-B$. Therefore $${(r^{3}y)}^2=r^6{y}^2={(r^{2}x)}^3-r^{4}A(r^{2}x)-r^{6}B.$$

This means that $(u,v)=(r^{2}x,r^{3}y)$ satisfies the equation

$$v^2=u^3-r^4\mathit{Au}-r^{6}B=u^3-A^{\prime }u-B,$$

where $A^{\prime }=r^{4}A,B^{\prime }=r^{6}B$, i.e. $(u,v)\in {𝒞}_g({\mathbb{Z}}_p)$, where $g(u,v)=v^3-A^{\prime }u-B^{\prime }$.

Note that the discriminant of $u^3-A^{\prime }u-B^{\prime }$ is given by ${\mathrm{\Delta }}^{\prime }=4{A{}^{\prime }}^3-27{B{}^{\prime }}^2=r^{12}(4A^3-27B^2)=r^{12}\mathrm{\Delta }$, so that if ${𝒞}_f({\mathbb{Z}}_p)$ is an elliptic curve, so is ${𝒞}_g({\mathbb{Z}}_p)$ if $r\ne 0$.

Consider now the linear map ${\phi }_r:{\mathbb{Z}}_p^2\to {\mathbb{Z}}_p^2$ defined by $\phi (x,y)=(r^{2}x,r^{3}y)$, where $r\ne 0$. Thus $\det <!--\; FUNCTION\; APPLICATION\; -->(\phi )=r^5\ne 0$, and ${\phi }_r$ is an automorphism of ${\mathbb{Z}}_p^2$.

Consider the restriction ${\psi }_r$ of ${\phi }_r$ to the curves ${𝒞}_f({\mathbb{Z}}_p),{𝒞}_g({\mathbb{Z}}_p)$:

$${\psi }_r\{\begin{array}{ccc}\hfill {𝒞}_f({\mathbb{Z}}_p)\hfill & \hfill \to \hfill & {𝒞}_g({\mathbb{Z}}_p)\hfill \\ \hfill (x,y)\hfill & \hfill \mapsto \hfill & (r^{2}x,r^{3}y).\hfill \end{array}$$

• Since ${\phi }_r$ is injective, so is ${\psi }_r$: for all $(x,y)\in {𝒞}_f({\mathbb{Z}}_p)$ and $(x^{\prime },y^{\prime })\in {𝒞}_f({\mathbb{Z}}_p)$

  $${\psi }_r(x,y)={\psi }_r(x^{\prime },y^{\prime })\Rightarrow {\phi }_r(x,y)={\phi }_r(x^{\prime },y^{\prime })\Rightarrow (x,y)=(x^{\prime },y^{\prime }).$$

• We show that ${\psi }_r$ is surjective. Let $(u,v)\in {𝒞}_g({\mathbb{Z}}_p)$. Put $(x,y)=(r^{-2}u,r^{-3}v)$, where $r^{-1}$ is the inverse of $r\ne 0$ in $\mathbb{Z}∕\mathit{p\mathbb{Z}}$. Then $(x,y)\in {𝒞}_f({\mathbb{Z}}_p)$, because

  $$r^6{y}^2=v^2=u^3-A^{\prime }u-B^{\prime }=r^6(x^3-\mathit{Ax}-B),(r\ne 0),$$

  and $\psi (x,y)=(u,v)$. This shows that ${\psi }_r$ is surjective.

So ${\psi }_r$ is bijective, and its reciprocal is ${\psi }_r^{-1}={\psi }_{r^{-1}}$.

In other words, ${\psi }_r$ places the points of ${𝒞}_f({\mathbb{Z}}_p)$ in bijective correspondence with those of ${𝒞}_g({\mathbb{Z}}_p)$.

(b)

The linear automorphism ${\phi }_r$ sends any line $L$, of equation $\mathit{ax}+\mathit{by}+c$ on the line $L^{\prime }:a{r}^{-2}u+b{r}^{-3}v+c=0$. Therefore ${\phi }_r$ sends three aligned points on three aligned points.

If $P=(x,y)$ is some point on ${𝒞}_f({\mathbb{Z}}_p)$, then $-P=(x,-y)$, ${\phi }_r(P)=(r^{2}x,r^{3}y)$ and ${\phi }_r(-P)=(r^{2}x,-r^{3}y)=-{\phi }_r(P)$.

Suppose that $M,N,P$ are three distinct aligned points on ${𝒞}_f({\mathbb{Z}}_p)$. Then $M+N+P=0$. Moreover $M^{\prime }={\phi }_r(M),N^{\prime }={\phi }_r(N)$ and $P^{\prime }={\phi }_r(P)$ are distinct and aligned, and are on the curve ${𝒞}_g({\mathbb{Z}}_p)$, so $M^{\prime }+N^{\prime }+P^{\prime }=0$. Therefore $M^{\prime }+N^{\prime }=-P^{\prime }=-{\phi }_r(P)={\phi }_r(-P)={\phi }_r(M+N)$. This shows that

$$\begin{array}{lll}\hfill {\phi }_r(M+N)={\phi }_r(M)+{\phi }_r(N).& & \hfill \text{(1)}\end{array}$$

Unfortunately, this argument proves (1) only if $A,B$ and $\mathit{AB}$ are distinct. To prove the general case, we use the explicit formulas (5.52), (5.53). Let $M=(x_1,y_1),N=(x_2,y_2)$, and $P=A+B=(x_3,y_3)$, and put $M^{\prime }={\phi }_r(M)=(u_1,v_1),N^{\prime }={\phi }_r(B)=(u_2,v_2),P^{\prime }={\phi }_r(P)=(u_3,v_3)$.

• If $M\ne N$, by (5.52) (where $a=0$),

  $$\begin{array}{llll}\hfill x_3& ={\left(\frac{y_2-y_1}{x_2-x_1}\right)}^2-x_1-x_2,& \hfill & \\ \hfill y_3& =-y_1-\left(\frac{y_2-y_1}{x_2-x_1}\right)(x_3-x_1).& \hfill & \end{array}$$

  Multiplying the first line by $r^2$, and the second by $r^3$, we obtain

  $$\begin{array}{llll}\hfill r^2{x}_3& ={\left(\frac{r^3{y}_2-r^3{y}_1}{r^2{x}_2-r^2{x}_1}\right)}^2-r^2{x}_1-r^2{x}_2,& \hfill & \\ \hfill r^3{y}_3& =-y{r}_1^3-\left(\frac{r^3{y}_2-r^3{y}_1}{r^2{x}_2-r^2{x}_1}\right)(r^2{x}_3-r^2{x}_1).& \hfill & \end{array}$$

  Therefore

  $$\begin{array}{llll}\hfill u_3& ={\left(\frac{v_2-v_1}{u_2-u_1}\right)}^2-u_1-u_2,& \hfill & \\ \hfill v_3& =-v_1-\left(\frac{v_2-v_1}{u_2-u_1}\right)(u_3-u_1).& \hfill & \end{array}$$

  This shows that $M^{\prime }+N^{\prime }=P^{\prime }$ on ${𝒞}_g({\mathbb{Z}}_p)$.

• If $M=N$, by (5.53) (where $a=0$ and $b=-A$),

  $$\begin{array}{llll}\hfill x_3& ={\left(\frac{3x_1^2-A}{2y_1}\right)}^2-2x_1,& \hfill & \\ \hfill y_3& =-y_1-\left(\frac{3x_1^2-A}{2y_1}\right)(x_3-x_1).& \hfill & \end{array}$$

  Multiplying the first line by $r^2$, and the second by $r^3$, we obtain

  $$\begin{array}{llll}\hfill r^2{x}_3& ={\left(\frac{3r^4{x}_1^2-r^{4}A}{2r^3{y}_1}\right)}^2-2r^2{x}_1,& \hfill & \\ \hfill r^3{y}_3& =-r^3{y}_1-\left(\frac{3r^4{x}_1^2-r^{4}A}{2r^3{y}_1}\right)(r^2{x}_3-r^2{x}_1).& \hfill & \end{array}$$

  Using $A^{\prime }=r^{4}A$, this gives

  $$\begin{array}{llll}\hfill u_3& ={\left(\frac{3u_1^2-A^{\prime }}{2v_1}\right)}^2-2u_1,& \hfill & \\ \hfill v_3& =-v_1-\left(\frac{3u_1^2-A^{\prime }}{2v_1}\right)(u_3-u_1).& \hfill & \end{array}$$

  This shows that $M^{\prime }+N^{\prime }=2M^{\prime }=P^{\prime }$ on ${𝒞}_g({\mathbb{Z}}_p)$.

In either case, for all $M,N\in {𝒞}_f({\mathbb{Z}}_p)$,

$$\begin{array}{lll}\hfill {\phi }_r(M)+{\phi }_r(N)={\phi }_r(M+N).& & \hfill \end{array}$$

So ${\psi }_r(M)+{\psi }_r(N)={\psi }_r(M+N)$ for all $M,N\in {𝒞}_f({\mathbb{Z}}_p)$.

We extend ${\psi }_r$ by ${\psi }_r(O)=O^{\prime }$, where $O^{\prime }=O=(0:1:0)$ is the point at infinity of ${𝒞}_g({\mathbb{Z}}_p)$, then ${\psi }_r(M)+{\psi }_r(N)={\psi }_r(M+N)$ remains true if $M=O$ or $N=O$, so

$$\forall <!--\; FUNCTION\; APPLICATION\; -->M\in E_f({\mathbb{Z}}_p),\forall <!--\; FUNCTION\; APPLICATION\; -->N\in E_g(Z_p),{\psi }_r(M)+{\psi }_r(N)={\psi }_r(M+N).$$

Therefore ${\psi }_r:E_f({\mathbb{Z}}_p)\to E_g({\mathbb{Z}}_p)$ is a group isomorphism, so

$$E_f({\mathbb{Z}}_p)\simeq E_g({\mathbb{Z}}_p).$$

(c)

We consider the group $G$ of linear automorphisms ${\phi }_r$ of ${\mathbb{Z}}_p^2$, where the matrix of ${\phi }_r$ is ${ℳ}_r=\left(\begin{array}{cc}\hfill r^2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill r^3\hfill \end{array}\right)$, where $r\ne 0$. $G$ is a subgroup of ${\mathrm{GL}}_2({\mathbb{Z}}_p)$, because $e={\phi }_1\in G$, ${\phi }_r\circ {\phi }_s={\phi }_{\mathit{rs}}\in G$ and ${\phi }_r^{-1}={\phi }_{r^{-1}}\in G$ for all $r\ne 0,s\ne 0$.

By part (a), $G$ acts on the set $S$ of elliptic curves ${𝒞}_{A,B}$ with equation $y^2=x^3-\mathit{Ax}-B$ by the action

$${\phi }_r\cdot {𝒞}_{A,B}={\phi }_r({𝒞}_{A,B})={𝒞}_{A^{\prime },B^{\prime }},A^{\prime }=r^{4}A,B^{\prime }=r^{6}B.$$

(This is a group action, because ${\phi }_1\cdot {𝒞}_{A,B}={𝒞}_{A,B}$, and ${\phi }_r\cdot ({\phi }_s\cdot {𝒞}_{A,B})={\phi }_r({\phi }_s({𝒞}_{A,B}))=({\phi }_r\circ {\phi }_s)({𝒞}_{A,B})$.)

We introduce the relation $\sim$ defined by

$$𝒞\sim {𝒞}^{\prime }⟺\exists <!--\; FUNCTION\; APPLICATION\; -->\phi \in G,\phi \cdot 𝒞={𝒞}^{\prime }.$$

We recall that $\sim$ is an equivalence relation: for all $𝒞,{𝒞}^{\prime },{𝒞}^{″}$ in $S$,

• R. ${\phi }_1(𝒞)=e(𝒞)=𝒞$, where $e={\phi }_1={\mathrm{id}}_{{\mathbb{Z}}_p^2}$. So $𝒞\sim 𝒞$.

• S. If $𝒞\sim {𝒞}^{\prime }$, there is some $\phi \in G$ such that $\phi \cdot 𝒞={𝒞}^{\prime }$. Then

  $${\phi }^{-1}\cdot {𝒞}^{\prime }={\phi }^{-1}\cdot (\phi \cdot {𝒞}^{\prime })=({\phi }^{-1}\circ \phi )\cdot 𝒞=e\cdot 𝒞=𝒞,$$

  so ${𝒞}^{\prime }\sim 𝒞.$

• T. If $𝒞\sim {𝒞}^{\prime }$ and ${𝒞}^{\prime }\sim {𝒞}^{″}$, then there are $\phi ,\psi \in G$ such that ${𝒞}^{\prime }=\phi \cdot 𝒞,{𝒞}^{″}=\psi \cdot {𝒞}^{\prime }$, thus

  $${𝒞}^{″}=\psi \cdot (\phi \cdot 𝒞)=(\psi \circ \phi )\cdot 𝒞.$$

  Since $\psi \circ \phi \in G$, $𝒞\sim {𝒞}^{″}$.

By definition of orbits, two curves in $S$ are equivalent if and only if they are in the same orbit. We must count the number of orbits, and the number of elements in each orbit.

First the set $S$ is in bijective correspondence with the set of ordered pairs $(A,B)\in {\mathbb{Z}}_p^2$ such that $4A^3-27B^2\ne 0$. By Problem (1), there are $p^2-p$ such pairs, so

$$|S|=p^2-p.$$

Moreover, the map

$$\{\begin{array}{ccc}\hfill {\mathbb{Z}}_p^{\text{∗}}\hfill & \hfill \text{→}\hfill & G,\hfill \\ \hfill r\hfill & \hfill \mapsto \hfill & {\phi }_r\hfill \end{array}$$

is a group isomorphism, because

$$\left(\begin{array}{cc}\hfill r^2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill r^3\hfill \end{array}\right)\left(\begin{array}{cc}\hfill s^2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill s^3\hfill \end{array}\right)=\left(\begin{array}{cc}\hfill {(\mathit{rs})}^2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill {(\mathit{rs})}^3\hfill \end{array}\right),$$

so ${\phi }_{r+s}={\phi }_r\circ {\phi }_s$ for all $r,s$ in ${\mathbb{Z}}_p^{\text{∗}}$.

Therefore

Let $G_{𝒞}$ be the stabilizer of some $𝒞={𝒞}_{A,B}$. If ${\phi }_r\in G_{𝒞}$, then $A^{\prime }=r^{4}A=A$ and $B^{\prime }=r^{6}B=B$. Since $(A,B)\ne (0,0)$ (otherwise $4A^3-27B^2=0$), then $r^2=1$, so $r=\pm 1$, and ${\phi }_r=\pm e$. So

where $e\ne -e$ if $p\ne 2$.

By the fundamental theorem of group actions, if ${𝒪}_{𝒞}$ is the orbit of some curve $𝒞\in S$,

Thus every orbit has $(p-1)∕2$ elements (if $p=2$, every orbit has one element : the action is trivial).

Let $N$ be the number of orbits.Since $S$ is the disjoint union of the orbits,

so

If $p>2$ then there are $(p-1)∕2$ curves in each equivalence class, and $2p$ equivalence classes. □