A001153 Degrees of primitive irreducible trinomials: n such that 2^n - 1 is a Mersenne prime and x^n + x^k + 1 is a primitive irreducible polynomial over GF(2) for some k with 0 < k < n.

2, 3, 5, 7, 17, 31, 89, 127, 521, 607, 1279, 2281, 3217, 4423, 9689, 19937, 23209, 44497, 110503, 132049, 756839, 859433, 3021377, 6972593, 24036583, 25964951, 30402457, 32582657, 42643801, 43112609

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• hard
• more

Comments

Also the list of "irreducible Mersenne trinomials" since here irreducible implies primitive.

Further terms of the form +-3 (mod 8) are unlikely, as the only possibility of an irreducible trinomial for n == +-3 (mod 8) is (by Swan's theorem) x^n+x^2+1 (and its reciprocal); see the Ciet et al. and the Swan reference. - Joerg Arndt, Jan 06 2014

The first Mersenne prime exponent not ruled out by Swan's theorem and yet not a member of this sequence is 57885161. - Gord Palameta, Jul 20 2018

74207281 is also in the sequence. - Gord Palameta, Jul 20 2018

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Joerg Arndt, Matters Computational (The Fxtbook), see p.850 (but note errata for statement of Swan's theorem).
• Joerg Arndt, Complete list of primitive trinomials over GF(2) up to degree 400.
• Joerg Arndt, Complete list of primitive trinomials over GF(2) up to degree 400 [Cached copy, with permission]
• R. P. Brent, Searching for primitive trinomials (mod 2) (first, "old" page)
• R. P. Brent, Searching for primitive trinomials (mod 2) (second, current page)
• R. P. Brent, Trinomial Log Files and Certificates
• Richard P. Brent and Paul Zimmerman, Twelve New Primitive Binary Trinomials, HAL Id : hal-01378493.
• R. P. Brent, S. Larvala and P. Zimmermann, A fast algorithm for testing reducibility of trinomials ..., Math. Comp. 72 (2003), 1443-1452.
• Mathieu Ciet, Jean-Jacques Quisquater, Francesco Sica, A Short Note on Irreducible Trinomials in Binary Fields, in: 23rd Symposium on Information Theory in the BENELUX, Louvain-la-Neuve, Belgium, Macq, B., Quisquater, J.-J. (eds.), pp.233-234, (May-2002).
• Yoshiharu Kurita and Makoto Matsumoto, Primitive t-nomials (t=3,5) over GF(2) whose degree is a Mersenne exponent <= 44497, Math. Comp. 56 (1991), no. 194, 817-821.
• A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see p. 162.
• Richard G. Swan, Factorization of polynomials over finite fields, Pacific Journal of Mathematics, vol.12, no.3, pp.1099-1106, (1962).
• N. Zierler, Primitive trinomials whose degree is a Mersenne exponent, Information and Control 15 1969 67-69.
• N. Zierler, On x^n+x+1 over GF(2), Information and Control 16 1970 502-505.
• N. Zierler and J. Brillhart, On primitive trinomials (mod 2), Information and Control 13 1968 541-554.
• N. Zierler and J. Brillhart, On primitive trinomials (mod 2), II, Information and Control 14 1969 566-569.
• Index entries for sequences related to trinomials over GF(2)

Crossrefs

Cf. A002475, A000043, A073571, A073639, A057486, A073726.

For smallest values of k, see A074743.

Extensions

Corrected and extended by Paul Zimmermann, Sep 05 2002

Six more terms from Brent's page added by Max Alekseyev, Oct 22 2011