Difference between revisions of "Discrete logarithm"
From Polymath1Wiki
(New page: The discrete logarithm problem is this: given a prime p, a generator g, and another nonzero residue class a mod p, find an integer n such that <math>g^n = a \hbox{ mod } p</math>. This p...) 
(No difference)

Revision as of 11:57, 8 August 2009
The discrete logarithm problem is this: given a prime p, a generator g, and another nonzero 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. DiffieHellman.
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?)