Talk:Factorization of polynomials over finite fields

Article needs improvement

This is just to say that a lot of work seems to be necessary here. Lots of stuff with little rhyme or reason, like the sectioning of the article; the subsection called "example" is hard to decipher, one wonders what this is an example of. Marc van Leeuwen (talk) 14:33, 18 March 2011 (UTC)[reply]

The article lacks a clear purpose. Cantor-Zassenhaus is given here even though it has its own wiki page, while recent algorithms with subquadratric complexity are not even mentioned. I propose deleting large portions, and reduce the article to a list of references to other places.MvH. —Preceding undated comment added 02:20, 8 February 2014 (UTC)[reply]

Needs more Mathematical Methods and less computer algorithms

Most of the stuff here is talk of finding the factors algorithmically, but no sense of how to do so intuitively. Perhaps examples would help. — Preceding unsigned comment added by 140.247.79.236 (talk) 17:30, 13 February 2012 (UTC)[reply]

Incorrect example

The current example for factorization of:

f = x^11 + 2 x^9 + 2x^8 + x^6 + x^5 + 2x^3 + 2x^2 +1

says that the result is:

f= (x+1)(x^2+1)^3(x+2)^4

But that does not seem correct:

http://www.wolframalpha.com/input/?i=factor+x%5E11+%2B+2+x%5E9+%2B+2x%5E8+%2B+x%5E6+%2B+x%5E5+%2B+2x%5E3+%2B+2x%5E2+%2B1

or:

http://www.wolframalpha.com/input/?i=expand+%28x%2B1%29%28x%5E2%2B1%29%5E3%28x%2B2%29%5E4

Not sure what should be fixed: the polynomial or the factors?

PS: I'm new to editing of Wikipedia, feel free to remove this comment if not appropriate. — Preceding unsigned comment added by 62.197.198.100 (talk) 13:17, 6 March 2014 (UTC)[reply]

The article is correct, although the fact that the factorization is done modulo 3 is not clear enough. I have clarified this. To verify correctness, you have simply to add "mod 3" at the end of the command line of each link that you have provided. D.Lazard (talk) 17:35, 6 March 2014 (UTC)[reply]

In that case, I apologize for the noise. Please delete this note once you read it, thanks. — Preceding unsigned comment added by 62.197.198.100 (talk) 21:13, 6 March 2014 (UTC)[reply]

The square free algorithm has a special case that is unnecessary

There is no need to test for the derivative being zero.MeanStandev (talk) 18:05, 16 April 2018 (UTC)[reply]

This is true in characteristic 0. Here we are over a finite field, and a nonzero polynomial may have a zero derivative. D.Lazard (talk) 19:42, 16 April 2018 (UTC)[reply]

Yes, a nonconstant polynomial can have a zero derivative. But if you remove the test, you will see that the zero derivative case is handled correctly in the remaining code, since the gcd of a polynomial with a zero polynomial is the polynomial itself.MeanStandev (talk) 20:07, 19 April 2018 (UTC)[reply]

OK, you are right. However the test is not costly, and, with it, the algorithm may be clearer for some readers. Thus, I have not modified the pseudocode, and I have added an explanation. D.Lazard (talk) 07:55, 20 April 2018 (UTC)[reply]

Cantor-Zassenhaus for characteristic 2

The C-Z algorithm as described posits odd q. But C-Z actually works for even q as well. See for example https://arxiv.org/pdf/1012.5322.pdf

I believe the only change needed to handle all cases is to replace the exponent (q**d-1)/2 with (q**d-1)/(the smallest factor of q**d-1), although there are more efficient techniques. MeanStandev (talk) 20:43, 27 April 2018 (UTC)[reply]