ProbSplit - Maple Help

ProbSplit

probabilistic splitting of same degree factors

 Calling Sequence ProbSplit(a, d, x, K) mod p

Parameters

 a - univariate polynomial in x d - positive integer x - name K - (optional) RootOf p - prime integer

Description

 • 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)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p$. The quantity $\mathrm{Rem}\left({x}^{p},a,x\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p$ can be computed using efficiently for large p using $\mathrm{Powmod}\left(x,p,a,x\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}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({\mathrm{log}}_{2}\left(p\right){\mathrm{log}}_{2}\left(m\right){n}^{2}\right)$ assuming classical algorithms for polynomial arithmetic.

Examples

Factor the square-free polynomial a over GF(2)

 > $a≔{x}^{6}+{x}^{5}+{x}^{3}+x$
 ${a}{≔}{{x}}^{{6}}{+}{{x}}^{{5}}{+}{{x}}^{{3}}{+}{x}$ (1)
 > $\mathrm{DistDeg}\left(a,x\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}2$
 $\left[\left[{{x}}^{{2}}{+}{x}{,}{1}\right]{,}\left[{{x}}^{{4}}{+}{x}{+}{1}{,}{4}\right]\right]$ (2)

This tells us that there are two linear factors, and one quartic factor. To complete the factorization we split the quadratic factor

 > $\mathrm{ProbSplit}\left({x}^{2}+x,1,x\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}2$
 $\left\{{x}{,}{x}{+}{1}\right\}$ (3)

Compute the roots of x^4-2=0 mod 10^10-33

 > $a≔{x}^{4}-2:$$p≔{10}^{10}-33:$
 > $q≔\mathrm{Powmod}\left(x,p,a,x\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p$
 ${q}{≔}{9642432862}{}{{x}}^{{3}}$ (4)
 > $g≔\mathrm{Gcd}\left(a,q-x\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p$
 ${g}{≔}{{x}}^{{2}}{+}{715134210}$ (5)
 > $\mathrm{ProbSplit}\left(g,1,x\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p$
 $\left\{{x}{+}{1137017280}{,}{x}{+}{8862982687}\right\}$ (6)
 > $\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}$ (7)
 > $d≔\mathrm{DistDeg}\left(a,x,\mathrm{\alpha }\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}2$
 ${d}{≔}\left[\left[{\mathrm{\alpha }}{}{x}{+}{{x}}^{{2}}{,}{1}\right]{,}\left[{{x}}^{{4}}{+}{\mathrm{\alpha }}{+}{x}{,}{2}\right]\right]$ (8)
 > $\mathrm{seq}\left(\mathrm{ProbSplit}\left(\mathrm{op}\left(f\right),x,\mathrm{\alpha }\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}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\}$ (9)

References

 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.