Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Ok I have a few questions that hopefully some people can answer:

  1. For the Index Calculus applied to the Discrete Log Problem in $\mathbb{Z}_p^*$. I first thought that if we could find the isomorphism $\mathbb{Z}_p^*\overset{\phi}{\rightarrow}\mathbb{Z}_{p-1}$ in polynomial time, then we could crack the Discrete Log Problem.

    But now I've decided that that's probably not true, because all that would do would be to change the problem from finding the $a$ such that $\alpha^a=\beta$ mod p, to finding the $k$ such that $k\phi(\alpha)=\phi(\beta)$ mod $p-1$, and I wasn't under the impression multiplication was significantly more costly than addition. Can someone confirm or deny my position on this?

  2. My understanding is that the great advantage of the Index Calculus applied to the Discrete Log Problem over $\mathbb{Z}_p^*$ is that for any prime $p$, we have the isomorphism $\mathbb{Z}^{\times}\rightarrow\mathbb{Z}_p^*$, which allows us to write any element of $\mathbb{Z}_p^*$ unambiguously in terms of its prime factorization.

    And thus since it's not prohibitively difficult to find integers which factor into just a few small (and thus frequently occurring) primes, this common representation among various elements in $\mathbb{Z}_p^*$ provides us with a powerful technique for cracking the Discrete Log Problem.

    My question is, is it this lack of an analogue of the integers when applying the Discrete Log Problem in the elliptic curve setting which prevents us from employing the Index Calculus effectively? Intuitively, its failure results from the fact that there's no obvious way to factor points on a curve in the same way we factor integers.

  3. I also want to clarify that the Index Calculus' success in certain cases comes from getting the elliptic curve $E(\mathbb{Q})$ to play the 'role' of the integers in certain special instances?


share|cite|improve this question
Is no one man enough to take on this question? – esproff May 12 '13 at 21:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.