Discrete logarithm
From Polymath Wiki
Jump to navigationJump to 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]\displaystyle{ 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?)
