# Trying to better understand the failure of the Index Calculus for ECDLP

So I'm going to give you guys my understanding and then if you would be so kind as to tell me where I'm off the mark (hopefully I'm not completely wrong).

So basically the index calculus for the discrete log problem over $\mathbb{Z}_p$ takes advantage of the fact that even though we don't know the structure of $\mathbb{Z}_p^*$, we still have the homomorphism $\mathbb{Z}\rightarrow\mathbb{Z}_p^*$. And thus we can still unambiguously write elements mod $p-1$ in terms of their prime factorizations.

And so since small primes occur the most frequently in these factorizations, then if we find enough elements of $\mathbb{Z}_p^*$ which can be written in terms of powers of some collection of small primes, then we can take the $\log_{\alpha}$ of both sides and form enough linear congruences to find the value of $\log_{\alpha}$ for each one of these small primes (this is the pre-computation part). And then we finish by doing a similar procedure again but for an equation involving $\beta$.

The point wasn't to go into all the technicalities of this algorithm but to observe that the failure in the elliptic curve setting seems to boil down to the fact that there is no clear analogue of this trick when we shift settings from groups where the operation was to either add or multiply, followed by modding out, to a setting where the group operation involves the geometrically motived application of algebraic equations to relate points on a curve. Since in this case there is no well understood UFD like the integers hanging around in the background to provide homomorphisms into any $\mathbb{Z}_p$ we want.

My understanding is that attempts to extend the Index Calculus to elliptic curves basically involve attempts to get $E(\mathbb{Q})$ to play the role of the integers. But that these attempts have been met with at best marginal success and only for certain special families of elliptic curves. While the problems encountered when trying to extend to the general case currently appear insurmountable.

I also want to clarify that being able to find in polynomial time the isomorphisms $\mathbb{Z}_p^*\rightarrow \mathbb{Z}_{p-1}$ in the finite field setting or $E(\mathbb{F}_p)\rightarrow \mathbb{Z}_{n_1}\times\mathbb{Z}_{n_2}$ in the elliptic curve setting would essentially crack the discrete log problem, correct? And so it is the apparently random structure of these groups which lies at the heart of the difficulty of these problems.

• How do we have the isomorphism $\: \mathbb{Z} \cong \mathbb{Z}_p^* \:$? $\;\;$
– user991
May 10 '13 at 4:35
• oops that was supposed to be a homomorphism, I'll edit. May 10 '13 at 4:57
• What's the question again? I see some reasonable statements, but I'm having a hard time understanding what is the question you want an answer to. Can you try to formulate a concrete, answerable question?
– D.W.
May 10 '13 at 19:17
• I'm just asking if what I'm saying is or not. I suppose I don't really have a specific question. May 11 '13 at 1:06
• Is no one man enough to take on this question? May 12 '13 at 21:24

In elliptic curves there is no such simple mapping. One can't use decomposition into prime divisors, as in hyperelliptic curves, since every point is a prime divisor. One possible solution, as you have pointed out, is to try to lift the elliptic curve into $E(\mathbb{Q})$ or $E(\mathbb{Q}_p)$; this approach is full of obstructions, however, and has proven not to be very productive yet. The survey by Joe Silverman explains some reasons why.