This  level-5 vital article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Mid‑priority 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.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated as Mid-priority on the project's priority scale. Cryptography: Computer science Mid‑importance 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.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography Mid This article has been rated as Mid-importance on the importance scale. This article is supported by WikiProject Computer science (assessed as Mid-importance).

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

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)[reply]

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)[reply]

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)[reply]

"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)[reply]

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)[reply]

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)[reply]

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 (talk • contribs) 02:15, 19 August 2011 (UTC)[reply]

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

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)[reply]

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

"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))[reply]

"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))[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

I've made the changes. I've also tried to make the notation more consistent. Mgnbar (talk) 12:35, 15 August 2013 (UTC)[reply]

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)[reply]

"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)[reply]

^[1]

I think that the "in general" is implicit in "believed to be difficult". For example, in any setting computing log_g 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)[reply]

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)[reply]

Today's edit to the Algorithms section attempts to address this complaint. Regards. Mgnbar (talk) 16:39, 22 January 2016 (UTC)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Today's edit to the Algorithms section attempts to address this complaint. Regards. Mgnbar (talk) 16:39, 22 January 2016 (UTC)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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 log₁₀ 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)[reply]

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)[reply]

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)[reply]

A link with modular logarithm name (a link I should have inserted earlier): http://cs.brown.edu/courses/cs007/oneway/node2.html --5.2.200.163 (talk) 13:54, 30 August 2017 (UTC)[reply]

Re non-integer exponents it seems that concepts like modular square root include non-integer (rational or fractional)exponents which thus can appear also in modular discrete logarithms. Thus the ordinary miraculous exponential function is not so miraculous. It can also admit discrete fractional exponents which are involved in the approximation of real irrationals by rational numbers powers.--5.2.200.163 (talk) 12:20, 30 August 2017 (UTC)[reply]

(I moved the preceding comment to a new section.) Yes, square roots involve non-integer exponents. But they are not an example of discrete logarithms. I mean, solving x^2 = g is different problem than solving b^x = g (for x, given g and b).

Whether or not you're a fan of the exponential function, perhaps we agree that the "hard part" is the transition from rational to real, not the transition from integer to rational. Mgnbar (talk) 13:31, 30 August 2017 (UTC)[reply]

(I think this new block of comments should be perhaps a new subsection of where it originates or moved to the bottom of the page as a new section to keep the cronology.)--5.2.200.163 (talk) 13:50, 30 August 2017 (UTC)[reply]

Done. Mgnbar (talk) 14:59, 30 August 2017 (UTC)[reply]

It would be interesting to analyze and see an example of modular (discrete) logarithm involving a fractional exponent, if it can be formulated.--5.2.200.163 (talk) 13:58, 30 August 2017 (UTC)[reply]

Do you mean something like defining x^(1 / 2) to be b^(1 / 2 * log_b x), which holds for real logarithms? And then, for example, 13^(1 / 2) = 9 (mod 17)? I see a few issues. First, it's more common in algebra to simply define square roots as anything that squares to the given number — not to go through logarithms and exponentials. Second, I'm not sure what properties this definition has, or whether any reliable source actually does it. Third, I'm worried that adding a bunch of non-logarithm material will confuse readers. (In my experience, which might not be representative of the whole world, people have trouble understanding the distinction between x^2 and 2^x.) Mgnbar (talk) 14:59, 30 August 2017 (UTC)[reply]

The exponential notation in general introduced by Michael Stifel and in particular (for roots as powers with fractional exponents) has been a great progres in mathematical notation allowing advantages for doing operations. Squaring or cubing roots of certain number as examples to give that number follows from the properties of the exponents as 1/2*2=1 (1/2 +1/2 = 1) or 1/3*3 = 1 (1/3 + 1/3 + 1/3 = 1). About the effort required for understanding the distinction between power function and exponential function (x^2 and 2^x), surely this is an effort required to readers of technical articles and wikipedia articles with these topics can help in this direction by mentioning all the necessary details.--5.2.200.163 (talk) 13:57, 11 September 2017 (UTC)[reply]

Your point about effort is fair, but I still don't understand what you want to do to the article. Mgnbar (talk) 16:51, 11 September 2017 (UTC)[reply]

I think it is necessary that article specify details about the possibility of modular discrete logarithms with fractional exponents. This possibility is a real one due to the existence of modular exponentiation with fractional exponent like modular square root, modular cube root and so on. There are some details to be clarified.--5.2.200.163 (talk) 11:54, 12 September 2017 (UTC)[reply]

Powers in an abstract group use only integer exponents. Therefore discrete logarithms are integer-valued, as the article explains. You are talking about something other than discrete logarithms. Maybe you are looking for something like Quadratic reciprocity? Mgnbar (talk) 15:21, 12 September 2017 (UTC)[reply]

Hmm. If the solution to b^k = g is k = 1 / 2, then it's not that g is in the subgroup generated by b, but rather that b is in the subgroup generated by g. So the discrete log problem has been posed "backwards".

