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 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)  ndegree polynomial, n>=2
 p  prime number modulus
Preparation steps
 Check the polynomial is monic. If not, then divide all the polynomial coefficients by the highestdegree coefficient u_{n}
 Check the polynomial is squarefree using Square free polynomial factoring in finite field
 For each squarefree 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_{0}, a_{1} ... a_{n1}) = 1,0...0
 Initialize the first row of the Q matirx (q_{0,0}, q_{0,1} ... q_{0,n1}) with 0,0...0
 Loop on i = 1..n1 do the following
 Loop on k = 1..n1 do the following
 Set t = a_{n1}
 Loop on j = n1 .. 0 do the following
 a_{j}=a_{j1}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
 Loop on k = 1..n1 do the following
 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 nelement vector C to 1 : c_{0} = c_{1} = .. = c_{n1 = 1}
 Set r = 0
 Loop on k = 0 ... n1 do the following
 Loop on j = 0 ... n1 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 nelement vector v^{[r]} to one of the following three:
 a_{k,s}, if found selement of C vector, such as c_{s} = i
 1, if i = k
 0  otherwise
 if q_{k,j} ≠ 0 and c_{j}<0
 Loop on j = 0 ... n1 do the following
 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

D.Knuth The Art of Computer Programming vol 2, par. 4.6.2 Factorization of Polynomials ↩
URL copied to clipboard
Comments