Distinct degree factorization

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

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

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