Talk:Factorization of polynomials over finite fields: Difference between revisions

Revision as of 07:56, 20 April 2018

Revision as of 02:51, 27 April 2018

Line 39:

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.[[User:MeanStandev|MeanStandev]] ([[User talk:MeanStandev|talk]]) 20:07, 19 April 2018 (UTC)

: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. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 07:55, 20 April 2018 (UTC)

== 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 for the even case is to replace the exponent (q**d-1)/2 with either (q**d-1)/3 when q is a multiple of 4 or ((2q)**d-1)/3 otherwise, perhaps the latter only when q**d is not a multiple of 4.

[[User:MeanStandev|MeanStandev]] ([[User talk:MeanStandev|talk]]) 02:51, 27 April 2018 (UTC)