Cryptographic challenge solved by two German scientists!

In 1989 I offered $100US for the solution of a problem in computational number and cryptography. At the time that I proposed it, I felt that it was unlikely to be solved in the near term, but I wanted to make it just beyond what was feasible at the time. This problem was recently solved by Damian Weber and Thomas Denny, using the number field sieve.

The problem was to solve a Diffie-Hellman problem modulo the prime p, where

p = 2*739*q+1, and q=(7149-1)/6.

I tell you that there exist integer x and y such that

7x = 127402180119973946824269244334322849749382042586931621654557735290322914679095998681860978813046595166455458144280588076766033781 (mod p)

7y = 180162285287453102444782834836799895015967046695346697313025121734059953772058475958176910625380692101651848662362137934026803049 (mod p)

The problem is to compute 7xy (mod p).

The solution provided by Weber and Denny is to supply x, which is:

It is interesting to consider what lessons can be learned from such an achievment:


Return to my home page

ps. The author claims an exemption from the minimum wage in offering this reward.