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

Revision as of 18:05, 16 April 2018

Latest revision as of 07:51, 22 July 2024

(27 intermediate revisions by 7 users not shown)

Line 1:

{{WikiProject banner shell|class=C|1=

{{WikiProject Mathematics}}

}}

== 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. [[User:Marc van Leeuwen|Marc van Leeuwen]] ([[User talk:Marc van Leeuwen|talk]]) 14:33, 18 March 2011 (UTC)

Line 36 ⟶ 40:

There is no need to test for the derivative being zero.[[User:MeanStandev|MeanStandev]] ([[User talk: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. [[User:D.Lazard|D.Lazard]] ([[User talk: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.[[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 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.

[[User:MeanStandev|MeanStandev]] ([[User talk:MeanStandev|talk]]) 20:55, 27 April 2018 (UTC)

== factorization of polynomial in a ring ''Z''/15''Z'' ==

In ''Z''/15''Z'', (''x''+1) × (''x''+2) = ''x''² + 3''x'' + 2, and (''x''+7) × (''x''+11) is also ''x''² + 3''x'' + 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''² + 3''x'' + 2 have two factorizations to irreducible polynomials in ''Z''/15''Z''. Besides, in ''Z''/15''Z'', ''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 {{math|''Z''/15''Z''}}, which is not a field. [[Chinese remainder theorem]] allows deducing the factorization(s) of a polynomial over {{math|''Z''/15''Z''}} from the factorizations over {{math|''Z''/3''Z''}} and {{math|''Z''/5''Z''}}. [[User:D.Lazard|D.Lazard]] ([[User talk: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):

<pre>

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

</pre>

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. [[User:Rcgldr|Rcgldr]] ([[User talk: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. [[User:D.Lazard|D.Lazard]] ([[User talk: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)? [[User:Rcgldr|Rcgldr]] ([[User talk: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. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 18:26, 13 July 2020 (UTC)

{{outdent}}For Distinct-degree factorization algorithm, on the very first step (i==1), <math>g=\gcd(f, x^{q}-x)</math> = 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. [[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 00:54, 15 July 2020 (UTC)

{{ping|D.Lazard}} - The Wiki article implies that Cantor–Zassenhaus will only work for odd order <math>q</math>. Is there an factoring algorithm for even order <math>q</math>, such as <math>2^n</math>? [[User:Rcgldr|Rcgldr]] ([[User talk: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. [[User:Rcgldr|Rcgldr]] ([[User talk:Rcgldr|talk]]) 15:41, 14 July 2020 (UTC)

:If the coefficients of a polynomial belong to a field {{mvar|F}}, all the factors of the square-free factorization have their coefficients in {{mvar|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. [[User:D.Lazard|D.Lazard]] ([[User talk: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, <math>g=\gcd(f, x^{q}-x)</math> = 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. [[User:Rcgldr|Rcgldr]] ([[User talk: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. [[User:D.Lazard|D.Lazard]] ([[User talk: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. [[User:Rcgldr|Rcgldr]] ([[User talk: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? [[User:Chinchiller569|Chinchiller569]] ([[User talk:Chinchiller569|talk]]) 06:35, 25 November 2020 (UTC)