# Factoring and Index Calculus and duality between DL and factoring via compuational problems made easy through them

If factoring is in $P$ (with a blazing fast polynomial time in $P$), would it affect the 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.

• Don't know, but it might not be a coincidence that the current best algorithms for both problems are of the same complexity. – joro Sep 10 '11 at 13:48
• Note that the question is specifically about the index calculus algorithm, not the general discrete logarithm problem. I think the answer is 'no' since even if you have fast factoring (even just a fast algorithm conditional on numbers being smooth) you still have a bottleneck with the sparse matrix reduction. Of course, if you can really reduce the size of the factor base, then the bottleneck might move to the factoring part and a fast factoring algorithm might really help. – François G. Dorais Sep 10 '11 at 15:57
• Hmm, good point. I think you're right that the answer is 'no'. In principle, a fast enough factoring algorithm would speed up the relation gathering stage, but that part is easy to parallelize anyway (unlike the linear algebra at the end). Ultimately, the real trade-off is between the size of the factor base and the probability that a random number will factor over it, and speeding up the process of checking whether it does won't improve that trade-off. – Henry Cohn Sep 10 '11 at 16:22
• Also, if you have a really small factor base, then plain trial division is already pretty fast. So you would need a blazing fast general factoring algorithm to make a serious improvement. I'm pretty sure the answer is definitely 'no'... – François G. Dorais Sep 10 '11 at 16:35
• @Francois: Assume you have a blazing fast factoring algorithm! I can edit my question. – user16007 Sep 10 '11 at 22:50

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).