Discrete logarithm: Difference between revisions
From Polymath Wiki
Jump to navigationJump to search
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... |
No edit summary |
||
| 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 15: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]\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?)
