Recently on MathOverflow the following question was asked: “.   What is x and how do you find x?”  This question was soon closed as being inappropriate for MO.  In fact it is a very interesting question.

The general question is:  Solve (a, b, x, m all integers).  This is the discrete logarithm problem.  All known general algorithms for solving it run in exponential time.  It is used in cryptography, for example in the RSA algorithm and the Diffie-Hellman algorithm.

For example, the RSA algorithm is implement in this way:  Find two very large primes p and q.  This can be done in polynomial time.  Let .  Find integers d and e relatively prime to such that ; this can also be done efficiently.  Note that for any integer a, .  You make m and e public but keep d, p and q private.  Then someone else can encode a message as an integer a and transmit (which can be calculated pretty fast)  to you.  Since you know the logarithm d you can decode it by calculating .   (What if the message is too long?  Details, details…)

The fact that you can find large primes fast but you can’t find discrete logarithms fast means that this method is safe.  The fact that no one can prove you can’t find discrete logarithms fast means cryptographers worry about this a lot.

Send to Kindle