The Program irred
irred is a program which searches for irreducible trinomials
xr + xs + 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
hardware available on such machines
(Pentium II, Pentium III etc). The MMX code is
significantly faster than the pure C code.
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
Nate Begeman has ported
irred version 3.11 to Motorola's
ISA extension to the PowerPC,
which is found in all "G4" machines shipped by Apple Computer. This runs
(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
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 2r - 1.
it is known that 2r - 1 is a
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.
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