Content deleted Content added
Line 89:
::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)
| |||