More generally, if the solution to b^k = g is k = n / d for integers n and d, then bⁿ = g^d? So we have to solve two coupled discrete log problems?

I've never seen this complication treated in the literature. But then I'm not an expert. Mgnbar (talk) 21:33, 12 September 2017 (UTC)[reply]

Interesting to analyse these aspects. Perhaps that could be done by involving other editors in this discussion, especially professional mathematicians by ping-ing them here or by opening a discussion at WikiProject Math talk page.--5.2.200.163 (talk) 16:20, 13 September 2017 (UTC)[reply]

About the use of only integer exponents in abstract group exponentiation, perhaps some enlargement of the frame could be considered, similar to that of fractional derivative or fractional derivative differential operators in the frame of mathematical structures.--5.2.200.163 (talk) 16:28, 13 September 2017 (UTC)[reply]

You are welcome to raise the issue at Wikipedia talk:WikiProject Mathematics. I would like to see at least one Wikipedia:Reliable source before I invest more effort into this topic. Mgnbar (talk) 19:22, 13 September 2017 (UTC)[reply]

I deleted the following paragraph:

Efficient algorithms exist in certain special cases. For example, let G = Z_p be the integers modulo p under addition. The abstract equation b^k = 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", b^k 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)[reply]

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)[reply]

"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)[reply]

"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)[reply]

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)[reply]

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)[reply]

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)[reply]

The first sentence currently reads: "In mathematics, a discrete logarithm is an integer k exponent solving the equation b^k = 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)[reply]

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)[reply]

I notice that this type of logarithm lacks a notation encountered in the case of ordinary logaritms.--5.2.200.163 (talk) 16:26, 7 September 2017 (UTC)[reply]

And what notation is that? Ordinary logarithms are denoted log_b g, and so are discrete logarithms. Mgnbar (talk) 20:34, 7 September 2017 (UTC)[reply]

Perhaps something (like *,m(od) exponent or index) for distinction from ordinary logarithms. I have opened this section due to not noticing the ordinary-like notation in the introduction of the article.--5.2.200.163 (talk) 12:59, 11 September 2017 (UTC)[reply]

Not all discrete logarithms arise from modular arithmetic. So a notation involving "mod" does not apply in general. But I have added the notation to the introduction of the article (although the lack of uniqueness has not been discussed yet). Mgnbar (talk) 16:44, 11 September 2017 (UTC)[reply]

I have several objections to the new lede. Here are the two most important.

"b, not being the identity": Was this inserted in an attempt to avoid cases where discrete logarithms don't exist? Unfortunately it is inadequate. For example, in Z/12Z^*, log₁ 3 and log₂ 3 are equally valid (neither exists). This is an issue better left for later in the article --- currently in the Definition section.

"not necessarily connected with integers at all": This phrase should not be here. At this point in the article, there is no reason for the reader to think that G is related to the integers. It reads like an editor trying to deal with his/her own misconceptions.

Mgnbar (talk) 16:30, 1 October 2017 (UTC)[reply]

Excluding the identity was not targeted at non-existing logs, but at disallowing for an idempotent base, rather useless with discrete exponents. Second, I do not recall anymore if, and in case how long, I nourished misconceptions about discrete exponents, and it is certainly true that this remark is un-encyclopedic in a puristic view, but -from hands on experience- helps to get to grips in some supportive view, which -from hearsay- is desirable around here, especially in math articles. To be honest, I shortly considered giving a hint to the possibility of "exponentiation" referring to a repeated group operation, even if this is usually called "addition". Third, and most important, please, help yourself to a version, which suits your desires, I am not that much into this topic as to insist on any specific content, I just take the freedom of making suggestions. Happy editing. N.B.: Of course, you are also free to reinsert the removed template. Purgy (talk) 06:58, 2 October 2017 (UTC)[reply]

So I see two points of discussion here, for anyone who wants to discuss them:

1. Should b = 1 be excluded, because it is trivial and boring? I do not think that it should be excluded, because I've never seen it excluded in any source and there is no logical reason to exclude it. But its triviality is probably worth a remark, but not in the lede, I think.
2. Should the lede drop readers directly into the setting of an abstract group? How can we soften that landing? That is always a good question in Wikipedia math articles.

Mgnbar (talk) 13:32, 8 October 2017 (UTC)[reply]

I have added a remark about b = 1 to the Definition section. Mgnbar (talk) 13:44, 8 October 2017 (UTC)[reply]

Even when this might transgress the two points conceded for discussion:

