Factor - Maple Programming Help

Factor

inert factor function

 Calling Sequence Factor(a, K)

Parameters

 a - multivariate polynomial K - optional specification of the algebraic extension

Description

 • The Factor function is a placeholder for representing the factorization of the polynomial a over a unique factorization domain. It is used in conjunction with either mod or evala, which define the coefficient domain as described below.
 • The call Factor(a) mod p computes the factorization of a over the integers modulo p a prime integer. The polynomial a must have rational coefficients or coefficients from a finite field specified by RootOfs.
 • The call Factor(a, K) mod p and computes the factorization of the polynomial a over the Galois field (finite field) defined by the algebraic extension K over the integers mod p a prime integer. The extension K is specified by a RootOf and must be irreducible over the integers mod p.
 • The call evala(Factor(a, K)) computes the factorization of the polynomial a over an algebraic number (or function) field defined by the extension K, which is specified as a RootOf or a set of RootOfs. The polynomial a must have algebraic number (or function) coefficients.
 • Factorization methods available are lenstra, trager, and linear. The default is trager. One selects the method by adding the name to the option set (see evala).
 • For the factorization of a univariate polynomial over an algebraic number field, use Lenstra's factorizer. This method is sometimes faster for small degree fields than the default factorizer.
 • For the factorization of a univariate polynomial over a finite field, Factor uses the Cantor Zassenhaus distinct degree algorithm. Berlekamp's algorithm is an alternate method that is more efficient in cases involving large p and a polynomial a that is irreducible or has few factors (see Berlekamp).
 • The Domains package is implicitly used to factor multivariate polynomials over a Galois field defined by a single extension. It can also be used explicitly to factor over a tower of multiple algebraic extensions.

Examples

 > $\mathrm{Factor}\left({x}^{2}+3x+3\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}7$
 $\left({x}{+}{4}\right){}\left({x}{+}{6}\right)$ (1)
 > $\mathrm{alias}\left(\mathrm{\alpha }=\mathrm{RootOf}\left({x}^{2}+x+1\right)\right):$
 > $\mathrm{Factor}\left({x}^{3}+1,\mathrm{\alpha }\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}2$
 $\left({x}{+}{\mathrm{\alpha }}\right){}\left({x}{+}{1}\right){}\left({x}{+}{\mathrm{\alpha }}{+}{1}\right)$ (2)
 > $\mathrm{alias}\left(\mathrm{sqrt2}=\mathrm{RootOf}\left({x}^{2}-2\right)\right):$
 > $\mathrm{evala}\left(\mathrm{Factor}\left({x}^{2}-2,\mathrm{sqrt2}\right)\right)$
 $\left({x}{+}{\mathrm{sqrt2}}\right){}\left({x}{-}{\mathrm{sqrt2}}\right)$ (3)
 > $\mathrm{evala}\left(\mathrm{Factor}\left({x}^{2}-2,\mathrm{sqrt2}\right),\left\{\mathrm{lenstra}\right\}\right)$
 $\left({x}{+}{\mathrm{sqrt2}}\right){}\left({x}{-}{\mathrm{sqrt2}}\right)$ (4)
 > $\mathrm{evala}\left(\mathrm{Factor}\left({x}^{2}-2{y}^{2},\mathrm{sqrt2}\right)\right)$
 $\left({\mathrm{sqrt2}}{}{y}{+}{x}\right){}\left({-}{\mathrm{sqrt2}}{}{y}{+}{x}\right)$ (5)
 > $\mathrm{alias}\left(\mathrm{\beta }=\mathrm{RootOf}\left({y}^{2}-x,y\right)\right):$
 > $\mathrm{evala}\left(\mathrm{Factor}\left(x{y}^{2}-1,\mathrm{\beta }\right)\right)$
 ${x}{}\left({y}{-}\frac{{\mathrm{\beta }}}{{x}}\right){}\left({y}{+}\frac{{\mathrm{\beta }}}{{x}}\right)$ (6)
 > $\mathrm{expand}\left(\left({x}^{3}+{y}^{5}+2\right)\left(x{y}^{2}+3\right)\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}7$
 ${x}{}{{y}}^{{7}}{+}{{x}}^{{4}}{}{{y}}^{{2}}{+}{3}{}{{y}}^{{5}}{+}{3}{}{{x}}^{{3}}{+}{2}{}{x}{}{{y}}^{{2}}{+}{6}$ (7)
 > $\mathrm{Factor}\left(\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}7$
 $\left({{y}}^{{5}}{+}{{x}}^{{3}}{+}{2}\right){}\left({x}{}{{y}}^{{2}}{+}{3}\right)$ (8)
 > $\mathrm{Factor}\left({x}^{2}+2xy+{y}^{2}+1+x+y,\mathrm{\alpha }\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}5$
 $\left({y}{+}{x}{+}{4}{}{\mathrm{\alpha }}\right){}\left({y}{+}{x}{+}{\mathrm{\alpha }}{+}{1}\right)$ (9)
 > $\mathrm{Factor}\left({x}^{2}y+x{y}^{2}+2\mathrm{\alpha }xy+\mathrm{\alpha }{x}^{2}+4\mathrm{\alpha }x+y+\mathrm{\alpha }\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}5$
 $\left({\mathrm{\alpha }}{}{x}{+}{x}{}{y}{+}{1}\right){}\left({y}{+}{x}{+}{\mathrm{\alpha }}\right)$ (10)

References

 Bernardin, Laurent, and Monagan, Michael B., "Efficient Multivariate Factorization over Finite Fields." In Proceedings of AAECC '97, pp. 15-28. Edited by Teo Mora and Harold F. Mattson. Springer, 1997.
 Lenstra, A. K., "Lattices and Factorization of Polynomials over Algebraic Number Fields." In Proceedings of EUROCAM '82, pp. 32-39. Edited by Jacques Calmet. Springer, 1982.