Talk:Euclidean algorithm

Alt text

I agree with commenting out the alt text, as it damages the view for users not using a text-reader, and are (with one exception) less understandable than the LaTeX text itself.

In addition, I find no consensus on the talk page for the requirement for the alt text.

I realize the problem for users with text-readers, but damaging the article for others is not the way to solve the problem. "<" math alt= text ">" is not properly implemented on Wikipedia, and should not be used. Yet. In addition, I do not understand most of the alt descriptions. As a mathematician of at least 45 years standing, that suggests a problem with the alt text. I find the LaTex more understandable, and I suspect a text-reader with spoken punctuation would also find the LaTeX more understandable than the alt text given here. — Arthur Rubin (talk) 07:38, 29 August 2014 (UTC)

I disagree.

I do not understand the claim that alt text is not properly implemented on WP. As I understand it, alt text is not a problem for the standard display that WP uses, but it is a problem for those who use MathJax because MathJax messes up. I'm not sure, but I have the impression that MathJax used to handle alt text without trouble but was broken in a new release.

Instead of fixing MathJax (or using other tools), the workaround has been to comment out or even delete the alt text. If alt text broke everything, then I would not have a problem commenting it out or even removing it. That does not seem to be the case here.

I have almost no understanding of WP's legal obligations to accomodate those with disabilities, but I believe that there is such a duty. Deleting existing accomodations for the benefit of able MathJax users would fly in the face of such a duty.

Independently, if the alt descriptions are inadequate, then they should be fixed. My disagreement is not with the adequacy of the alt text. Presumably even text that was an exceptionally good description of the math would confuse MathJax. If the text were perfect, would you still advocate that it be commented out?

Glrx (talk) 17:31, 1 September 2014 (UTC)

@Girx: If it worked properly in MathJax (and it's not correct to say that it was an error in MathJax; it was a change in Wikimedia rendering, probably related to Parsoid, which passes the wrong information to MathJax. It should be fixed sometime, but, considering that math is not yet working properly in Flow, I wouldn't hold my breath), I would be in favor of quoting it in a way that could be easily restored. But

$M={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}$

is worse than having no alt tag at all in a reasonable implementation, which would puts the TeX into the alt tag. I don't know if that is done.

As a further aside, I don't know if anyone on the Wikimedia "improvement" team has access to screen readers. You might want to check with them and ask them make sure none of these "improvements" damage screen readers more than they damage the use by visually-oriented users. — Arthur Rubin (talk) 00:07, 4 September 2014 (UTC)

Anyone interested in testing the new Math accessibilty features build into the new Math rendering mode based on this article. See http://mathosphere.wmflabs.org:8080/wiki/Main_Page --Physikerwelt (talk) 08:50, 18 January 2016 (UTC)

The RSA Section is Confused and Confusing

The section "Multiplicative inverses and the RSA algorithm" starts out with a long paragraph defining what a finite field is, but then in the third paragraph admits that RSA does not use finite fields, but claims that it uses rings. Actually, it doesn't really use rings either, it just uses finite abelian groups.

The Extended Euclidean Algorithm is used during RSA key generation to (1) verify that a component (call it e) of one of the keys is a member of the multiplicative group of integers modulo (p-1)·(q-1) where p and q are primes; and to (2) find the inverse of e in that group, which will be a component of the other key. See https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Key_generation

LaQuilla (talk) 10:31, 6 December 2014 (UTC)

I agree. This is better explained (in my opinion) in Extended Euclidean algorithm. However the problem addressed here is the problem of "modular multiplicative inverse". This is not just a problem of group theory, as addition is used by the algorithm for computing the inverse.

The section has other issues: modular inverses are computed in many other widely used cryptographic schemes, such as ECDHE, which is used in the secure connexions to Wikipedia. Also RSA is not specifically used in e-commerce, it is used is almost all secure web connections, such as (again) secure connexions to Wikipedia.