On one hand this article tries to tie up its theme of "discrete logarithm" with the generally well known notion of an integer exponent n in an environment of positive real numbers g and b≠1 by referring to the equation with obviously also well known meaning; on the other hand, it introduces a group with an inherently abstract binary operation, acting on group elements b and b or g. While I think it is easy to attach some association with the exponential equation by poor men's exponentiation (repeated multiplication), I also believe that a good deal of considerate readers (I do not expect many sages of group theory for this article) might hesitate at connecting integers with arbitrary group elements, especially, when the group, which comes to the readers mind, by chance, has an operation of additive style, which would correctly suggest a notation like for the same question, implying "quotient" instead of "logarithm". Obviously to me, it is necessary to be explicit about the exact meaning of the "exponential" notation in this context. Furthermore, in group theory, the exponential notation is also readily used for the right conjugation of group elements, possibly misleading another group (sic!) within the readership.

Here, the "discrete "exponentiation"" is imho no true exponentiation, it is just a simple shorthand for the repeating of an arbitrary operation (satisfying some associativity), not necessarily requiring a full group structure. These specifics should be made as such available to the reader in a clean manner, so that the notion of the "discrete "logarithm"" (note the double scare quotes around exponentiation and logarithm) can be safely introduced. Neither of these discrete "relations" is imho intimately connected to the full blown exponential and logarithmic functions within the realm of the real/complex numbers, but only loosely to a "repeated multiplication" of numbers.

The whole "group"-environment appears to me as owed only to the allusions to modulo-arithmetic, to the selected examples and, most prominently, to the whole article being quite targeted at cryptography with its "dl-problem"; and I think that the term discrete logarithm is not widely used within group theory, at all. Purgy (talk) 06:51, 11 October 2017 (UTC)[reply]

I have added an explicit explanation of the b^k notation to the Definition section. Is it adequate?

Currently, all of the explicit examples use the real numbers or modular arithmetic. Maybe the abstract definition would be better motivated if we included a genuinely different example? I'm thinking of the discrete logarithm problem in the group of points on an elliptic curve. This example is also highly relevant to cryptography. Mgnbar (talk) 13:53, 11 October 2017 (UTC)[reply]

Concretely, I propose:

1. We rename the Examples section to something like "Analogy with real logarithms". We keep the real examples there, but remove the (Z_p)^* example.
2. We remove the b = 1 example from the Definition section.
3. After the Definition section, we insert a new Examples section, with these four examples: b = 1 in an arbitrary group, (Z_p)^*, Z_p under addition, and the group of points on an elliptic curve.
4. In the Algorithms section, we can then shorten/improve the treatment of Z_p under addition.

Mgnbar (talk) 14:24, 11 October 2017 (UTC)[reply]

I consider the recent referrals "per talk page" in edit summaries as inappropriate, insofar they insinuate consensus. Just for the records, I disagree to certain uncritical, careless reverting edits, hinting to usurped ownership, possible evoked by my announcement not to interfere any further with this article. Purgy (talk) 06:47, 6 October 2017 (UTC)[reply]

I apologize for over-stating consensus or suggesting ownership. You might have misinterpreted my intent, because I was largely responding to editors other than you. Let me be more specific about the two edits in question:

1. The first edit largely reverted your lede edit, but leaving in the "whose group operation is denoted as multiplication" part. I viewed this clause as a good compromise, because the issue of multiplicative notation has been a sticking point in Talk:Discrete logarithm#Deleted: integers modulo p under addition and the main sticking point (?) in Talk:Discrete logarithm#New lede.
2. The second edit was in response to a complaint, particularly in Talk:Discrete logarithm#Non-integer rational powers, about the emphasis on the exponential function.

If my edit summaries had cited these specific talk page sections, would they have been adequate? I'm honestly asking. Mgnbar (talk) 17:08, 6 October 2017 (UTC)[reply]

Given my relatively low level of interest in this article, why should I discuss your hypothetical meta-questions on ex post support for your "edit summaries" (not even the edits themselves!), experiencing you as strictly avoiding any discussion of arguments, even those opposing your most important on-topic opinions? I'm equally honestly asking.

Rebus sic stantibus, I continue not to care about any specific content in this article. Purgy (talk) 13:02, 7 October 2017 (UTC)[reply]

I don't understand. You seem to be accusing me of behaving badly and avoiding discussion of arguments that oppose my opinions. But when I try to engage with you, you declare that you don't actually care.

So I'll drop the entire discussion, until there is some clear sign that someone wants to discuss something. Have a nice day. Mgnbar (talk) 17:08, 7 October 2017 (UTC)[reply]

You force me to emphasize that I did not accuse you of anything, and especially not of behaving badly, not even of avoiding discussion. You may check that I experienced your behaviour as the latter, and, yes, you can also check that you still did not reply to my arguments against your objections. Your efforts to "engage" with me started with "two most important objections" among "several" others, continued with ignoring my arguments against your POV, culminated in almost fully reverting with an imho inappropriate referral to "per talk page", and finishes now with asking about some cosmetics for edit summaries and blaming me for a fictitious accusation of bad behaviour. Maybe, these are figments.

You are still free to start to argue about my on-topic argumentation, or to simply continue any further edits to your liking, but I will not accept you unsubstantiatedly charging me without protest, and will hold myself free to engage in any discussion at my discretion. Purgy (talk) 08:24, 8 October 2017 (UTC)[reply]

