Discrete Logarithm Problem

Importance: High ✭✭✭
Keywords: discrete log
Recomm. for undergrads: no
Posted by: cplxphil
on: September 27th, 2008

If $p$ is prime and $g,h \in {\mathbb Z}_p^*$, we write $\log_g(h) = n$ if $n \in {\mathbb Z}$ satisfies $g^n = h$. The problem of finding such an integer $n$ for a given $g,h \in {\mathbb Z}^*_p$ (with $g \neq 1$) is the \emph{Discrete Log Problem}.

\begin{conjecture} There does not exist a polynomial time algorithm to solve the Discrete Log Problem. \end{conjecture}

The Discrete Logarithm Problem is a critical problem in number theory, and is similar in many ways to the integer factorization problem. If it were possible to compute discrete logs efficiently, it would be possible to break numerous thought-to-be unbreakable cryptographic schemes. However, although most mathematicians and computer scientists believe that the DLP is unsolvable, this conjecture is difficult to establish, because such a proof would imply that P != NP...which is the most difficult open problem in theoretical computer science.

Avi Wigderson has shown that there is no ``natural proof'' (in the sense of [RR]) that the DLP requires circuits of greater than half-exponential size. The key idea is that a natural proof that the DLP is hard would yield a method for breaking discrete-log-based cryptosystems, and this is a contradiction. Of course, it could still be that DLP is provably hard, but by a proof that is not ``natural.''


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries) [RR] Alexander A. Razborov and Steven Rudich, Natural proofs, Journal of Computer and System Sciences 55 (1997), 24–35.

* indicates original appearance(s) of problem.

Discrete Logrithm is polynomial

The discrete logarithm problem is little more than an integer analog to a rotor-code cipher problem. The later is a problem in finding concurrent zeros for two periodic functions where the periodicity of one tracks the value of x and the other the value of y. The value of x being x, x^2, x^3, ... x^n. The value of y being y, y+p, y+2p,..., y+np. These forms of problems are amenable to solution using a multi dimensional difference (recurrence) expression (as is the Elliptic Curve Cryptographic problem which is a direct application of DE over algebraic fields). The Discrete Logarithm problem is solvable by a deterministic polynomial time algorithm in O(n^3). Google a paper titled "Computing a Discrete Logarithm in O(n^3)", which can be found at Cornell's arXiv website. Example code for the algorithm is also provided by the author of that paper.

N != n

The above paper solves the discrete logarithm in time O(N^3) not O(n^3), two very different things. N being the size of the modulus, n being log_2 of N (the binary length). There are many algorithms that will solve the discrete log problem much faster than this method, brute force search runs at a worst case of O(N), or in other words O(2^n). The provided algorithm in the above paper runs in (2^(3*n)).

A polynomial algorithm

See the paper at http://arxiv1.library.cornell.edu/abs/0912.2269.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.