probabilistic splitting of same degree factors
ProbSplit(a, d, x, K) mod p
univariate polynomial in x
ProbSplit factors a monic square-free univariate polynomial over a finite field where it is known to contain factors of degree d only. The factorization is returned as a set of irreducible factors.
This function is normally used with the DistDeg function which is used to split a polynomial into factors which contain factors of the same degree. The ProbSplit function can then be applied to split those factors.
This function can also be used to compute the roots of a polynomial over a large finite field efficiently. If a is square-free, p>2, then the product of linear factors g dividing a is given by Gcd⁡a,xp−xmodp. The quantity Rem⁡xp,a,xmodp can be computed using efficiently for large p using Powmod⁡x,p,a,xmodp. Applying ProbSplit(g, 1, x) mod p splits g into linear factors, hence obtaining the roots of a.
The optional argument K specifies an extension field over which the factorization is to be done. See Factor for further information. Note: only the case of a single field extension is implemented.
Algorithm: a probabilistic method of Cantor-Zassenhaus is used to try to split the polynomial a of degree n into m=(n/d) factors of degree d. The average complexity is Olog2p⁢log2m⁢n2 assuming classical algorithms for polynomial arithmetic.
Factor the square-free polynomial a over GF(2)
a ≔ x6+x5+x3+x
This tells us that there are two linear factors, and one quartic factor. To complete the factorization we split the quadratic factor
Compute the roots of x^4-2=0 mod 10^10-33
a ≔ x4−2:p ≔ 1010−33:
q ≔ Powmod⁡x,p,a,xmodp
g ≔ Gcd⁡a,q−xmodp
a ≔ x6+α⁢x5+x3+α⁢x+x
d ≔ DistDeg⁡a,x,αmod2
Cantor, D. G., and Zassenhaus, H. "A New Algorithm for Factoring Polynomials over a Finite Field." Mathematics of Computation, Vol. 36, (1981): 587-592.
Geddes, K. O.; Labahn, G.; and Czapor, S. R. Algorithms for Computer Algebra. Kluwer Academic Publishers, 1992.
Download Help Document