This site is supported by donations to The OEIS Foundation.



Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
(Formerly M0678 N0250)
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 (list; graph; refs; listen; history; text; internal format)



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]


Kurita, Yoshiharu and Matsumoto, Makoto; Primitive t-nomials (t=3,5) over GF(2) whose degree is a Mersenne exponent <= 44497. Math. Comp. 56 (1991), no. 194, 817-821.

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).

N. Zierler, On x^n+x+1 over GF(2). Information and Control 16 1970 502-505.

N. Zierler, Primitive trinomials whose degree is a Mersenne exponent. Information and Control 15 1969 67-69.

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.


Table of n, a(n) for n=1..30.

Joerg Arndt, Matters Computational (The Fxtbook), see p.850 (but note errata for statement of Swan's theorem).

R. P. Brent, Searching for primitive trinomials (mod 2)

R. P. Brent, Trinomial Log Files and Certificates

R. P. Brent, Tables of trinomials (outdated)

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).

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).

Index entries for sequences related to trinomials over GF(2)


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

For smallest values of k, see A074743.

Sequence in context: A103383 A103382 A143027 * A141453 A100532 A231480

Adjacent sequences:  A001150 A001151 A001152 * A001154 A001155 A001156




N. J. A. Sloane.


Corrected and extended by Paul Zimmermann, Sep 05 2002.

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



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 28 15:24 EST 2014. Contains 250363 sequences.