9.2 Factorization of Polynomials

REDUCE is capable of factorizing univariate and multivariate polynomials that have integer coefficients, finding all factors that also have integer coefficients. The package for doing this was written by Dr. Arthur C. Norman and Ms. P. Mary Ann Moore at The University of Cambridge. It is described in [NM81].

The easiest way to use this facility is to turn on the switch factor, which causes all expressions to be output in a factored form. For example, with factor on, the expression a^2-b^2 is returned as (a+b)*(a-b).

It is also possible to factorize a given expression explicitly. The operator factorize that invokes this facility is used with the syntax

the optional argument of which will be described later. Thus to find and display all factors of the cyclotomic polynomial \(x^{105}-1\), one could write:

    factorize(x^105-1);

The result is a list of factor,exponent pairs. In the above example, there is no overall numerical factor in the result, so the results will consist only of polynomials in x. The number of such polynomials can be found by using the operator length. If there is a numerical factor, as in factorizing \(12x^{2}-12\), the first member of the result will be a list with two elements: the numerical factor and its multiplicity (1). It will however not be factored further. Prime factors of such numbers can be found, using a probabilistic algorithm, by turning on the switch ifactor. For example,

    on ifactor; factorize(12x^2-12);

would result in the output

    {{2,2},{3,1},{x + 1,1},{x - 1,1}}.

If the first argument of factorize is an integer, it will be decomposed into its prime components, whether or not ifactor is on.

Note that the ifactor switch only affects the result of factorize. It has no effect if the factor switch is also on.

The order in which the factors occur in the result (with the exception of a possible overall numerical coefficient which comes first) can be system dependent and should not be relied on. Similarly it should be noted that any pair of individual factors can be negated without altering their product, and that REDUCE may sometimes do that.

The factorizer works by first reducing multivariate problems to univariate ones and then solving the univariate ones modulo small primes. It normally selects both evaluation points and primes using a random number generator that should lead to different detailed behavior each time any particular problem is tackled. If, for some reason, it is known that a certain (probably univariate) factorization can be performed effectively with a known prime, p say, this value of p can be handed to factorize as a second argument. An error will occur if a non-prime is provided to factorize in this manner. It is also an error to specify a prime that divides the discriminant of the polynomial being factored, but users should note that this condition is not checked by the program, so this capability should be used with care.

Factorization can be performed over a number of polynomial coefficient domains in addition to integers. The particular description of the relevant domain should be consulted to see if factorization is supported. For example, the following statements will factorize \(x^{4}+1\) modulo 7:

        setmod 7;
        on modular;
        factorize(x^4+1);

The factorization module is provided with a trace facility that may be useful as a way of monitoring progress on large problems, and of satisfying curiosity about the internal workings of the package. The most simple use of this is enabled by issuing the REDUCE command on trfac; . Following this, all calls to the factorizer will generate informative messages reporting on such things as the reduction of multivariate to univariate cases, the choice of a prime and the reconstruction of full factors from their images. Further levels of detail in the trace are intended mainly for system tuners and for the investigation of suspected bugs. For example, trallfac gives tracing information at all levels of detail. on overview; reduces the amount of detail presented in other forms of trace. Other forms of trace output are enabled by directives of the form

    symbolic set!-trace!-factor(<number>,<filename>);

where useful numbers are 1, 2, 3 and 100, 101, ... . This facility is intended to make it possible to discover in fairly great detail what just some small part of the code has been doing — the numbers refer mainly to depths of recursion when the factorizer calls itself, and to the split between its work forming and factorizing images and reconstructing full factors from these. If nil is used in place of a filename the trace output requested is directed to the standard output stream. After use of this trace facility the generated trace files should be closed by calling

    symbolic close!-trace!-files();

NOTE: Using the factorizer with mcd off will result in an error.

Hosted by