Distinct degree factorization

The calculator finds distinct degree factors of a polynomial in finite field

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


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.

PLANETCALC, Distinct degree factorization

Distinct degree factorization

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

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 xpd-x and it is not a divisor of xpc-x, where 0<c<d. 1

// 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)

  1. Donald Knuth, The art of computer programming vol.2, par. 4.6.2 Factorization of polynomials 

URL copied to clipboard
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Distinct degree factorization