26
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ What is that reduction in one direction? $\endgroup$
    – Ilya Nikokoshev
    Commented Nov 3, 2009 at 15:01

4 Answers 4

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So does Shor's algorithm break elliptic-curve crypto, too? I was under the impression that it didn't, but admittedly that's mostly just because I've never had anyone tell me that it did. $\endgroup$
    – Harrison Brown
    Commented Nov 3, 2009 at 17:17
  • 2
    $\begingroup$ Yes, the quantum Fourier transform can be employed to break elliptic curve crypto. As a rule of thumb (not a rigorous statement), anything that relies on abelian group structure is susceptible to a quantum attack. I say it's a rule of thumb because we don't know in general how to turn black box query algorithms into "real" quantum algorithms for all cases. But the raw black box algorithms are very powerful for any problem involving Abelian group structure, so if I were extremely paranoid, I would not trust any such crypto scheme. $\endgroup$
    – Steve Flammia
    Commented Nov 3, 2009 at 17:48
  • 1
    $\begingroup$ Hmm... I'm still a bit lost as to why classical algorithms tend to work nicely for both, though. For instance, the number field sieve (well, the rational sieve, which I actually understand) doesn't seem to be computing any sort of period... $\endgroup$
    – Harrison Brown
    Commented Nov 4, 2009 at 0:35
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That's the basic idea of the reduction, except it becomes a bit messier in the general case. $\endgroup$
    – Harrison Brown
    Commented Nov 3, 2009 at 16:14
  • $\begingroup$ And it only works for composite N. AFAIK there is no known reduction of factoring to discrete log modulo primes. $\endgroup$
    – Emil Jeřábek
    Commented Mar 9, 2011 at 14:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .