Discrete logs vs. factoring - MathOverflow

Discrete logs vs. factoring

2009-11-03T11:21:14Z

One thing that I've never quite understood is why computing discrete logarithms (in the multiplicative group mod p) and factoring seem to be so closely related. I don't think that there's a reduction in either direction, at least when p is prime (although a quick literature search tells me that there's a probabilistic reduction in one direction), but there are a huge number of nontrivial similarities:

Neither of them are believed to have a classical polynomial-time algorithm, but essentially the same quantum algorithm works for both.
Both of them serve as an easy basis for public-key cryptography, while other problems (for instance, lattice-based problems) are much more difficult to turn into working cryptosystems, and some (graph isomorphism, computing the permanent) seem to have no hope whatsoever of being useful in crypto.
Many of the classical algorithms for one of them are closely related to a classical algorithm for the other -- number field sieve and function field sieve, Pollard's rhos, baby-step giant-step vs. Fermat-type methods, and so on.

Is there a simple reason why, even though in theory they aren't reducible to each other, in practice they behave as though they were?

Edit: To clarify further, as Rune points out, both factoring and discrete log can be seen as versions of the hidden subgroup problem over an abelian group. I understand why there are quantum algorithms for this, and some of the obstacles to quantum algorithms for nonabelian HSP, and even to a degree why HSP is good to base a public-key system around. My question is essentially why "they share a much closer bond that isn't seen with other abelian HSPs."

Answer by Steve Flammia for Discrete logs vs. factoring

2009-11-03T14:53:05Z

I think the reason is that the underlying group structure in both cases is that of an Abelian group. This is indeed why Shor's algorithm can be applied to both. Specifically, when you have access to an efficient "period-finding" subroutine (such as a quantum Fourier transform), then you can solve both problems.

Answer by Ilya Nikokoshev for Discrete logs vs. factoring

2009-11-03T15:03:01Z

Actually, they are directly related sometimes:

Suppose you have N = pq without knowing the decomposition. Now finding the order of (Z/NZ)^*, which is (p-1)(q-1), is equivalent to factorizing N.

Answer by Rune for Discrete logs vs. factoring

2009-11-04T00:07:17Z

Adding to Steve's answer: Both problems are special cases of the hidden subgroup problem over an abelian group. (Elliptic curve crypto also falls in the same category.)

We do have efficient quantum algorithms for solving the hidden subgroup problem over any abelian group. By "efficient" I mean it takes polynomially many queries AND has polynomial time complexity.

As for examples of non-abelian hidden subgroup problems: graph isomophism and certain lattice problems. We don't know how to solve these efficiently on a quantum computer. The WP article on quantum algorithms has more information and references.

Despite this similarity, factoring and discrete log share a much closer bond, which isn't seen with other abelian HSPs. I have no good explanation for that though.

Answer by David Mandell Freeman for Discrete logs vs. factoring

2010-07-29T22:01:47Z

Another relationship is that in both cases the fundamental structure is a ring of integers modulo some other integer m (prime or composite, as the case may be). In such a ring there are distinguished "small prime" elements, 2,3,5, etc. The reason that index calculus (and the Number Field Sieve, etc) works in both cases is that you can decompose (some) elements in the ring into these small prime elements, and then find relations between these decompositions.

On the other hand, on elliptic curves over (prime) finite fields there is no analogous "factor base," which is why the discrete log problem is so much harder in this case.

So I would say that the connection is not between discrete logs and factoring, but between the multiplicative group mod p and the multiplicative group mod N = pq.