Square-free polynomial factorization in finite field

The calculator finds all square factors of polynomial in finite field.

This page exists due to the efforts of the following people:

Anton

Created: 2019-08-26 18:22:02, Last updated: 2020-11-03 14:19:37
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/8368/. Also, please do not modify any references to the original work (if any) contained in this content.

The following calculator finds all square factors of a polynomial in the finite field. The square-free factorization is the first step in the polynomial factor decomposition process. You can find more details just below the calculator.

PLANETCALC, Square free polynomial factoring in finite field

Square free polynomial factoring in finite field

Input polynomial
 
Solution
 
The file is very large. Browser slowdown may occur during loading and creation.



We already have similar calculator for square free decomposition in the field of rational numbers, but for some edge cases it will not work for a polynomial with coefficients in finite field. A square-free polynomial decomposition algorithm is based on calculation of the greatest common divisor (GCD) of the polynomial and its derivative : gcd(A,A').
The derivative of a non-zero degree polynomial is always not zero in the ring of integers or rational field. But it can become zero in finite field. E.g. the polynomial x6+x3+2 has zero derivative in F3 field, since (6 mod 3)x5+(3 mod 3)x2 = 0x5+0x2 = 0. A polynomial term with a degree that's a multiple of a field order becomes zero in the derivative.

Square-free decomposition algorithm in finite field

The square-free factorization algorithm for finite field addresses the zero derivative issue, discussed above. The calculator uses the algorithm, described in wikipedia1 ( without recursion ):

// a(x) - Input polynomial (must be monic)
// p - field order
m⟵1 
do
       //Greatest common divisor calculation     
        c(x) ⟵ gcd( a(x), a'(x) ) 
        w(x) ⟵ a(x)/c(x)
       i ⟵1 
       loop while w(x) !=1 
           y(x) ⟵ gcd(w(x), c(x));
           q(x) ⟵ w(x) / y(x)
           if q(x)!=1  output ⟵ q(x)^i*m

           w(x) = y(x)
           c(x) = c(x)/y(x)
           i=i+1
       end loop
       if c(x)!=1
           a(x) = c(x)^(1/p)
           m ⟵ p*m
       end if
loop until c(x)!=1
URL copied to clipboard
PLANETCALC, Square-free polynomial factorization in finite field

Comments