# The Program *irred*

*irred* is a program which searches for irreducible trinomials
*x*^{r} + x^{s} + 1
of prime degree *r* over the finite field GF(2).
It is written in C
and runs under Linux, Solaris or other flavours of Unix
(not yet Windows).
There are optional assembler routines for IBM PCs
to take advantage of the
MMX
hardware available on such machines
(Pentium II, Pentium III etc). The MMX code is
significantly faster than the pure C code.

### Availability

*irred* is available (free, but with absolutely no warranty)
as open-source software under the
GNU General Public License.
A gzipped tar file of *irred version 3.15* is available
here (41 KB).

The earlier versions *1.35* and *1.50* are available
here (42 KB). These versions are slower than recent versions, but are
useful if the exponent *s* is
small (see below), and for checking purposes (since they use a different
algorithm).

Nate Begeman has ported
*irred version 3.11* to Motorola's
AltiVec
ISA extension to the PowerPC,
which is found in all "G4" machines shipped by Apple Computer. This runs
* extremely * fast
(more than three times as fast as a 1GHz Athlon running the MMX code),
so if you have access to a suitable machine you should download
Begeman's code, which is available
here.

### Restrictions on the exponents

Recent versions of *irred* assume
0 < *s* < *r*,
*s* __>__ LIM,
*r* - *s* __>__ LIM,
where LIM = 32, 64 or 256,
depending on the version and compilation options.
These restrictions permit certain loop optimisations.
Early versions (e.g. version 1.35 or version 1.50) can handle the
case *s* < LIM,
and the restriction
*r* - *s* __>__ LIM
can be circumvented by replacing *s* by
*r* - *s*,
provided *r* __>__ 2.LIM.
The case *r* < 2.LIM can be handled by
less efficient programs, or by looking up published tables.

*irred* assumes that *r* is prime - if not then
it performs a necessary (but not sufficient) test for irreducibility.
Recent versions (e.g. version 3.11) give a warning if *r*
is not prime. Earlier versions did not check primality of *r*.

### Results obtained with *irred*

*irred* does not (in general) test primitivity, because this would
require knowledge of the factors of 2^{r} - 1.
However, if
it is known that 2^{r} - 1 is a
Mersenne prime,
then an irreducible trinomial of degree *r* is necessarily
primitive, so *irred* can be used to find primitive trinomials
of very high degree, e.g. 3021377.
More information is available here.

# Note

*irred* is largely obsolete as our
*factor* program is much
faster on average when searching for irreducible trinomials. However,
*irred* is still used for checking irreducibility.
Return to Richard Brent's index page