If factoring is in $P$ (with a blazing fast polynomial time in $P$), would it affect the [index calculus algorithm](http://en.wikipedia.org/wiki/Index_calculus_algorithm) used for Discrete Log calculation in any serious way?


**Other connections**


$1.)$ "Number field cryptography" Johannes Buchmann Tsuyoshi Takagi Ulrich Vollmer


The above paper mentions Root Problem (RP) and Group Order Problem (GOP) is same as factoring discriminant. So factoring easy implies RP and GOP are easy.


$2.)$ "A Signature Scheme Based on the Intractability of Computing Roots" Ingrid Biehl Johannes Buchmann Safuat Hamdy Andreas Meyer


The above paper mentions if DL is easy, Group Order Problem (GOP) is easy which inturn would imply Root Problem (RP) would be easy. So DL is easy implies RP and GOP are easy.


Though unrelated to index calculus directly, could any of these links be used to show index calculus for DL could be done faster than $O(\sqrt{P})$ if factorization is quick? 


There seems to be some kind of duality between DL and factoring since both lead to easy solutions for RP and GOP.



Factoring and Index Calculus and duality between DL and factoring via compuational problems made easy through them
Nobody knows. It's striking that the best algorithms for factoring and finite field discrete log are so closely analogous, and it hints at a deeper relationship between the problems (as joro pointed out in the comments), but no efficient reduction is known in either direction. In particular, it might just be a coincidence that the few good ideas so far happen to apply to both problems, in which case a new factoring algorithm might shed little light on discrete log. However, if factoring turned out to be doable, then nobody would have any faith in the difficulty of the discrete log problem, even if the new algorithm didn't seem to apply.


Incidentally, there is a reduction in the other direction for a slightly more general problem: factoring $n$ can be reduced to computing discrete logs in $\mathbb{Z}/n\mathbb{Z}$. This is due to Eric Bach (<http://www.eecs.berkeley.edu/Pubs/TechRpts/1984/5973.html>). It starts with a known reduction from factoring to computing a multiple of the order of a unit mod $n$. In other words, the problem of computing for a given unit $a$ mod $n$ a positive exponent $e$ such that $a^e \equiv 1 \pmod{n}$. Now, given a unit $a$ mod $n$ and a prime $p$ not dividing $\varphi(n)$, let $b = a^p$. We can find $x$ such that $b^x \equiv a \pmod{n}$ by solving the discrete log problem mod $n$, and then $a^{px-1} \equiv 1 \pmod{n}$. Of course, to do this we need a prime $p$ not dividing $\varphi(n)$, and we won't know $\varphi(n)$. However, we will only need to try a logarithmic number of small primes before we hit one that works (because $\varphi(n)$ can't have more than $\log\_2 n$ prime factors).