I think I understand better now. You do not want to continue this talk page section, which you created to discuss my edit summaries. But you are unsatisfied with how I have addressed your substantive objections in the section Talk:Discrete logarithm#New lede. I'll return there as soon as I have time. Mgnbar (talk) 13:11, 8 October 2017 (UTC)[reply]

I am afraid I cannot contribute in a substantial way to this article. Just throwing in my 2 cents on the question and the suggestions from above:

1. I think there is no good analogy to "real logarithm" at all. Establishing an isomorphism between a multiplicative group and an additive group requires at least a ring structure. I see no chance to create a logarithm with a similarly broad meaning on the level of groups, and fields do not seem to be the target of "discrete logarithm" or cryptography. Having "Examples" before reasonably defining a notion, only supports sloppiness, by seducing to skip the details within the "Definition". The motivation for defining exactly this way should be in the lede, already, and good examples pinpoint the possible pitfalls in the definition.
2. Considering the many holes in the unique existence of discrete logs, I still cling to avoid early on, i.e. in the "Definition", some obvious holes by exclusion of the identity as a base, as is done for real logarithms. The current section "Definition" goes -to my taste- beyond a definition by discussing also properties; and I would not call a specific form of the defining functional equation of a true(?) logarithm a "usual algebraic equation" -neither just usual, nor very algebraic, but mostly transcendental.
3. I do not object against examples from "elliptic curves", since they are(?) important in cryptography, but I think they are just another group and do not add much to discrete logarithms themselves, besides requiring a non-trivial introduction.
4. To be honest, the "Algorithm" section is beyond me. I seriously doubt the claim "The discrete logarithm problem is considered to be computationally intractable." in this unspecified form. To me it is obviously the case that the Euclidean algorithm is tractable and provides a solution for the usual additive group. Afaik, it is the decompositions of products of large primes, which is computationally hard, but I can give no encyclopedic content on this. It seems to depend on the group operation under consideration (functional equation?) if the dl-problem is hard, and also on the available parallelism (P. Shor). I cannot judge the other content of this section, and I do not know if the article is intended to focus on the dl-problem, or on the dl itself.

All the best. Purgy (talk) 07:34, 13 October 2017 (UTC)[reply]

Thanks for your comments. Whether or not you continue with this article, I'll respond here, in case other editors are interested in the discussion.

About 3: I agree that elliptic curves won't solve the problem of providing a gentle introduction to discrete logs, even if they are a practically important example.

About 2: I agree that the current Definition section goes beyond definition into properties and even an example. It should be cleaned up. I'm not sure what you mean about transcendental operations. For integer k, the power b^k can be defined in a purely algebraic way without reference to anything transcendental.

About 2: I do not think that the definition should exclude b = 1, because reliable sources don't make that exclusion. Also, there is no clear mathematical reason for doing so (because it avoids only a tiny sliver of the ill-definedness).

About 1: The real examples given are accessible and authentic examples of the discrete logarithm problem, so we should keep them. No ring structure is required, because we are not assuming a single set with addition and multiplication. Rather, we are assuming two separate groups, whose operations happen to be denoted differently.

About 1: I like examples before definition, because the education literature suggests that this is an effective way of teaching. But Wikipedia is not a textbook, and if other editors feel strongly that the definition should come first, then I'll go along.

About 4: Yes, certain special cases of the discrete logarithm problem are tractable. But there is no fast classical algorithm for solving the problem in general --- meaning, all instances of the problem. I think that the Algorithms section already explains this well, but I'm open to improvements of course. Mgnbar (talk) 15:49, 15 October 2017 (UTC)[reply]

We refer to different meanings of "algebraic".

I do not see excluding the identity as referring to a "tiny sliver", but to a fundamentally meaningless chunk wrt to the notion of a "logarithm", akin to the "real logarithm".

The main problem is, imho, that there is no reasonably sharp definition of what is targeted by the notion "discrete logarithm", and is referred to in the applications. There is only a hint to some notation, optically reminding the observant reader of the foundations of the "real logarithm". I see no meaningful target in defining "dl"s for all possible operations in groups.

I cling to the opinion that it does not suffice to establish just a "multiplicative notation" in an arbitrary group to derive a suitable "dl" for the intended tasks (see above). For a useful "logarithmic" behaviour there must be some isomorphism (logarithm—exponential) between two groups (and their ops), and this is where the ring comes in.

I consider the fact that there is no "algorithm for solving the problem in general" as a hint to the problem not being sufficiently chiseled out (I do accept the vague "classical"). Furthermore, it's not about solvability, but about complexity; and obviously, the problems, only vaguely fenced in, are not within the same complexity class.

Never mind. Purgy (talk) 08:30, 16 October 2017 (UTC)[reply]

Perhaps the fundamental ongoing problem is the lack of citations. Here is a reliable source that is typical in my experience:

