indicates that

is divisible by a factor of degree 25.
This can be verified by computing the GCD of T(*x*) and
*x ^{E} + x*, where

The entry

indicates that

is reducible, and the low-order 32 terms of
*x ^{E}* 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

In our log files, the sieving limit varies. It is at least
log_{2}*r*,
and usually about
log_{2}*r* + 4.

Finally, the entry

indicates that

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:

- We use it for bookkeeping, to keep track of which values of
*s*have already been checked. - Anyone who wishes to check our results can select entries at random from the log file and verify them.

The extended format includes entries of the form

or

or (in some old files)

or (if the search for this degree is incomplete)

where *f* is a hexadecimal encoding of an irreducible factor
F(*x*) of degree *d*,
"p" indicates a factor of the trinomial
*x*^{r} + *x*^{s} + 1,
and "q" indicates a factor of the reciprocal trinomial
*x*^{r} + *x*^{r-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

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

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

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

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

- 127 full (1 KB), extended (1 KB)
- 521 full (1 KB), extended (2 KB)
- 607 full (2 KB), extended (2 KB),
- 1279 full (3 KB), extended (3 KB)
- 2281 full (4 KB), extended (6 KB)
- 3217 full (6 KB), extended (8 KB)
- 4423 full (8 KB), extended (11 KB)
- 9689 full (18 KB), extended (25 KB)
- 19937 full (37 KB), extended (52 KB)
- 23209 full (40KB), extended (61 KB)
- 44497 full (77 KB), extended (136 KB)
- 110503 full (186 KB), extended (328 KB), degrees (28 KB)
- 132049 full (222 KB), extended (408 KB), degrees (33 KB)
- 756839 full (1.23 MB), extended (2.38 MB), degrees (200 KB)
- 859433 full (1.40 MB), extended (2.74 MB), degrees (224 KB)
- 3021377 full (4.93 MB), extended (10.1 MB), degrees (748 KB)
- 6972593 full (11.7 MB), extended (24.27 MB), degrees (1.76 MB)
- 24036583 extended (88 MB), degrees (6 MB)
- 25964951 extended (92 MB), degrees (6 MB)
- 30402457 extended (110 MB), degrees (8 MB)
- 32582657 extended (122 MB), degrees (8 MB)
- 42643801 extended (155 MB), degrees (11 MB)
- 43112609 extended (154 MB), degrees (11 MB)
- 57885161 extended (208 MB) degrees (15 MB)
- 74207281 extended (265 MB)

indicating which trinomials

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
*x ^{E}* mod T(

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.

- 2203 full (6 KB)
- 4253 full (41 KB)
- 9941 full (27 KB)
- 11213 full (75 KB)
- 21701 full (58 KB)
- 86243 full (134 KB)
- 216091 abbreviated (124 KB)
- 1257787 abbreviated (114 KB)
- 1398269 abbreviated (420 KB)
- 2976221 abbreviated (1416 KB)

Last revised 4 August 2013