Open Problem Garden - Discrete Logarithm Problem - Comments

N != n (re: Discrete Logarithm Problem)

Anonymous — Mon, 25 Feb 2013 00:43:58 +0100

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

Discrete Logrithm is polynomial (re: Discrete Logarithm Problem)

Anonymous — Tue, 29 Dec 2009 20:14:55 +0100

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.

A polynomial algorithm (re: Discrete Logarithm Problem)

Anonymous — Tue, 29 Dec 2009 19:55:58 +0100

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

Discrete Logarithm Problem

cplxphil — Sat, 27 Sep 2008 23:51:50 +0200

Author(s):

Subject: Theoretical Comp. Sci. » Complexity

If is prime and , we write if satisfies . The problem of finding such an integer for a given (with ) is the Discrete Log Problem.

Conjecture There does not exist a polynomial time algorithm to solve the Discrete Log Problem.