If G is a finite group, b is an element of G, and y is an element of G which is a power of b, then the discrete logarithm of y to the base b is any integer x such that b^x = y (Koblitz, A Course in Number Theory and Cryptography, p. 98).

Koblitz then goes on to give examples where G is the non-zero elements of a finite field. Later in the book, he does the example of an elliptic curve over a finite field, switching from multiplicative to additive notation. I think that he focuses on finite groups G because they are most relevant to his cryptographic agenda. Notice that his definition dodges the issue of non-existence but embraces the issue of non-uniqueness.

So I don't understand objections that the discrete log problem lacks a sharp definition. The definition given in this Wikipedia article is unambiguous and pretty representative of the literature. Mgnbar (talk) 14:56, 16 October 2017 (UTC)[reply]

... as well as multiplication is not repeated addition. I perceive the new emphasis on a far fetched analogy to the reals as mathematically inappropriate and not fruitful for the given theme, but rather confusing outside of modulo arithmetic. Without any further effects I just document my objections to the new lede. Purgy (talk) 16:10, 27 October 2017 (UTC)[reply]

It's good to register your objections. But b^k = b b ... b (k times) is standard notation in group theory --- so standard that Koblitz (referenced above) doesn't even bother to explain it (as far as I could tell). The Group (mathematics) article (admittedly not a reliable source) also uses it without explanation. Further, this notation is the origin of the inverse notation b^-1.

We should not focus solely on modular arithmetic, because the discrete logarithm problem has other important examples. And integer logarithms in the reals are a valid example --- with two advantages. First, the discrete logarithm notation log_b a is clearly modeled after the historically earlier real logarithm notation. Second, there is continually pressure to make Wikipedia math articles friendlier, and including an example from the real numbers seems like a friendly idea. Mgnbar (talk) 18:32, 27 October 2017 (UTC)[reply]

It's long overdue, but let's list what some reliable sources say about discrete logarithms.

• Graham Ellis, "Rings and Fields": Defines the problem in GF(p^k)^*. Does concrete example in GF(2^4)^*. Describes difficulty of general problem and cryptographic applications (p. 156).
• Neal Koblitz, "A Course in Number Theory and Cryptography", second edition: Draws an analogy with real logarithms. Defines the problem in an arbitrary finite group. Says, "the word 'discrete' distinguishes the finite group situation from the classical (continuous) situation". Mentions (Z/nZ)^* (n not specified) and GF(p^k)^* as examples. Does example in (Z/19Z)^*. Does example in GF(3^2)^*. Describes cryptographic applications. Discusses algorithms for GF(p^k)^* (p. 97-106). Exercises show that discrete logs help expedite computations in finite fields (p. 106-107) and that there is a polynomial time algorithm for (Z/pZ)^* where p is a Fermat prime (p. 109). Later, defines the problem in the group of points on an elliptic curve over GF(p^k). The group operation is written additively, so powers are written as multiples and logarithms look like divisions. Describes cryptographic algorithms (p. 180-185).
• Kenneth H. Rosen, "Elementary Number Theory and its Applications", third edition: Defines the problem in (Z/pZ)^*, where p is prime. Discusses algorithmic difficulty and cryptographic applications (p. 255).
• Adleman and Huang, "Function field sieve method for discrete logarithms over finite fields", Information and Computation 151 (1999): Defines the problem in GF(p^k)^*. Mentions intense research and cryptographic relevance. Relates discrete log algorithms to factoring algorithms. Discusses difficulty.
• MathWorld, Discrete logarithm article: Defines the problem in (Z/nZ)^*, where n is not necessarily prime. Gives example with n = 41. Discusses some alternative terminology and one television appearance.

In the near future I intend to use these references as a guide to revising the article in a better-cited way. Mgnbar (talk) 22:55, 28 October 2017 (UTC)[reply]

Maybe it's only my, rare to find elsewhere, personal opinion that it is a bit far fetched to report the solitary, parenthesized remark by Koblitz [here "log" has a different but analogous meaning than before], immediately referring to the notation y=log_bx, as "Koblitz drawing an analogy to real logarithm". In any case, I think Koblitz mostly works in fields, extending results to groups, and this sheds some light on earlier reservations of mine. As usual, I just want to document my opinion. Purgy (talk) 08:09, 29 October 2017 (UTC)[reply]

That parenthetical remark is not solitary. It's part of an entire paragraph of analogy: "When working with the real numbers, exponentiation (finding b^x to a prescribed accuracy) is not significantly easier than the inverse operation (finding log_b x to a prescribed accuracy). But now suppose that we have a finite group...One can compute b^x for large x rather rapidly...But...how can we compute x = log_b y (where here 'log' has a different but analogous meaning than before)?" Mgnbar (talk) 12:11, 29 October 2017 (UTC)[reply]

