This interactive page has been made possible by the consent
of Waterloo Maple. The current version of the program are written using
Maple 8 and are being run on a SUN Ultra 1 workstation
(using solaris 2.5.1) in the
University of South Carolina.
We express our gratitude to the staff
of Waterloo Maple who graciously aided in improvements to the interface.
A Maplet interface to the algorithms is currently under development.
The current version can be accessed via our
server at the URL
If you experience any problems with this Maplet, please send e-mail to
This page is set-up to test the irreducibility of polynomials f(x)
having each coefficient 0 or 1.
To use this page, begin by selecting one of the
following three tests under "Test to be conducted".
(Click and drag to your choice of tests.)
irreduc01: This is the main program on the page. It determines
whether a given 0-1 polynomial f(x) is irreducible. The program works
best for lacunary polynomials. In particular, the more non-zero terms the
polynomial has, the slower the performance. On the other hand, the degree
of f(x) can be somewhat large. The program can easily handle a 0-1 polynomial
of degree 20000 having say 50 non-zero terms (this typically takes between 2
and 2.5 MAPLE CPU minutes).
irreduc and irreduc01: The program irreduc is MAPLE's
built-in irreducibility test, and this selection does as it suggests.
It checks the irreducibility of f(x) using both algorithms, outputs
the results, and indicates the time it took to do each computation.
Due to the use of irreduc,
this test is only feasible to use when f(x) has relatively small degree;
you will probably not want to wait for the results if f(x) has degree 1000
This option is included for comparison purposes.
To clarify, however, we emphasize that MAPLE's irreduc is an irreducibility
test for general polynomials f(x); irreduc01 is written specifically
to handle 0-1 polynomials and nothing more.
irreduc01NR: This is the main subprogram of irreduc01. It does
not test the irreducibility of f(x) but instead tests the irreducibility of
the non-reciprocal part of f(x). The non-reciprocal part of f(x)
is defined as follows. A polynomial f(x) having coefficients 0 and 1
is said to be reciprocal
if f(x) = xdeg f f(1/x).
The non-reciprocal part of f(x) is f(x) with
its reciprocal irreducible factors having positive leading coefficient
removed. For typical polynomials, one can expect that f(x)
and its non-reciprocal part are the same (this, however, is not really
the case when one considers 0-1 polynomials with a limited number
of non-zero terms). This program runs exceptionally well for lacunary
polynomials with not too many non-zero terms. One can even try f(x)
of degree 10100 if one wants here, though the program does take
slightly longer as the degree of f(x) increases.
After selecting the test to be conducted, you have an option of typing
in a polynomial of your choice or testing a random polynomial. For
the former, choose the "user-specified" option and type in the polynomial
following the example indicated . For the latter, choose the
"randomly-selected" option and indicate the number of non-zero terms
and a bound on the degree. The random polynomial will appear after
the program is run in the displayed output. To clarify, the random polynomial
will have constant term 1 (if you want to test the irreducibility of polynomials
divisible by x, you will have to use the user-specified option) and the remaining
exponents will be determined randomly less than or equal to the bound given
for the degree. If two identical exponents are selected at random, the
random polynomial will have fewer non-zero terms than you have indicated
(only one term for each exponent is used). The random polynomial options
will not affect the field containing the user-defined polynomial. After
making the above choices, choose "Perform Test" and wait for the results
or choose "Reset Form" and start again.
The main theorem of Schinzel in  (also see ) implies that it is possible
to determine whether the non-reciprocal part (see definition above) of a
polynomial f(x) is irreducible in running time that depends only logarithmically on the
degree of f(x). For this result, f(x) can have arbitrary integer coefficients.
The running time of such an algorithm may however depend poorly on the
Euclidean norm of f(x) or the number of non-zero terms of f(x).
The programs irreduc01 and irreduc01NR represent joint work by
Michael Filaseta and
Douglas Meade (see ). The algorithms are partially
based on work in  (which itself is based on work of Ljunggren  and
the forementioned work of Schinzel )
and will be described in further detail in a forthcoming
paper that will be made available at this site. Though running versions
of the programs apparently exist, further improvements are being pursued
prior to public release of the code.
We are also in the process of altering
the code so that if the proper infolevel is set in the downloaded version,
then a non-trivial factor is given for any reducible f(x).
When the programs are
complete, we will make them available to download at this location.
As we are using the MAPLE language, access to MAPLE will be
necessary to run the downloaded programs.
The following includes the current references and downloadable programs.
Presently there are no downloads. More will be listed as it
becomes available (and complete).
 M. Filaseta and Douglas Meade,
Irreducibility testing of lacunary 0,1-polynomials,
 M. Filaseta,
On the Factorization of Polynomials with Small Euclidean Norm,
 W. Ljunggren,
On the irreducibility of certain trinomials and quadrinomials,
Math. Scand., 8 (1960), 65-70.
 A. Schinzel,
Reducibility of lacunary polynomials I,
Acta Arith., 16 (1969/70), 123-159.
Another Interactive Page:
Determine if a Polynomial has a Cyclotomic Factor