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 CantorZassenhaus 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 squarefree 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. ^{1}
// v(x)  Input polynomial (must be squarefree)
// 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 ↩
Comments