Haven't I pointed to the possibility of me being solitary in my opinion? Certainly you have cited the one and only (solitary?) occurrence in a perfectly reliable source for the notations of discrete and real logarithms being analogous. I apologize, for always having had their semantics, and not the syntax of "log" in mind. BTW, the cited paragraph seems to emphasize the most relevant disanalogy of the notions, and I could not make me aware of any other remarks on logarithmic analogy. I think I better remove this page from my watchlist. Purgy (talk) 16:28, 29 October 2017 (UTC)[reply]

Here are a few more reliable sources.

• Whitfield Diffie and Martin E. Hellman, "New directions in cryptography", IEEE Transactions on Information Theory, Vol. IT-22, No. 6, November 1976: Defines problem in (Z/qZ)^*, where q is prime. Calls it just logarithm, not discrete logarithm.
• Michael Nielsen and Isaac L. Chuang, "Quantum Computation and Quantum Information": Defines the problem in (Z/NZ)^*, where N is arbitrary. Describes it as a special case of the finite Abelian hidden subgroup problem. Explains the idea of the algorithm, leaving the details as an exercise.
• Eleanor Rieffel and Wolfgang Polak, "Quantum Computing: A Gentle Introduction": Mentions cryptographic application (p. 18). Defines the problem in (Z/pZ)^*, where p is prime. Mentions that it can be generalized to arbitrary finite cyclic groups G. Describes the discrete log problem as a special case of the finite Abelian case of the hidden subgroup problem in an arbitrary group G (p. 171-175). Develops the quantum solution to the finite Abelian hidden subgroup problem (Appendix B).

Mgnbar (talk) 22:04, 1 November 2017 (UTC)[reply]

Today an editor has made some big edits. I appreciate the motivation, and I like the addition of new sources. However, there are many issues that would need to be resolved, to keep these edits. For starters:

1. The opening paragraph reads like a definition, but it is actually giving an example, and readers complain about a lot about this kind of thing.
2. I find the new opening paragraph to be less friendly than the old one, because the old one started with the more familiar concept of real logarithm.
3. I've never seen the notation "dlog". Is there a source for it? All of my sources use "log".
4. The new "Simple Intro" section is not written in encyclopedic prose. I'm not sure what would remain if it were cleaned up.
5. Is the new "Irrational Bases" section a special case of the pre-existing "Powers of a fixed real number" section? I can't tell.

Mgnbar (talk) 02:52, 14 September 2022 (UTC)[reply]

Thank you for taking the time to explain the issues with my revision. I have made a second attempt at my revision based on your comments.

2. I have revised the opening paragraph. It's not giving an example, rather it's trying to show in mathematical terms exactly what a discrete logarithm is so that the reader has some reference point to begin understanding the rest of the article (are discrete logarithms an abstract concept used to prove theorems in math or are they a concrete function able to take numbers and spit out numbers?)
3. I have adjusted my approach to consider this, but I contend that the old paragraph really needed some change. It was well written and excellently explained discrete logarithms if you were previously familiar with discrete lograritihims. For the uninitiated, the previous first paragraph left you wondering what exactly a discrete logarithm is. Granted, it may have been possible to glean the definition of a discrete logarithm after sufficient time spent studying the first paragraph, but this should not be necessary in the first place. Content should be written to give the reader exactly what's going on in a fast paced manner they don't have to reread many many times.
4. There is no source for this. I was in error.
5. Some people are great at instantly picking up highly abstract concepts like modular exponentiation. Some people are not. Some people need some concrete physical numbers to wrap their head around. I rewrote this section to improve it greatly, but I feel strongly it should remain. Having this section doesn't harm the highly abstract mathematicians one bit and they can even skip their eyes over this section if they so choose. Meanwhile, people who need concrete examples to start their conceptual understanding can relish the scalar integers provided.
6. No, it is not. The "Irrational bases" section has to do with base b and the "Powers of a fixed real number" section has to do with powers k in the aspect of a discrete logarithm's definition.

Wowzery (talk) 17:56, 14 September 2022 (UTC)[reply]

Thank you for your continued input, but today's edits still exhibit several important issues.

1. The first sentence is much too narrow. Cryptographically important discrete logs include those in (the multiplicative groups of) finite fields and in (groups of points on) elliptic curves.
2. Formerly the "Powers of 10" example segued into the "Powers of a fixed real number" example, but you have inserted your new examples between them. They are more accessible than your new examples.
3. Your "Calculation via modular recurrence" example uses modular arithmetic but comes before the "Modular arithmetic" example.
4. In the "Irrational bases" section, one of the bases mentioned is 2.2, which is rational.
5. I still don't understand how the "Irrational bases" section isn't a special case of "Powers of a fixed real number". The "fixed real number" is what you call the base, and this section uses bases e and 2.2.

Some of my objections can be addressed by simply moving text around, but they suggest a larger issue. Your edits suggest to me that you view the discrete log problem as primarily about (Z / n Z)^*. It seems that you want to reorganize the article to get to that point as quickly as possible. However, the discrete log problem is more general than that. It encompasses accessible examples that are less esoteric than modular arithmetic and practical examples that are more esoteric. Focusing on modular arithmetic does not represent the discrete log problem accurately, either in theory or in practice, and makes the article less accessible too. Sorry if I have misunderstood your motivation. Mgnbar (talk) 03:13, 15 September 2022 (UTC)[reply]

