Polynomial factorization modulo p

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.

Berlekamp polynomial factorization

Integer polynomial coefficients

Modulus

Calculate

Input polynomial

 

Solution

 

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

Download 

 Link  Salvar  Widget

Berlekamp factorization algorithm

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

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 u_n
• 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 (a₀, a₁ ... a_n-1) = 1,0...0
  • Initialize the first row of the Q matirx (q_0,0, q_0,1 ... q_0,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 = a_n-1
      • Loop on j = n-1 .. 0 do the following
        • a_j=a_j-1-t*u_j, assume a_-1 = 0
    • Set i row of matrix Q to A vector
    • Subtract 1 from q_i,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 : c₀ = c₁ = .. = c_{n-1 = -1}
  • Set r = 0
  • Loop on k = 0 ... n-1 do the following
    • Loop on j = 0 ... n-1 do the following
      • if q_k,j ≠ 0 and c_j<0
        • Set a = q_k,j
        • Multiply column j of matrix Q by -1/a
        • Add to each other columns (i ≠ j) column j times q_k,i
      • else (if q_k,j=0 or c_j 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:
          • a_k,s, if found s-element of C vector, such as c_s = i
          • 1, if i = k
          • 0 - otherwise
• Find r factors of u(x) polynomial using vectors v^[2] ... v^[r]
  • Find all w_i = 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 w_i with factors found by gcd(v^[j]-s,w_i) ≠ 1 for each s = 0 ... p