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) - 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
- Loop on k = 1..n-1 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 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
- if qk,j ≠ 0 and cj<0
- Loop on j = 0 ... n-1 do the following
- 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
-
D.Knuth The Art of Computer Programming vol 2, par. 4.6.2 Factorization of Polynomials ↩
URL copiado para a área de transferência
Calculadoras similares
PLANETCALC, Polynomial factorization modulo p
Comentários