From: chavey@beloit.edu (Darrah Chavey)
Newsgroups: sci.math
Subject: Re: discrete log complexity
Date: Thu, 17 Dec 1998 11:26:34 -0600

In article <755o3f$sd4$1@nntp1.uunet.ca>, jme@mycpu.org () wrote:
> hi
> 
> what is the complexity of the discret log computation ?
> in other words, i have y = g^x mod n with y,g,n known and i want x.
> 
> as far as i know, there is a part of the computation which doesnt depend
> on x. if so, how big is this part?

An algorithm of Shanks can solve the discrete log problem in time
sqrt(n). [Proc. of Symposia in Pure Mathematics, (20), 415-440, 1969].
An algorithm that runs in time O(lg N) can be found in Pomerance,
"Discrete Algorithms & Complexity" (ed. by D.S. Johnson), pp. 119-143,
1986.

Some additional information can be found in Bach & Shallit, "Algorithmic
Number Theory, Vol. 1", 1996, although they promise a full chapter on
the question in Vol. 2 which, as far as I know, is not available yet.

--Darrah Chavey         Department of Math & Computer Science
  chavey@beloit.edu     Beloit College; 700 College St; Beloit, Wisc.
  (608)-363-2220        http://www.beloit.edu/~chavey          53511

-- One tequila, two tequila, three tequila, floor.