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)

Concerned the statement about difficulty is misleading[edit]

"Computing discrete logarithms is believed to be difficult. No efficient general method for computing discrete logarithms on conventional computers is known, and several important algorithms in public-key cryptography base their security on the assumption that the discrete logarithm problem has no efficient solution."

I'm concerned this is misleading. Is it believed that computing discrete logarithms in general is difficult or is computing discrete logarithms in (Z/pZ)* difficult? If we take our group to be (Z/pZ) [or however you'd like to show addition mod p over {0, ..., p-1}], then I believe we still have DLP as g=kp (since it is an additive group and not multiplicative) but it is not difficult to solve.

Perhaps it could be clarified whether the most general case is meant when saying that the DLP is difficult, and if it is meant to be said that the problem in general is difficult (as in, given any random finite group, I'd expect it to be difficult), then I'd be very interested in seeing a reference for that!

Or perhaps I am missing something important! — Preceding unsigned comment added by 166.175.57.92 (talk) 05:31, 20 September 2015 (UTC)

[1]

I think that the "in general" is implicit in "believed to be difficult". For example, in any setting computing logg g is trivially easy (the answer is 1). The statement about "believed to be difficult" is about the formulation of algorithms to solve the problem in general, not about the computation of any particular example.
If you feel strongly, then how about some mild wording change, such as "Except in simple special cases, computing discrete logarithms is believed to be difficult"? Mgnbar (talk) 13:33, 20 September 2015 (UTC)
I changed the statement a bit. The previous claim was indeed a bit misleading. For crypto one should indeed choose the groups carefully to avoid the special purpose algorithms listed further down on the article. 2A02:120B:2C71:9BD0:911B:9B03:D404:E791 (talk) 06:39, 21 September 2015 (UTC)
Today's edit to the Algorithms section attempts to address this complaint. Regards. Mgnbar (talk) 16:39, 22 January 2016 (UTC)
I came across your edit, claiming that the case for prime modulus p of b^k = g mod p is equivalent to bk = g mod p. This is clearly wrong, but perhaps you have something a bit more subtle in mind about why the prime modulus case is "easy". Hardmath (talk) 15:57, 18 July 2016 (UTC)
Hi. The edit did not say that these two equations were equivalent:
  • b^k = g (mod p) in the integers,
  • b k = g (mod p) in the integers.
That would be wrong, as you say. Rather, the edit said that Eq. 2 is an example of Eq. 1 below:
  1. b^k = g in an unspecified group G whose group operation is written as multiplication,
  2. b k = g (mod p) in the integers.
That is, you specialize to the case where (G, *) is (Z / pZ, + (mod p)). In other words, if abstract * concretely means +, then abstract ^ concretely means *. Does that make sense? Mgnbar (talk) 16:13, 18 July 2016 (UTC)
And to finish responding to your comment: Solving b k = g (mod p) is the trivial discrete log problem. Solving b^k = g (mod p) is nontrivial. Do we agree? Mgnbar (talk) 16:19, 18 July 2016 (UTC)

Easy in some groups[edit]

Is it worth mentioning in the article that the difficulty of the discrete logarithm problem depends on the group representation? For example, while discrete logarithms in modular multiplication groups are hard, discrete logarithms in modular addition groups are easy—calculating such discrete logarithms is simply the Extended Euclidean GCD algorithm. -- Myria (talk) 22:35, 10 December 2015 (UTC)

Those are different groups. You can argue that they are isomorphic to each other, but then the computational difficulty shifts to the computation of the isomorphism. Traditionally this article has not dealt with the easy cases, because the hard cases are more mathematically interesting and cryptographically useful. But I would not be opposed to a section on "Easy special cases" or something like that. Mgnbar (talk) 16:48, 11 December 2015 (UTC)
Today's edit to the Algorithms section attempts to address this complaint. Regards. Mgnbar (talk) 16:39, 22 January 2016 (UTC)

Name[edit]

Is this type of logarithm discrete of modular? Which name is more appropriate considering also the discrete ordinary logarithm such integer exponents of ten, for instance?--5.2.200.163 (talk) 15:17, 10 November 2016 (UTC)

First let's get this out of the way: Wikipedia doesn't decide what the terminology "should" be. It just uses whatever terminology already exists in the discipline.
Second, what is the meaning of modular logarithm? I have never heard that phrase. Does it mean a discrete logarithm in (Z / m Z)* for some m? This article is about all instances of the discrete logarithm --- including, but not limited to, those in (Z / m Z)*. Mgnbar (talk) 21:08, 10 November 2016 (UTC)
The term modular logarithm is the counterpart/opposite of the modular exponentiation (based on modular arithmetic (Z / m Z)). Modular logarithm is also a subset or special case of the discrete logarithm. The term modular logarithm is needed to avoid confusion between discrete logaritm and modular logarithm because there can be ordinary discrete (non-modular) logarithm which is not the counterpart of modular exponentiation. I′m sure the term modular logarithm can be found in some sources.--5.2.200.163 (talk) 13:01, 11 November 2016 (UTC)
Of course this article is about all instances of the discrete logarithm --- including, but not limited to, those in (Z / m Z)*, but the ordinary logaritms as discrete exponents of bases like 10 are not covered in article. The ordinary discrete logarithm does not necessarily involve group-theoretic frame.--5.2.200.163 (talk) 13:07, 11 November 2016 (UTC)
You seem to be talking about a third class of logarithm problem, beyond discrete logarithms and the special case of modular logarithms. Can you give a concrete example? Is it something like log10 10000 = 4? Because that is a discrete logarithm problem in the infinite cyclic group {..., 0.001, 0.01, 0.1, 1, 10, 100, 1000, ...} under multiplication. I am not opposed to mentioning this example in the article, but again it's just an example. You don't need to know group theory to understand it, but it can be phrased in terms of groups.
Really the distinction between discrete logarithms and "ordinary, real" logarithms in the real numbers is: Discrete logarithms are about integer exponents, which are definable in terms of products and inverses and thus definable in any group. Real logarithms are about real exponents, which are not an algebraic concept at all but rather a consequence of the miraculous exponential function. And in computing real logarithms it is understood that we are satisfied with an approximation rather than an exact answer.
Do you know what I mean? Am I missing your point? Mgnbar (talk) 14:22, 11 November 2016 (UTC)
The point is well adressed. The example you mention with exponent 4 is appropriate. What is somewhat surprising is the labelling of it as a third class of logarithm problem. Of course it can be phrased in terms of groups as a more general conceptual frame based on math structures.--5.2.200.163 (talk) 11:56, 14 November 2016 (UTC)

I have just noticed the redirect discrete exponential function as the reverse of discrete logarithm. Modular exponentiation is a subset or special case of the discrete exponential function.--5.2.200.163 (talk) 16:15, 18 November 2016 (UTC)

Deleted: integers modulo p under addition[edit]

I deleted the following paragraph:

Efficient algorithms exist in certain special cases. For example, let G = Zp be the integers modulo p under addition. The abstract equation bk = g then amounts to
in ordinary arithmetic notation. The extended Euclidean algorithm finds k quickly.

I found this very confusing. I checked the talk page and now understand that in this "abstract equation", bk is not what we usually think of when we say "power". Such special cases are certainly of interest to mathematicians, but I think the paragraph should be rewritten to make this much clearer, or maybe moved to a different section. I would guess that most readers don't know what the "integers modulo p under addition" are. Chrisahn (talk) 19:23, 17 April 2017 (UTC)

It is an important and basic example, just as "integers modulo p under addition" is one of the most basic examples of a group. We have to write for the most likely audience, which is not everybody who speaks English, but more like people who know basic group theory. Mgnbar (talk) 21:51, 17 April 2017 (UTC)
"We have to write for the most likely audience". Even if that had been true, if you compare the small number of people who know "basic group theory" compared to the billions of other potential readers, do you seriously believe that the "people who know" outnumber the laymen on this page? Mlewan (talk) 05:12, 18 April 2017 (UTC)
"Even if that had been true...": It is true. It is a Wikipedia policy, stated in the "nutshell" summary at Wikipedia:Make technical articles understandable. And if a reader doesn't know what a group is, then why is that reader interested in this particular problem about groups?
To answer my own question: A reader might be interested because they have heard that this problem is important to cryptography. But the example in question is not cryptographically relevant, because an efficient algorithm exists for it.
I think I do know basic group theory: I know what an operation is, a neutral element, inverse elements, and a few other things. But I still found the paragraph confusing, because it wasn't obvious to me that the syntax we usually use for multiplication and exponentiation means addition and multiplication, respectively, in the integers modulo p under addition. If that was made clearer, the paragraph would be fine. But as it is, I'm pretty sure it will confuse most readers. I acknowledge that mathematicians may be looking for more in-depth information, but I think we should balance the needs of mathematicians and other readers. Chrisahn (talk) 17:21, 18 April 2017 (UTC)
This syntax issue is the kind of thing typically covered in the first hour of an introductory course in group theory. But, okay, I have added a parenthetical explanation to the article. Is it sufficient? Is it too much? Mgnbar (talk) 21:05, 18 April 2017 (UTC)
Thanks! I think the new explanation is better, but maybe a little long. I shortened it, hopefully keeping its content intact. But I'm not a mathematician, so please check if my wording is correct.
I also moved it to the end of the section. I think I partly found these sentences confusing because they appeared at the start of the section, which seemed to imply that they're important, but they're really just mentioning a special case in which a "logarithm" isn't a logarithm in the common sense. Chrisahn (talk) 22:03, 30 April 2017 (UTC)
It appeared at the start of the section for two reasons. First, integers modulo p is one of the most basic examples. Second, it's classical, not quantum (which is in danger of receiving undue weight in this article). But okay. But I've removed some redundancy and tweaked the text to make sense relative to the preceding paragraph. Let us know if there is a problem. Mgnbar (talk) 00:25, 1 May 2017 (UTC)

finite group in first sentence, infinite group in first example[edit]

The first sentence currently reads: "In mathematics, a discrete logarithm is an integer k exponent solving the equation bk = g, where b and g are elements of a finite group" (emphasis added), but an example in the first section is based on an infinte group of powers of 10. Is the first sentence wrong? Should we drop or change the word "finite"? Or is the example somewhat misleading? Chrisahn (talk) 20:19, 11 May 2017 (UTC)

The opening sentence should not include the word "finite". Neither should the second sentence. Please remove those two occurrences. Thanks for noticing. Mgnbar (talk) 22:05, 11 May 2017 (UTC)