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

1. For the Index Calculus applied to the Discrete Log Problem in Z_p*. I first thought that if we could find the isomorphism f:Z_p*-->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 $kf(alpha)=f(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 Z_p* is that for any primp, we have the isomorphism Z-->Z_p*, which allows us to write any element of 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 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(Q) to play the 'role' of the integers in certain special instances?

Thanks.

Tweet This+ 1 thisPost To Linkedin