Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
What is that reduction in one direction? –  Ilya Nikokoshev Nov 3 '09 at 15:01
add comment

4 Answers 4

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  Harrison Brown Nov 3 '09 at 17:17
2  
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. –  Steve Flammia Nov 3 '09 at 17:48
    
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... –  Harrison Brown Nov 4 '09 at 0:35
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
That's the basic idea of the reduction, except it becomes a bit messier in the general case. –  Harrison Brown Nov 3 '09 at 16:14
    
And it only works for composite N. AFAIK there is no known reduction of factoring to discrete log modulo primes. –  Emil Jeřábek Mar 9 '11 at 14:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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