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 the Elwyn Berlekamp factorization algorithm. The algorithm description is just below the calculator.

PLANETCALC, Berlekamp polynomial factorization

Berlekamp polynomial factorization

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

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 the count of w < r do the following
    • Loop on j=3 ... r until the 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 

URL copied to clipboard
PLANETCALC, Polynomial factorization modulo p

Comments