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 $\mathrm{Gcd}\left(a\,x^p-x\right)\mathbf{mod}p$. The quantity $\mathrm{Rem}\left(x^p\,a\,x\right)\mathbf{mod}p$ can be computed using efficiently for large p using $\mathrm{Powmod}\left(x\,p\,a\,x\right)\mathbf{mod}p$. 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 $\mathrm{O}\left({\log }_2\left(p\right){\log }_2\left(m\right)n^2\right)$ assuming classical algorithms for polynomial arithmetic.

$a≔x^6+x^5+x^3+x$

$a≔x^6+x^5+x^3+x$

$\mathrm{DistDeg}\left(a\,x\right)\mathbf{mod}2$

$\left[\left[x^2+x\,1\right]\,\left[x^4+x+1\,4\right]\right]$

$\mathrm{ProbSplit}\left(x^2+x\,1\,x\right)\mathbf{mod}2$

$\left\{x\,x+1\right\}$

$a≔x^4-2\:$$p≔{10}^{10}-33\:$

$q≔\mathrm{Powmod}\left(x\,p\,a\,x\right)\mathbf{mod}p$

$q≔9642432862x^3$

$g≔\mathrm{Gcd}\left(a\,q-x\right)\mathbf{mod}p$

$g≔x^2+715134210$

$\mathrm{ProbSplit}\left(g\,1\,x\right)\mathbf{mod}p$

$\left\{x+1137017280\,x+8862982687\right\}$

$\mathrm{alias}\left(\mathrm{\alpha }=\mathrm{RootOf}\left(x^2+x+1\,x\right)\right)\:$

$a≔x^6+\mathrm{\alpha }{x}^5+x^3+\mathrm{\alpha }x+x$

$a≔\mathrm{\alpha }{x}^5+x^6+x^3+\mathrm{\alpha }x+x$

$d≔\mathrm{DistDeg}\left(a\,x\,\mathrm{\alpha }\right)\mathbf{mod}2$

$d≔\left[\left[\mathrm{\alpha }x+x^2\,1\right]\,\left[x^4+\mathrm{\alpha }+x\,2\right]\right]$

$\mathrm{seq}\left(\mathrm{ProbSplit}\left(\mathrm{op}\left(f\right)\,x\,\mathrm{\alpha }\right)\mathbf{mod}2\,f=d\right)$

$\left\{x\,x+\mathrm{\alpha }\right\},\left\{\mathrm{\alpha }x+x^2+1\,\mathrm{\alpha }x+x^2+\mathrm{\alpha }\right\}$

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.