Trinomial Log Files and Certificates

A log file is a list of triples (r, s, status) indicating which trinomials have been tested and the result. For example, the entry

3021377  359  25

indicates that

T(x) = x3021377 + x359 + 1

is divisible by a factor of degree 25. This can be verified by computing the GCD of T(x) and xE + x, where E = 225.

The entry

3021377  375  x78943b98

indicates that

T(x) = x3021377 + x375 + 1

is reducible, and the low-order 32 terms of xE mod T(x), where E = 23021377, are encoded in the 32-bit hexadecimal number 78943b98. (The low-order terms are interesting because, if T is irreducible, then xE = x mod T.)

In some cases, for reasons of efficiency, we tested the reciprocal trinomial (that is, the trinomial with s replaced by r - s). This is indicated by a "y" in the log entry in place of "x". For example, the entry above might be written as

3021377  3021002  y78943b98

In our log files, the sieving limit varies. It is at least log2r, and usually about log2r + 4.

Finally, the entry

3021377 361604 i   or   3021377 361604 irreducible

indicates that

T(x) = x3021377 + x361604 + 1

is irreducible. Sometimes we write "primitive" instead of "irreducible" when r is the exponent of a Mersenne prime, but we rely on the GIMPS project for this information and do not check it ourselves.

A log file has two purposes:

Extended Format of Log Files

So that the log files can provide more information and be more readily checked, we are introducing (from January 2004) an "extended format" in which an irreducible factor (if known) is specified. This "extended log" is also called a "certificate".

The extended format includes entries of the form

s primitive


s d pf

or (in some old files)

s d qf

or (if the search for this degree is incomplete)

s d u

where f is a hexadecimal encoding of an irreducible factor F(x) of degree d, "p" indicates a factor of the trinomial xr + xs + 1, and "q" indicates a factor of the reciprocal trinomial xr + xr-s + 1. "u" indicates unknown status. Note that the degree (r) is (usually) implicit. If d is small, we may omit details of the factor of degree d, since it is easy to find by a small GCD computation.

For example, instead of the "normal" log file entry

6972593 2210949 28

which indicates that the given trinomial has an irreducible factor of degree 28, but is difficult to check without a long GCD computation, we could give an "extended" entry

2210949 28 p1e1af9a5

where "1e1af9a5" is a hexadecimal encoding of the coefficients 11110000110101111100110100101 of the factor

F(x) = x28 + x27 + x26 + x25 + x20 + x19 + x17 + x15 + x14 + x13 + x12 + x11 + x8 + x7 + x5 + x2 + 1.

This is easy to check with NTL or Magma, because it only requires the computation of xr mod F(x) and xs mod F(x), which can be done with O(log r) operations mod F(x).

Some other examples (all for r = 6972593) are:

2209961 50 p58d2b7131cc5f

2221947 89 p396c96a47c19c1d7fb88acf

Log Files

The following log files are relevant to the search for primitive trinomials. In some cases they have been abbreviated by making r implicit and omitting the "trivial" entries (s, k) with k < 10. The files labelled "degrees" contain a list of the degrees of the smallest irreducible factor of each trinomial xr + xs + 1; here r and s are implicit, and s ranges from 1 to (r-1)/2.

For a list of errors discovered in earlier versions of the log files, click here.

"Almost Primitive" Trinomials

In cases where r is a Mersenne exponent but no primitive trinomial of degree r exists, we are searching for trinomials of slightly higher degree r+d which have a primitive factor of degree r. In this case the log files have a slightly different format - they consist of quadruples

(r, d, s, status)

indicating which trinomials

T(x) = xr+d + xs + 1

have been tested. If status is a small integer k it indicates that sieving up to degree k, in combination with Swan's theorem, is sufficient to show that T(x) has no irreducible factor of degree r. (Special case: if k = 1 then T(x) can be ruled out immediately, e.g. by Swan's theorem or because GCD(r+d,s) > 1.) If status is a hexadecimal number of the form x########, where # is a hexadecimal digit in {0..9, a..f}, then T(x) has a small factor F(x) of degree d, or several small factors whose product F(x) has degree d, but the quotient T(x)/F(x) is reducible. The hexadecimal number encodes the low-order 32 terms of xE mod T(x), where E = 2 r f, and f < 2 d is determined by the small factors. (We expect xE = xf mod  T if T/F is irreducible.) Sometimes the hexadecimal number is written as y########, which implies that the reciprocal trinomial was tested (i.e. we replaced s by r+d-s).

The following log files are relevant to the search for almost primitive trinomials. In some cases they have been abbreviated by making r implicit and omitting the "trivial"entries (r, d, s, k) with k <= d. This can make a large difference in the size of the log files, because for some (r, d) all entries are trivial. For example, when r = 216091, all entries with d = 2, 4, or 6 are trivial, and the abbreviated log file has only 20948 entries, versus 1188536 for the full log file.

R. P. Brent (in collaboration with Samuli Larvala, Brendan McKay and Paul Zimmermann)
Last revised 4 August 2013

Return to Richard Brent's index page