Distinct degree factorization

The calculator finds distinct degree factors of a polynomial in finite field

This page exists due to the efforts of the following people:

Anton

Timur

Timur

Created: 2019-08-27 13:04:13, Last updated: 2022-01-27 08:36:13
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

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.

PLANETCALC, Distinct degree factorization

Distinct degree factorization

Input polynomial
 
The file is very large. Browser slowdown may occur during loading and creation.



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 

URL copied to clipboard
PLANETCALC, Distinct degree factorization

Comments