Thank you for your insights. I have made corresponding edit that addresses your issues of reorganization.

As for #1, please keep in mind that it's an introductory paragraph. It's purpose is to give the reader some idea of where the article is heading, not to paint a pedantically perfect picture with excessive verbiage. It's more than sufficient to leave it at "it has important uses for asymmetric encryption in cryptography" because this statement is later clarified and explained throughout the rest of the article. Also, as far as I can tell, the specific wording "it has" gives the clear and unmistakable impression that discrete logarithims are not restricted to this one purpose.

To address the issue of the scope of my edits:

1. Understanding the discrete logarithm from the perspective of (Z / n Z)* (in full honesty, I don't actually know what that means as I'm more of a compsci guy and less of a mathematician) serves well as a beginner's first baby steps. If one cannot begin these steps somehow, then all advanced revelations to follow are lost on them. That is, the article needs some basic information that oversimplifies discrete logarithms so that the uninitiated can have some firm basis to grab a hold of and begin their understanding. I'm not saying I achieved this the best way; some improvements could be made about how I explained things without loosing sight of the larger picture. However, I do not have sufficient knowledge of mathematics to be the person who could make these improvements.

2. Yes, I agree it is not possible to fully understand/appreciate the discrete logarithm without a solid understanding of set theory, but it is still nonetheless possible to glimpse the beauty of it without this advanced insight. Moreover, I see no reason why access to this beauty should be needlessly restricted to only those privy to the notation and terminology of set theory.

In short, I see no reason why the interesting problem of the discrete logarithm can't appeal to a larger audience of people outside knowledgeable mathematicians as this is fundamentally what Wikipedia is about: being a wiki accessible by everyone (to a reasonable degree of course!) Wowzery (talk) 07:38, 15 September 2022 (UTC)[reply]

For example, I personally have taken math all the way up to Calculus III and Linear Algebra in college, so I consider myself to know more than the average person about math.

Yet, with my knowledge, statements such as "The powers of 10 form an infinite subset G = {…, 0.001, 0.01, 0.1, 1, 10, 100, 1000, …} of the rational numbers. This set G is a cyclic group under multiplication, and 10 is a generator. For any element a of the group, one can compute log₁₀ a" are completely lost on me. I have no idea what any part of that is trying to say, even with my understanding of discrete logarithms and my ability to work backwards on what I guess it might be trying to say. Yet, despite my ignorance of such notations, I am nonetheless able to appreciate (to some lesser degree than a full mathematician probably) the interesting problem of discrete logarithms.

If I, a non-mathematician, can appreciate discrete logarithims without understanding set theory, then surely there must be plenty of other non-mathematician people who can appreciate discrete logarithms without set theory? At least, that's the way I see it. Wowzery (talk) 07:53, 15 September 2022 (UTC)[reply]

You bring up important questions of who Wikipedia is for, how to write technical material for a non-technical audience, etc. Because you bring up these big issues, I note some policy here, at the risk of telling you something you already know. :)

1. Our job is to write for the typical reader of this article, not for the typical reader of Wikipedia.
2. Wikipedia is a reference work, not a textbook. Its job is to summarize reliable sources accurately. Within that constraint, it should be as accessible as it can.

Based on what you've said about yourself, I suspect that you are close to a typical reader of this article. So your viewpoint is valuable in helping us make this article more accessible while retaining its accuracy.

Concretely, let's please set aside the introduction for a moment (introductions are especially hard) and think about what should come immediately after the introduction. Maybe the general definition should not be first. Maybe examples should come first, and maybe rewritten to avoid group-theoretic language. I'd be very open to that. What do you think? Mgnbar (talk) 11:43, 15 September 2022 (UTC)[reply]

Thank you for coming around to see my point of view. I pride myself on trying to keep my mind open and I enjoy appreciate other people who do as well.

I can think of 3 types of possible audience members, but there may be more:

1. Mathematicians
2. Compsci people
3. Ordinary joes who get wind of something called a "discrete logarithm" and look it up because they want to learn something new/interesting
4. Those looking to assign a definition/meaning to a label

The special case of #4 audience members should be satisfied with the introductory statement "it is the inverse function of Modular exponentiation and it has important uses for asymmetric encryption in cryptography", which establishes where the discrete logarithm piece fits into the larger puzzle of mathematics and establishes what's interesting/important about this topic.

Although all are human, the first three types of members would approach this article very differently. I would venture to guess the three types of people might get something as follows out of the article.

1. is a group isomorphism called the discrete logarithm to base b and modulus m.
2. Solving for integer x is the discrete logarithm function.
3. It's a function takes a few integer numbers, does some multiplication and some remainder of division, and spits out a number. It is difficult to calculate, which makes it important to cryptography.

