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 ↩
Comentários