# 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 non-zero residue class a mod p, find an integer n such that <math>g^n = a \hbox{ mod } p</math>. This p...) |
|||

Line 1: | Line 1: | ||

− | 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 '''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?) | 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?) | ||

− | * [ | + | * [[wikipedia:Discrete_logarithm|The wikipedia page on discrete logarithms]] |

## Latest revision as of 16:52, 19 August 2009

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?)