# 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. #### 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 ... v[r] linearly independent vectors, such as v Q = v 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 ... v[r]
• Find all wi = gcd(u(x),v-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

#### Similar calculators

PLANETCALC, Polynomial factorization modulo p