# Isomorphisms to Additive Group of Integers to Solve ECDLP

I know that with prime ordered Elliptic Curve Groups, the Elliptic Curve Discrete Logarithm Problem (ECDLP) can be solved easily by defining an isomorphism to the additive group of integers mod $p$ where $p$ is the order of the group. The ECDLP is transformed into a simpler matter of performing the Extended Euclidean algorithm. However, for non-prime ordered groups, can a similar isomorphism to the additive group of integers be defined?

Would one need to compute the order of a point X and then define an Isomorphism between the cyclic subgroup generated by X and the group of additive integers modulo the order?

• I'm afraid the question sounds a bit confused. IF (a BIG if) you have an easily computable isomorphism from an elliptic curve $E$ to the additive group $\Bbb{Z}/n\Bbb{Z}$, then the ECDLP on $E$ is, indeed, solved by the Extended Euclidean algorithm. This is quite irrespective of whether $n$ is a prime number or not. The catch is that given a generating point $P\in E$ of known order $n$, we have an easily computable (for a suitable definition of easy) isomorphism $\phi:\Bbb{Z}/n\Bbb{Z}\to E$. BUT the inverse of that function is NOT easily computable. Sep 18, 2017 at 6:39
• (cont'd), so ECDLP remains uncracked. Again, irrespective of whether $n$ is a prime or not. Caveat: I assumed that $E$ was chosen in such a way that its $K$-rational points form a cyclic group. This is often the case with the elliptic curves chosen for crypto, but does not hold for all (most?) elliptic curves.. Sep 18, 2017 at 6:41
• Thank you very much. I guess a way to rephrase my question would be if the primality of the order of the group made the inverse of that function easier to compute. The reasoning behind this being: if the group order was a prime number, every non-identity point along the curve would have order equal to the group order by Lagrange's Theorem, so one would avoid computing the order of a particular point with like the Baby-step Giant-step algorithm, which is needed to define the inverse of the isomorphism given above. Does computing the inverse of the function mainly rely on the point order then? Sep 18, 2017 at 9:46