In Stinson's Cryptography Theory and Practice, a theorem is given without proof:
Theorem 6.1 Let $E$ be an elliptic curve defined over $Z_p$, where $p$ is prime and $p > 3$. Then there exist positive integers $n_1$ and $n_2$ such that $(E,+)$ is isomorphic to $Z_{n_1} \times Z_{n_2}$. Further $n_2 | n_2$ and $n_2 | (p – 1)$
While I understand that for some $(e_x,e_y) \in E, \exists\;(z_x,z_y)\in Z_{n_1} \times Z_{n_2}:(e_x,e_y) \cong (z_x,z_y)$, I am interested in the mapping $\phi:\phi(E) \mapsto(Z_{n_1} \times Z_{n_2})$, which is given nowhere in the text and I have had no success finding any such mapping in my searches through other texts or online sources.
Could anyone suggest to me an appropriate source where I might learn about (this mapping)/(constructing this mapping)?
Best Answer
The $\mathbb{Z}/p\mathbb{Z}$-rational points of $E$ form a finite abelian group $E(\mathbb{Z}/p\mathbb{Z})$, so there exist uniquely defined integers $n_1,n_2,\ldots,n_k$ (the invariant factors) such that $1<n_k$ and $ n_{\ell+1}\mid n_{\ell}$ for all $\ell=1,2,\ldots,k-1$, and $$ E(\mathbb{Z}/p\mathbb{Z})\cong\mathbb{Z}/n_1\mathbb{Z}\oplus \mathbb{Z}/n_2\mathbb{Z}\oplus\cdots\oplus\mathbb{Z}/n_k\mathbb{Z}. $$ This is true for all finite abelian groups.
We need two special properties of elliptic curves to reach the conclusion. For one, the subgroup $E[m]$ of points $P\in E$ with the property $[m]P=0$ (i.e. torsion of order a factor of $m$) never has more than $m^2$ points. This means that $k\le2$, for if $n_3>1$, then we would have $|E[n_3]|\ge n_3^3$.
So we know that $E(\mathbb{Z}/p\mathbb{Z})\cong\mathbb{Z}/n_1\mathbb{Z}\oplus \mathbb{Z}/n_2\mathbb{Z}$ for some $n_2\mid n_1$. What this means is that $|E[n_2]\cap E(\mathbb{Z}/p\mathbb{Z})|=n_2^2$. The Weil pairing of $\mathbb{Z}/p\mathbb{Z}$-rational points takes values in the multiplicative group $\mathbb{Z}/p\mathbb{Z}^*$. Furthermore, when restricted to $E[n_2]$ the pairing takes all the roots of unity of order $n_2$ as values. These two items together imply that roots of unity of order $n_2$ must belong to the prime field $\mathbb{Z}/p\mathbb{Z}$, and hence $n_2\mid p-1$.
It seems to me that your main question is about constructing an explicit isomorphism $\phi:E(\mathbb{Z}/p\mathbb{Z})\to\mathbb{Z}/n_1\mathbb{Z}\oplus \mathbb{Z}/n_2\mathbb{Z}$. This is a taller order. Basically you first need to find both $n_2$ and $n_1$. Before that you must find the order of $E(\mathbb{Z}/p\mathbb{Z})$. The Schoof-Elkies-Atkin algorithm is often used there. IIRC in Menezes' book (mentioning it because it is also widely used among crypto people) an algorithm for finding $n_1$ (and thus also $n_2$) is described. Then you "just" need to find a point $P_1$ of order $n_1$, and then a point $P_2$ of order $n_2$ such that the pairing of $([n_1/n_2]P_1,P_2)$ is a primitive root of unity of order $n_2$. Then an isomorphism is given by $$ \phi: [x]P_1+[y]P_2\mapsto (x,y). $$
Because finding $n_1$ and $n_2$ is a complicated process (though the algorithms run in polynomial time) I'm fairly sure that there does not exist a simple way of writing this isomorphism down given, say, the equation of $E$ in Weierstrass form.