Talk:Discrete logarithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Importance
 Field: Algebra
WikiProject Cryptography / Computer science  (Rated Start-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the quality scale.
 Mid  This article has been rated as Mid-importance on the importance scale.
Taskforce icon
This article is supported by WikiProject Computer science (marked as Mid-importance).
 

P is 7?[edit]

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}[edit]

I think (Zp)× 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[edit]

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?[edit]

"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[edit]

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 has exactly 2 factors, then factoring that integer is equivalent to compute a discrete logarithm of c^((n-1)/2), for a random c. 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?) — Preceding unsigned comment added by LaurV (talkcontribs) 02:15, 19 August 2011 (UTC)

You might try your question at Wikipedia:Reference desk/Mathematics. Mgnbar (talk) 03:39, 19 August 2011 (UTC)

Error in example?[edit]

I think the last "4" in the sentence "Since 316 ≡ 1 (mod 17) it also follows that if n is an integer then 34+16 n ≡ 13 x 1n ≡ 4 (mod 17)." should be "13". So the sentence should read "Since 316 ≡ 1 (mod 17) it also follows that if n is an integer then 34+16 n ≡ 13 x 1n ≡ 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[edit]

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

"S/He didn't say worse. Said 'at least as'. When the worst case is as bad as the average case doesn't that also make it the best case? That is, all cases are just as good/bad? (Gaelhalee (talk) 17:17, 9 April 2012 (UTC))

"Too technical"[edit]

A "too technical" tag was just placed on this article, saying that the presentation is too difficult for an elementary concept. The concept is not really elementary, in that the non-mathematical layperson will never encounter it. It's typically studied at the advanced undergraduate level, in courses in abstract algebra and cryptography. The treatment here seems appropriate to me. In fact, the article seems to do a good job of relating discrete logs to ordinary logs in the real numbers. So I vote against the tag. Mgnbar (talk) 11:53, 14 August 2013 (UTC)

I generally agree, though the lede could be a little less jargony. Before i edit it, I noticed it refers to finite cyclic groups. That restriction can't be right or am I missing something? --agr (talk) 15:25, 14 August 2013 (UTC)
I think that it was added in an attempt to make the logarithm always unique and well-defined. But it doesn't succeed, and infinite cyclic groups behave just as well as finite cyclic groups with respect to this issue. My vote is that we remove "finite cyclic", just defining logs in arbitrary groups, but that we also make clear that logs do not always exist and may not always be unique. Mgnbar (talk) 15:42, 14 August 2013 (UTC)
I'll go with all the above. I'm no expert, but is this concept not defined for any group? (Obviously with non-uniqueness, but then this is also the case for finite groups: they are periodic). Should we not also change "is a solution" in the lead to "is an integer solution"? After all, there are contexts in which non-integers make sense, or might seem to make sense. — Quondum 11:54, 15 August 2013 (UTC)
I've made the changes. I've also tried to make the notation more consistent. Mgnbar (talk) 12:35, 15 August 2013 (UTC)

New (May 2014) algorithm and its impact on crypto?[edit]

An improved algorithm for computing discrete logarithms was published just now (mid-May 2014). See this article in Science Daily. The paper itself is available here via Springer Link (subscription required). The issue has been mentioned on Bruce Schneier's blog (see here), and it's also being talked about on Slashdot (see here), but I haven't found any reliable sources yet listing any specific crypto systems that are no longer secure as a result. People should probably keep an eye on this and see how it develops. — Richwales (no relation to Jimbo) 02:34, 19 May 2014 (UTC)