Polynomial factorizaton in finite field

The calculator finds factors of a polynomial using Cantor-Zassenhaus algorithm

This calculator finds irreducible factors of an univariate polynomial in finite field using Cantor-Zassenhaus algorithm. Initially it performs Distinct degree factorization to find factors, which can be further decomposed. Finally, if required, it applies equal degree factorization algorithm described just below the calculator.

PLANETCALC, Cantor-Zassenhaus polynomial factorizaton in finite field

Cantor-Zassenhaus polynomial factorizaton in finite field

Input polynomial

Cantor-Zassenhaus factorization algorithm

This algorithm generally has better characteristics for big modulus than similar Berlecamp factorization algorithm.

  • Check the polynomial is square-free
  • Find all factors for distinct degrees
  • Apply equal degree decomposition algorithm, described below, for every factor which degree greater than distinct degree obtained on previous step

Equal degree factorization algorithm

// u(x) - Input polynomial of degree rd 
//    which has r factors each 
//    of degree d in Fp field
// p - odd field order
// d - target factors degree
// r - number of target factors
s⟵ { u }
loop while size(s) less than r
        h ⟵ random polynomial 
                  of degree less than 2d
        g ⟵ h^(p^d-1/2) -1 mod u
        for each a in s do 
              if deg(a) greater than d 
                    and gcd(g, a) ≠ 1 
                    and gcd(g, a) ≠ a then
                       remove a from s
                       add gcd(g,a) to s
                       add a/gcd(g,a) to s
              end if
         end do
end loop
output s
URL copied to clipboard
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Polynomial factorizaton in finite field