When a reader is introduced to a brand new topic for the first time, they need some anchor point to begin their understanding from. Here is my best-guess of the anchor points for these audience members:

1. The group isomorphism
2. The solve for x in definition in the first paragraph.
3. The nice pretty table with nice pretty scalars in "Calculation via modular recurrence"

After the anchor point, everything is fair game and the reader's next choice of reading depends upon a wide variety of factors such as their education and purpose for visiting the article.

I think the group-theory language should stay and coexist alongside the other explanations appeals to the variety of audience members. This is based on my guess that the group-theory language much better captures the essence of discrete logaritihms in a way much more meaningful to mathematicians. And, people who don't understand the group-theory language have no trouble skipping their eyes over it as they are accustomed to doing so elsewhere on Wikipedia. 129.137.28.238 (talk) 20:54, 15 September 2022 (UTC)[reply]

I could write various things in reply, but I'll restrict myself just to the main issue, because you continue to ignore it:

Discrete logs are not just about modular arithmetic. I'm not making this up; it's what the reliable sources say. Wikipedia's primary job is to summarize the reliable sources. Therefore, a version of this article that restricts to modular arithmetic is untenable.

To put it more bluntly, at the risk of offending someone who has been sincere and civil to me: You cannot re-write this article to focus on the one example that you happen to understand. Mgnbar (talk) 23:28, 15 September 2022 (UTC)[reply]

Thank you for being sincere and frank with me. I appreciate bluntness, so no need to sugar-coat it.

Now that I understand that the issue is citation, I will provide you with one such citation from the first page DEMONSTRATING POSSESSION OF A DISCRETE LOGARITHM WITHOUT REVEALING IT: "Discrete Log Problem-i.e. that she knows an x such that holds" (1). See this attachment: https://www.dropbox.com/s/1z2evt48fmdb3xq/Demonstrating_Possession_of_a_Discrete_Logarithm_W.pdf?dl=0

I hope that this citation is sufficient proof that I am not the only one who needs the discrete logarithm problem condensed down into just modular arithmetic.

To fully finish answering your original question, it is my understanding based upon what you have said that it is not possible to fully understanding everything there is to know about discrete logarithms without understanding group theory.

However, it is nonetheless possible to understand a limited piece of what discrete logarithms are via modular arithmetic. And, although this limited piece paints a woefully incomplete picture, it still does paint as much of the picture as is practically feasible for those who don't know group theory.

Thus, I propose the following solution:

1. The citation I found is used as the basis for introducing non-group-theorists to discrete logarithms via the small portion of discrete logarithm understanding that can be seen in modular arithmetic.
2. All the group theory is kept in the article as a means of fully understanding the true depth and breadth of the discrete logarithm for those familiar with group theory.

Wowzery (talk) 00:42, 16 September 2022 (UTC)[reply]

The text that you found is not making a general claim about the discrete logarithm problem. It is defining the scope of its own discussion about discrete logarithms. This is a common idiom in math writing. For example, a topology textbook might contain the statement "All manifolds are compact." It means, "In this text we consider only compact manifolds, and we don't want to keep saying the word 'compact'." It does not literally mean that all manifolds are compact; that would be false.

Please read the section "Reliable sources" higher on this talk page. There I list seven reliable sources (plus MathWorld). Only two of the seven sources (Rosen and Diffie-Hellman) restrict to the case of modular arithmetic. Even if we found 10 more sources that restricted to modular arithmetic, it's not a majority voting process. There is already ample documentation that discrete logs are not just about modular arithmetic. Mgnbar (talk) 15:43, 17 September 2022 (UTC)[reply]

Upon re-reading some of these posts, I see that we're talking past each other, and it's at least partly my fault. :)

I'm afraid that the devil is in the details. For example, if you intend to focus on modular arithmetic in the introduction, then that's a problem. But maybe you have a different plan.

In these situations, it is often best to propose text on this talk page, reach consensus, and then commit it to the article. Regards, Mgnbar (talk) 01:47, 18 September 2022 (UTC)[reply]

I think I realized what discrete logarithims are about.

I still don't really know group theory, so I probably butchered my language a bit, but I strongly suspect I'm on the right track.

Perhaps something as minor as a few fix-ups of my prepositional phrases involving group-theoric language might make my additions to this article acceptable? (These fix-ups would have to come from someone who knows group theory, though.) Wowzery (talk) 02:16, 20 September 2022 (UTC)[reply]

Let me emphasize that I asked you to propose text on this talk page.

Your recent edit is better than previous ones, in that it does not restrict the problem to Z/mZ. Thank you. However, it will require work to get up to Wikipedia's standards. It would help if you were simply more careful. For example, inexplicably there are now two copies of the "Powers of 10" section. For another example, there is a citation to the Encyclopedia of Math article "Cyclic group" following a sentence that has little to do with it. Mgnbar (talk) 12:20, 22 September 2022 (UTC)[reply]