Talk:Discrete logarithm

P is 7?

This article could use a -little- more explaination, or at least an easy to follow (more laymans) example. For instance, in the existing example is p supposed to be 7? (I would fix it myself, but IANAMW [I am not a math wiz]).

C needs to be explained further

{0,1,...,p-1}

I think (Z_p)^× is {0,1, …, p − 1}, not {1, …, p − 1}

No, it isn't Z_p is {0..p-1} (additive group), but (Z_p)^× is {1..p-1}, without zero (multiplicative group -- that × in the exponent connotes multiplication). Veky 09:30, 10 January 2006 (UTC)

Quantum Computing

Should we add a few sentences about quantum computing and Shor's efficient quantum solution of the discrete log problem? WindowMaker 22:24, 18 April 2006 (UTC)

Sure; please do. I'm not familiar with it. If it's a modification of Shor's algorithm for factoring, perhaps it would be best treated there, and just cited here? Joshua Davis 00:34, 19 April 2006 (UTC)

Typo?

"This algorithm requires running time linear in the size of the group G and thus exponential in the number of digits in the size of the group"

Other way 'round. No?

No, I don't think so. If the size of the group is 256, then the algorithm takes (proportional to) 256 steps, so an exponential number of steps in log 256 = 8, the number of bits needed to represent 256. (I'm using base 2 for exponentials and logs.) Make sense? Joshua Davis 13:09, 1 November 2006 (UTC)

Integer Factorization

Hasn't it been proven that calculating discrete logarithms is Turing equivalent to integer factorization (i.e., a polynomial-time algorithm for one implies the existence of a polynomial-time algorithm to solve the other?) —Preceding unsigned comment added by 24.254.224.181 (talk) 22:25, 4 January 2008 (UTC)

Nevermind, I was wrong. There are some obstacles to showing this, or at least that's what I've read. Simphilip (talk) 02:50, 5 January 2008 (UTC)

If an (odd) integer n=a*b has exactly 2 factors, a=2k+1, b=2x+1 then factoring that integer is equivalent to compute a discrete logarithm in s=k+x from the equation c^s=(n-1)/2. If we would have an efficient algorithm to compute discrete logarithms then we could efficiently factorize any number that have exactly 2 factors. I don't know any generalization of this for numbers with more factors. Are the two problems really equivalent? (it seems so, but is there any proof somewhere?)

Error in example?

I think the last "4" in the sentence "Since 3¹⁶ ≡ 1 (mod 17) it also follows that if n is an integer then 3^{4+16 n} ≡ 13 x 1ⁿ ≡ 4 (mod 17)." should be "13". So the sentence should read "Since 3¹⁶ ≡ 1 (mod 17) it also follows that if n is an integer then 3^{4+16 n} ≡ 13 x 1ⁿ ≡ 13 (mod 17)." Anyone disagree?

Greg McFarlane (talk) 05:55, 30 April 2008 (UTC)

Agreed. It should be correct now. 85.2.113.214 (talk) 06:04, 30 April 2008 (UTC)

Worst case

"Computing discrete logarithms is apparently difficult. Not only is no efficient algorithm known for the worst case, but the average-case complexity can be shown to be at least as hard as the worst case using random self-reducibility."

"at least as"? It's not the worst case if the average case is worse. (VillemVillemVillem (talk) 19:34, 16 July 2010 (UTC))