Discrete logarithm

From Polymath Wiki
Revision as of 23:52, 19 August 2009 by Asdf (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

The discrete logarithm problem is this: given a prime p, a generator g, and another non-zero residue class a mod p, find an integer n such that [math]g^n = a \hbox{ mod } p[/math]. This problem is related to a number of cryptography systems, e.g. Diffie-Hellman.

The possibility was raised that if discrete logarithm was assumed to be hard, then some pseudorandom number generator might be constructed which could resolve the finding primes problem. But there is a basic difficulty here, which is that one needs to have a large prime in hand before one could solve this problem! (But perhaps one could use one large prime to find others by this method?)