homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightPolynomials

Polynomial factorization modulo p

The calculator finds polynomial factors modulo p using Elwyn Berlekamp algorithm

This calculator finds irreducible factors of a given polynomial modulo p using Elwyn Berlekamp factorization algorithm. The algorithm description is just below the calculator.

PLANETCALC, Polynomial factorization modulo p

Polynomial factorization modulo p

Input polynomial
 

Berlekamp factorization algorithm

The algorithm described here is a compact compilation of the factoring algorithm described in TAOCP vol 2 by D.Knuth 1.

Initial data

  • u(x) - n-degree polynomial, n>=2
  • p - prime number modulus

Preparation steps

  • Check the polynomial is monic, if not then divide all the polynomial coefficients by the highest-degree coefficient un
  • Check the polynomial is square free using Square free polynomial factoring in finite field
  • For each square-free polynomial factor of degree 2 or higher run the algorithm below

The algorithm

  • Find Q matrix (n * n ), where n is a polynomial degree by the procedure below:
    • Initialize a vector A (a0, a1 ... an-1) = 1,0...0
    • Initialize the first row of the Q matirx (q0,0, q0,1 ... q0,n-1) with 0,0...0
    • Loop on i = 1..n-1 do the following
      • Loop on k = 1..n-1 do the following
        • Set t = an-1
        • Loop on j = n-1 .. 0 do the following
          • aj=aj-1-t*uj, assume a-1 = 0
      • Set i row of matrix Q to A vector
      • Subtract 1 from qi,i element of matrix Q
  • Find v[1] ... v[r] linearly independent vectors, such as v[1] Q = v[2] Q = ... v[r] Q = (0,0...0)
    • Set all elements of n-element vector C to -1 : c0 = c1 = .. = cn-1 = -1
    • Set r = 0
    • Loop on k = 0 ... n-1 do the following
      • Loop on j = 0 ... n-1 do the following
        • if qk,j ≠ 0 and cj<0
          • Set a = qk,j
          • Multiply column j of matrix Q by -1/a
          • Add to each other columns (i ≠ j) column j times qk,i
        • else (if qk,j=0 or cj equal to 0 or greater than 0)
          • Set r = r + 1
          • Set every i element of a new n-element vector v[r] to one of the following three:
            • ak,s, if found s-element of C vector, such as cs = i
            • 1, if i = k
            • 0 - otherwise
  • Find r factors of u(x) polynomial using vectors v[2] ... v[r]
    • Find all wi = gcd(u(x),v[2]-s) ≠ 1 for each s = 0 ... p
    • if count of w < r do the following
    • Loop on j=3 ... r until count of w < r
      • Replace wi with factors found by gcd(v[j]-s,wi) ≠ 1 for each s = 0 ... p


  1. D.Knuth The Art of Computer Programming vol 2, par. 4.6.2 Factorization of Polynomials 

Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Polynomial factorization modulo p

Comments