Talk:Berlekamp–Rabin algorithm

The following is an archived discussion of the DYK nomination of the article below. Please do not modify this page. Subsequent comments should be made on the appropriate discussion page (such as this nomination's talk page, the article's talk page or Wikipedia talk:Did you know), unless there is consensus to re-open the discussion at this page. No further edits should be made to this page.

The result was: promoted by Cwmhiraeth (talk) 06:18, 21 August 2019 (UTC)

(

• Comment or view
• Article history

)

• ... that the original article for Berlekamp's root finding algorithm did not contain a proof of correctness? Source: "The article [3] does not contain a proof for the validity of this algorithm" (Probabilistic Algorithms in Finite Fields)

Created/expanded by Adamant.pwn (talk). Self-nominated at 05:59, 28 July 2019 (UTC).

General: Article is new enough and long enough
New enough: Long enough:

Policy: Article is sourced, neutral, and free of copyright problems
Adequate sourcing: Neutral: Free of copyright violations, plagiarism, and close paraphrasing:

Hook: Hook has been verified by provided inline citation
Cited: - Offline/paywalled citation accepted in good faith Interesting:

QPQ: None required.

Overall: I've reworded the hook a bit, but it should now be good to go! — Bilorv (he/him) _(talk) 10:54, 28 July 2019 (UTC)

GA Review

This review is transcluded from Talk:Berlekamp's root finding algorithm/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Jakob.scholbach (talk · contribs) 13:47, 17 September 2019 (UTC)

I am willing to review this article. One immediate concern that I would have is with the manual of style, specifically MOS:WE which requires to completely avoid the usage of "we" (that is so common in other mathematical writings). For example "Let a polynomial have degree n. We derive the algorithm's complexity as follows" should be rephrased to something like "For a polynomial of degree n, the algorithm has complexity [...]". Jakob.scholbach (talk) 13:47, 17 September 2019 (UTC)

With the current state of the article, I have rather strong reservations about this GA nomination. Problematic are the WP:GAC 1, 2 and 3a, in my opinion.

• The lead does not adequately summarize the article. It is currently approximately a copy of the history section; the rest of the article should (somehow) be covered as well.
• There are various spots where formulations are a bit rough. These include
  • " Peralta's method was generalized for cubic equations" -- "to cubic ..."?
  • "To find such factorization" -- such a ?
  • "is quadratic residue"
  • "is quadratic non-residual"
  • [I could go on.]
• The 2nd section "Statement" is too short to meaningfully stand alone, in my mind.
• Concerning criterion 1a: the article is not currently "understandable to an appropriately broad audience", I think. To this end, it should contain a brief review of the arithmetic in $\mathbb {Z} _{p}$, and a review of the notion of factoring a polynomial. Same for quadratic residues.
• " In 1986 René Peralta proposed a similar algorithm[4] for finding square roots" -- is Berlekamp for arbitrary roots (i.e., not just square roots)? If yes, why is Peralta's work notably here if it is only a special case?
• In §3.2, shouldn't f_z(x) be divisible by x-z to exclude the \lambda = 0 case?
• Section 3.1 "Randomization" does not currently explain what is being randomized here.
• What is also unclear is the fact that an arbitrary polynomial may not actually split into linear factors (i.e., the zeroes of f need not be in Z_p)
• Referencing is problematic throughout the article.
  • Some references are not well-formatted, e.g. the Berlekamp reference lacks an author.
  • It is generally advisable to use secondary or even tertiary references as opposed to primary ones. That is, Berlekamp's own article (and the other original articles) should be referenced only once, probably in the history section, in order to say they exist. All actual information concerning Berlekamp's algorithm should be referenced with secondary or tertiary sources. The article does have a number of such references, but for books like, say the Menezes et al. reference, there should be precise page numbers so the reader can track down the claims.
  • Care should be taken that the references back up the key point of a sentence. For example "Using the fast Fourier transform and Half-GCD algorithm[9]" -- is reference 9 (=Aho's book) supposed to be a general reference for the FT and Half-GCD algorithms? If yes, what is lacking is a reference for the second part of the sentence (which is the part which needs one, the first part may not need one).
• About criterion 3a (broad in its coverage): I see problems here, too. I am not an expert in this area, but I would expect some information about the following questions / areas to be in a Good Article: notable applications? Comparison with other algorithms? Implementations?

To sum up, I believe the article is still quite a bit away from being a Good Article. I will put the nomination on hold for a week or so to see if there is reasonable convergence to the Good Article criteria in the meantime. Jakob.scholbach (talk) 19:02, 21 September 2019 (UTC)

• Hi there! Thanks for your review. Unfortunately, it's already autumn and I don't really have much time to work on the article now. So, I'd ask to drop the nomination completely. I'll keep in mind your remarks if I ever return to this article though. ${\texttt {adamant}}$^{(talk/contribs)} 12:27, 22 September 2019 (UTC)