homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightPolynomials

# 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.

#### 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

PLANETCALC, Distinct degree factorization