Thus the section has not only to be rewritten, but also to be renamed "Modular inverse". D.Lazard (talk) 11:38, 6 December 2014 (UTC)

There is a more straightforward way to describe the calculation of multiplicative inverses in finite fields and the methods extension to rings. LACornell (talk) 15:54, 29 July 2016 (UTC)

Math formatting

I was tempted to undo this recent revert as I think that the {{math}} formatting is an improvement over straight wiki-text both in its appearance and in how well it matches the <math> equations. However, in order to be effective, the formatting needs to be applied consistently throughout the article, and it wasn't even done to all of the formulas within a single section. @Cedar101:: Would you be interested in making the same changes more globally? Or, if others (including 86.187.176.209) object to the math templates, here would be a good place to discuss it. —David Eppstein (talk) 18:42, 5 January 2016 (UTC)

Undo the revert. I support the edit with {{math}} as an improvement even if nothing further is done by Cedar101. It's an edit in the right direction. Glrx (talk) 01:33, 8 January 2016 (UTC)

Invitation to discourse on alternative formulations of some sections and related algorithms.

I have ways of describing some of the applications here that are different than these relying more heavily and more transparently on abstract algebra. Also I have a factorization method algorithm that has the Euclidean Algorithm as its starting point which I think deserve a page of its own linked to this one. Can anyone speak to these things? LACornell (talk) 15:49, 29 July 2016 (UTC)

Whether something is appropriate for inclusion here depends on whether it is covered by third-party reliable sources, typically peer-reviewed publications from established mathematics journals, or textbooks on the subject published by recognized scientific publishing houses. Generally speaking, we should not include anything that is exclusively self-published or original. The same holds for whether it is appropriate to have a separate article on a topic. Sławomir Biały (talk) 17:15, 29 July 2016 (UTC)

Proof of worst case

Under the subsection "worst case" under the the section "efficiency" an argument is given that the Fibonacci numbers F_k+1 and F_k+2 are the smallest numbers that take k steps. However, the author never defines what it means for a pair to be smallest. Given the argument about bounding the number of steps that follows, it seems that the implicit definition being used is (a, b) is "smaller" than (c, d) if b < d and (presumably) if b = d a < c. However, this makes the induction argument unclear. If we are just trying to get b to be small, how do we know that we can you use the induction hypothesis on the M-1 step where b = q₁ r₀ + r₁. Couldn't we have r₀ be bigger than F_M, but b be smaller than F_M+1? — Preceding unsigned comment added by Narjul (talk • contribs) 16:18, 30 January 2017 (UTC)

"Smallest" has to be taken in its strongest meaning. That is: if the pair a > b requires n steps for the Euclidean algorithm, then we have both a ≥ F_n+2 and b ≥ F_n+1. Proof: Let a = bq + r be the first division step. As the pair q > r requires n − 1 steps, the induction hypothesis is b ≥ F_{n + 1} and r ≥ F_n. Then a = bq + r ≥ b + r ≥ F_{n + 1} + F_n = F_n+2, qed. I have edited the article for clarifying this point (and simplifying the proof). D.Lazard (talk) 17:46, 30 January 2017 (UTC)

Bibliograhpy

Would there be any objections to moving the "Bibliography" section to a subsection of "References". This is not a major move but there is more than one reason why it would make sense.

• On Wikipedia a bibliography section is normally the first section in the appendices, usually for biographies, or otherwise "Works" per Works or publications.
• A bibliography of sources, along with a references or notes section providing text-source integrity, constitute the citations so are certainly related.
• The number of GA and FA articles that use a separate sourcing "Bibliography" section is small so it becomes an "exception".

This has nothing to do with any article rating but as "approaching" (GA) and attaining the "best articles Wikipedia has to offer" (FA) other articles are often styled accordingly. The use of "Bibliography" sections in more than one place is confusing and this would remove that aspect and show the relationship as we normally would in subsections. Otr500 (talk) 18:53, 24 July 2018 (UTC)