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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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 (even and odd) is to replace the exponent (q**d-1)/2 with (q**d-1)/(the smallest prime factor of q**d-1), although there are more efficient techniques. MeanStandev (talk) 20:55, 27 April 2018 (UTC)

factorization of polynomial in a ring Z/15Z

In Z/15Z, (x+1) × (x+2) = x² + 3x + 2, and (x+7) × (x+11) is also x² + 3x + 2, and all of the polynomials x+1, x+2, x+7 and x+11 are irreducible (since all of they have degree 1), thus x² + 3x + 2 have two factorizations to irreducible polynomials in Z/15Z. Besides, in Z/15Z, x² + 2 is irreducible, since −2 is not a quadratic residue mod 15.

This article is about factorization over a finite field. Thus it does not applies to Z/15Z, which is not a field. Chinese remainder theorem allows deducing the factorization(s) of a polynomial over Z/15Z from the factorizations over Z/3Z and Z/5Z. D.Lazard (talk) 19:56, 13 August 2018 (UTC)

Trying to understand how any of these methods would work for f(x) with coefficients in GF(p^r)

Consider GF(2^16) based on primitive polynomial x^16 + x^12 + x^3 + x + 1. Find the factors of f(x) = x^32 + x^22 + x^2 + x + 1, where the coefficient values are 0 and 1, but are elements of GF(2^16). There are 16 quadratic factors, shown in hex (found by brute force search):

x^2 + 04c4 x + 118d
x^2 + 09ad x + 1cec
x^2 + 0e38 x + 1cb7
x^2 + 16b6 x + 1dbc
x^2 + 173b x + 0cf9
x^2 + 1c89 x + 1cf0
x^2 + 40ab x + 4be1
x^2 + 524f x + 0a76
x^2 + 5e62 x + 0716
x^2 + 5eec x + 0a37
x^2 + b67f x + 4188
x^2 + be6f x + fbf0
x^2 + e079 x + 17d4
x^2 + effe x + ed71
x^2 + f62b x + 07d5
x^2 + fd83 x + 17dd

For the first algorithm shown, the issue is that f '(x) = 1. For the others it would seem that math would involve multiply or xor of the values 0 and 1, and I don't see how non-zero values other than 1 are produced. Rcgldr (talk) 14:38, 13 July 2020 (UTC)

As your polynomial is square free and all its factors are quadratic, the first algorithms to be considered are Berlekamp and Cantor–Zassenhaus algorithms. Berlekamp algorithm has a loop on all elements of the ground field (here GF(2^16)), and Cantor–Zassenhaus algorithm chooses at random polynomials with coefficients in GF(2^16). This is this way that polynomial coefficients that are not in GF(2) are introduced. D.Lazard (talk) 15:41, 13 July 2020 (UTC)

Does the Berlekamp algorithm loop on all 2^16 elements of GF(2^16) or on all 2^32 combinations of 2 elements of GF(2^16)? Rcgldr (talk) 17:54, 13 July 2020 (UTC)

As far as I remember, it loops on all 2^16 elements of GF(2^16). In any case, Cantor–Zassenhaus is probably more efficient on this size of problems. I agree that the article Berlekamp's algorithm is not clearly written. If you want to be sure look at one of the numerous textbooks that describe these algorithms in details. Wikipedia is not a textbook, and is not aimed to replace textbooks. D.Lazard (talk) 18:26, 13 July 2020 (UTC)

For Distinct-degree factorization algorithm, on the very first step (i==1), $g=\gcd(f,x^{q}-x)$ = 1, same issue as the first algorithm. The size of the coefficients doesn't seem to matter if the values start off as 0 and 1. Rcgldr (talk) 00:54, 15 July 2020 (UTC)

@D.Lazard: - The Wiki article implies that Cantor–Zassenhaus will only work for odd order $q$. Is there an factoring algorithm for even order $q$, such as $2^{n}$? Rcgldr (talk) 03:17, 10 October 2021 (UTC)

Square free factorization - are the polynomial coefficients GF(p) or GF(q)?

This section includes "factorization for polynomials whose coefficients come from the finite field F_q", however, it seems that the coefficients are from finite field F_p.

For example, consider a typical case for GF(2^32), p = 2, q = 2^32, f(x) = x^32 + x^22 + x^2 + x + 1, with coefficients in GF(p) == GF(2), f(x) is primitive. However say that GF(2^32) is to be mapped to a composite field GF((2^16)^2). Let p = 2, q = 2^16, f(x) = x^32 + x^22 + x^2 + x + 1, with coefficients in GF(q) == GF(2^16) (is this the same as F_q ?) , in this case f(x) has 16 quadratic factors, any of which can be used as the basis for a composite field. For the first algorithm note that f '(x) = 1, so it would end up in an infinite loop. For the second algorithm, the coefficients of f(x) are 0 or 1, and multiplication or xor'ing of these values is not going to produce any numbers other than 0 or 1. Rcgldr (talk) 15:41, 14 July 2020 (UTC)

If the coefficients of a polynomial belong to a field F, all the factors of the square-free factorization have their coefficients in F. This results from the fact that the main tool of the algorithms is the polynomial greatest divisor. In your example, the input polynomial is the product of distinct irreducible quadratic factors. This implies that the results of the square-free factorization and the distinct-degree factorization are both the input polynomial. D.Lazard (talk) 19:15, 14 July 2020 (UTC)

As I posted in the above section, for f(x) = x^32 + x^22 + x^2 + x + 1 with coefficients in GF(2^16), square free factorization, f '(x) = 1, and the first step of distinct degree factorization, $g=\gcd(f,x^{q}-x)$ = 1. So those two methods are not working in GF(q), but instead only in GF(p), and the size of the coefficients being used to hold 0 or 1 doesn't matter. Rcgldr (talk) 01:07, 15 July 2020 (UTC)

Please, read the definition of the distinct-degree factorization. It is not the complete factorization. In your example the result of the distinct-degree factorization of f(x) is f(x) itself, independently whether the coefficients are considered to belong to GF(q) or GF(2). This does not means that the algorithm does not work This means that you confuse the specifications of the square-free factorization and of the complete factorization. D.Lazard (talk) 08:45, 15 July 2020 (UTC)

I didn't realize that in my case, it's just another check for being square free. In my case, the degree of the factors and number of factors is known. If factoring f(x) of degree 64, with coefficients in GF(2^32), there are 32 primitive quadratics, or if the coefficients are in GF(2^16), there are 16 primitive quartics. I don't know if there is any way to take advantage of this. I'm trying to find a way to factor that doesn't involve trying 2^64 combinations of factor coefficients just to find one factor (one factor is all I need), which isn't possible time wise. Rcgldr (talk) 18:40, 15 July 2020 (UTC)

Citation needed

'As the reduction of the factorization of multivariate polynomials to that of univariate polynomials does not have any specificity in the case of coefficients in a finite field, only polynomials with one variable are considered in this article.'

Can someone help with a citation for this statement, please? Chinchiller569 (talk) 06:35, 25 November 2020 (UTC)