Distinct degree factorization

The calculator below decompose an input polynomial to the number of distinct degree factors in a finite field. It is also can be used as a simple test of irreducibility if the result is an only factor of the input polynomial degree.

Distinct degree factorization

Integer polynomial coefficients

Modulus

Calculate

Input polynomial

$x^{9}+7x^{8}+x^{7}+7x^{6}+10x^{5}+2x^{4}+6x^{2}+9x+4$

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

Download 



Factors

Factor	Degree	Exponent
$x^{2}+10x+8$	1	1
$x^{3}+8x^{2}+4x+12$	3	1
$x^{4}+2x^{3}+3x^{2}+4x+6$	4	1
Items per page: 5102050100200500100010K100KAll 1 - 3 of 3

 Link  Save  Widget

If a degree of a result factor is greater than a distinct degree of this factor the further decomposition can be done using Berlekamp algorithm or Cantor-Zassenhaus factorization algorithm. If a factor degree is equal to a distinct degree of this factor then the factor is not reducible.
Before starting main algorithm, described below, this calculator performs the decomposition into square-free factors, if any, the exponent of such a factor will be reflected in the Exponent column.

The distinct degree decomposition algorithm

The algorithm uses the fact that an irreducible polynomial of degree d is a divisor of the x^pd-x and it is not a divisor of x^pc-x, where 0<c<d. ¹

// v(x) - Input polynomial (must be square-free)
// p - field order
w ⟵  x+0
d ⟵  0
loop while d+1 ≤ deg(v)/2 
        w ⟵  w^p mod v
        g ⟵ gcd( w - x, v)
        if g ≠ 1 then
            output ⟵  g,d
            v ⟵  v / g 
            w ⟵ w mod v
        end if
 end loop  
 if v ≠ 1 then output ⟵  v,deg(v)