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.
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)
Donald Knuth, The art of computer programming vol.2, par. 4.6.2 Factorization of polynomials ↩