indicates that
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
indicates that
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
In our log files, the sieving limit varies. It is at least log2r, and usually about log2r + 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:
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 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
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 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:
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 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.