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