This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/8371/. Also, please do not modify any references to the original work (if any) contained in this content.
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 ↩