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?

  • $\begingroup$ 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. $\endgroup$ Sep 18, 2017 at 6:39
  • $\begingroup$ (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.. $\endgroup$ Sep 18, 2017 at 6:41
  • $\begingroup$ 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? $\endgroup$
    – Harry Alli
    Sep 18, 2017 at 9:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy