Content deleted Content added
Assessment: banner shell, Mathematics (Rater) |
|||
| (9 intermediate revisions by 5 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 80 ⟶ 84:
:::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)? ==
Line 87 ⟶ 93:
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'''<sub>''q''</sub> ?) , 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
:::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)
| |||