2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Don't know, but it might not be a coincidence that the current best algorithms for both problems are of the same complexity. $\endgroup$ – joro Sep 10 '11 at 13:48
  • 1
    $\begingroup$ 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. $\endgroup$ – François G. Dorais Sep 10 '11 at 15:57
  • 1
    $\begingroup$ 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. $\endgroup$ – Henry Cohn Sep 10 '11 at 16:22
  • $\begingroup$ 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'... $\endgroup$ – François G. Dorais Sep 10 '11 at 16:35
  • $\begingroup$ @Francois: Assume you have a blazing fast factoring algorithm! I can edit my question. $\endgroup$ – user16007 Sep 10 '11 at 22:50
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I would be very interested to see a formal proof that "Nobody knows". Pwning m$ might give much more money than a paper "Factoring is efficient" $\endgroup$ – joro Sep 10 '11 at 17:06
  • $\begingroup$ Of course I can't rule out the possibility that someone knows but is keeping it secret (perhaps it's classified). What I meant is that I'm confident that nobody has published, or widely circulated, a polynomial-time reduction in either direction between factoring and finite-field discrete log. (Of course, as François pointed out, this is probably not what was being asked.) $\endgroup$ – Henry Cohn Sep 10 '11 at 18:03
  • $\begingroup$ Professor Cohn: Do you have any intuition what algebraic/algebraic geometric structures might you consider helpful to understand the relationship? $\endgroup$ – user16007 Sep 10 '11 at 23:05
  • $\begingroup$ In continuation: There are specific ideas in factoring such as representing numbers as sum of two different squares which help you factor. Are there any special forms of cyclic groups of prime order that the DL is doable provided we have another related information? $\endgroup$ – user16007 Sep 10 '11 at 23:29
  • $\begingroup$ @unknown IIRC the DL is tractable on anomalous elliptic curves. $\endgroup$ – joro Sep 11 '11 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.