A091250 -id:A091250 - cp's OEIS frontend

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375

Offset: 1

David Petry (petry(AT)accessone.com)

nonn

Or, binary irreducible polynomials, interpreted as binary vectors, then written in base 10.
The numbers {a(n)} are a subset of the set {A206074}. - Thomas Ordowski, Feb 21 2014
2^n - 1 is a term if and only if n = 2 or n is a prime and 2 is a primitive root modulo n. - Jianing Song, May 10 2021
For odd k, k is a term if and only if binary_reverse(k) = A145341((k+1)/2) is. - Joerg Arndt and Jianing Song, May 10 2021

			x^4 + x^3 + 1 -> 16+8+1 = 25. Or, x^4 + x^3 + 1 -> 11001 (binary) = 25 (decimal).

A.H.M. Smeets, Table of n, a(n) for n = 1..20000 (first 1377 terms from T. D. Noe)
Index entries for sequences operating on GF(2)[X]-polynomials

Written in binary: A058943.
Number of degree-n irreducible polynomials: A001037, see also A000031.
Multiplication table: A048720.
Characteristic function: A091225. Inverse: A091227. a(n) = A091202(A000040(n)). Almost complement of A091242. Union of A091206 & A091214 and also of A091250 & A091252. First differences: A091223. Apart from a(1) and a(2), a subsequence of A092246 and hence A000069.
Table of irreducible factors of n: A256170.
Irreducible polynomials satisfying particular conditions: A071642, A132447, A132449, A132453, A162570.
Factorization sentinel: A278239.
Sequences analyzing the difference between factorization into GF(2)[X] irreducibles and ordinary prime factorization of the corresponding integer: A234741, A234742, A235032, A235033, A235034, A235035, A235040, A236850, A325386, A325559, A325560, A325563, A325641, A325642, A325643.
Factorization-preserving isomorphisms: A091203, A091204, A235041, A235042.
See A115871 for sequences related to cross-domain congruences.
Functions based on the irreducibles: A305421, A305422.

fQ[n_] := Block[{ply = Plus @@ (Reverse@ IntegerDigits[n, 2] x^Range[0, Floor@ Log2@ n])}, ply == Factor[ply, Modulus -> 2] && n != 2^Floor@ Log2@ n]; fQ[2] = True; Select[ Range@ 378, fQ] (* Robert G. Wilson v, Aug 12 2011 *)
Reap[Do[If[IrreduciblePolynomialQ[IntegerDigits[n, 2] . x^Reverse[Range[0, Floor[Log[2, n]]]], Modulus -> 2], Sow[n]], {n, 2, 1000}]][[2, 1]] (* Jean-François Alcover, Nov 21 2016 *)

is(n)=polisirreducible(Pol(binary(n))*Mod(1,2)) \\ Charles R Greathouse IV, Mar 22 2013

A058947 Coefficients of primitive irreducible polynomials over GF(2) listed in lexicographic order.

Original entry on oeis.org

11, 111, 1011, 1101, 10011, 11001, 100101, 101001, 101111, 110111, 111011, 111101, 1000011, 1011011, 1100001, 1100111, 1101101, 1110011, 10000011, 10001001, 10001111, 10010001, 10011101, 10100111, 10101011

Offset: 1

N. J. A. Sloane, Jan 13 2001

Church's table extends through degree 11.

			The first few are x+1; x^2+x+1; x^3+x+1, x^3+x^2+1; ... Note that x is irreducible but not primitive.

T. D. Noe, Table of n, a(n) for n=1..1110 (through degree 13)
R. Church, Tables of irreducible polynomials for the first four prime moduli, Annals Math., 36 (1935), 198-209.
F. Ruskey, Irreducible and Primitive Polynomials over GF(2)
Index entries for sequences containing GF(2)[X]-polynomials

Cf. A000020, A001037, A011260, A058943, A058944, A058945, A058946, A058948.
Irreducible over GF(2), GF(3), GF(4), GF(5), GF(7): A058943, A058944, A058948, A058945, A058946.
Primitive irreducible over GF(2), GF(3), GF(4), GF(5), GF(7): A058947, A058949, A058952, A058950, A058951.
a(n) = A007088(A091250(n)).

car = 2; maxDegree = 13;
okQ[{1, 1}] = True;
okQ[coefs_List] := Module[{P}, P = coefs.x^Range[Length[coefs]-1, 0, -1]; coefs[[1]] == 1 && IrreduciblePolynomialQ[P, Modulus -> car] && PrimitivePolynomialQ[P, car]];
FromDigits /@ Select[Table[IntegerDigits[k, car], {k, car+1, car^(maxDegree + 1)}], okQ] (* Jean-François Alcover, Sep 09 2019 *)

A132447 First primitive GF(2)[X] polynomial of degree n.

Original entry on oeis.org

3, 7, 11, 19, 37, 67, 131, 285, 529, 1033, 2053, 4179, 8219, 16427, 32771, 65581, 131081, 262183, 524327, 1048585, 2097157, 4194307, 8388641, 16777243, 33554441, 67108935, 134217767, 268435465, 536870917, 1073741907, 2147483657

Offset: 1

Francois R. Grieu, Aug 22 2007

nonn

			a(5)=37, or 100101 in binary, representing the GF(2)[X] polynomial X^5+X^2+1, because it has degree 5 and is primitive, contrary to X^5, X^5+1, X^5+x^1, X^5+X^1+1 and X^5+X^2.

Robert Israel, Table of n, a(n) for n = 1..330
Rich Schroeppel, Hasty Pudding Cipher Specification on archive.org, (revised May 1999 ed.), June 1998. (The numbers are called "Swizpoly numbers" here, except that they start with 0 for some reason.)
Index entries for sequences operating on GF(2)[X]-polynomials

a(n) is the smallest member of A091250 at least 2^n. A132448(n) = a(n)-2^n, giving a more compact representation. Cf. A132449, similar, with restriction to at most 5 terms. Cf. A132451, similar, with restriction to exactly 5 terms. Cf. A132453, similar, with restriction to minimal number of terms.

f:= proc(n) local k,L,i,X;
   for k from 2^n+1 by 2 do
     L:= convert(k,base,2);
     if Primitive(add(L[i]*X^(i-1),i=1..n+1)) mod 2 then return k fi
   od
end proc:
map(f, [$1..40]); # Robert Israel, Nov 05 2023

f[n_] := If[n == 1, 3, Module[{k, L, i, X}, For[k = 2^n+1, True, k = k+2, L = IntegerDigits[k, 2]; If[PrimitivePolynomialQ[Sum[L[[i]]*X^(i-1), {i, 1, n+1}], 2], Return[k]]]]];
Table[f[n], {n, 1, 40}] (* Jean-François Alcover, Mar 29 2024, after Robert Israel *)

A132448 First primitive polynomial over GF(2) of degree n, X^n suppressed.

Original entry on oeis.org

1, 3, 3, 3, 5, 3, 3, 29, 17, 9, 5, 83, 27, 43, 3, 45, 9, 39, 39, 9, 5, 3, 33, 27, 9, 71, 39, 9, 5, 83, 9, 175, 83, 231, 5, 119, 63, 99, 17, 57, 9, 63, 89, 101, 27, 303, 33, 183, 113, 29, 75, 9, 71, 125, 71, 149, 45, 99, 123, 3, 39, 105, 3, 27, 27, 365, 39, 163

Offset: 1

Francois R. Grieu, Aug 22 2007

nonn

More precisely: minimum value for X=2 of polynomials P[X] with coefficients in GF(2) such that X^n+P[X] is primitive. Applications include maximum-length linear feedback shift registers with efficient implementation in software.

			a(11)=5, or 101 in binary, representing the GF(2)[X] polynomial X^2+1, because X^11+X^2+1 is primitive, contrary to X^11, X^11+1, X^11+X^1, X^11+X^1+1 and X^11+X^2.

Francois R. Grieu, Table of n, a(n) for n = 1..400 (using Joerg Arndt's table).
Joerg Arndt, Binary primitive polynomials with lowest-most possible set bits
Index entries for sequences operating on GF(2)[X]-polynomials

2^n+a(n) is the smallest member of A091250 at least 2^n. A132447(n) = a(n)+2^n and gives the corresponding primitive polynomial. Cf. A132450, similar, with restriction to at most 5 terms. Cf. A132452, similar, with restriction to exactly 5 terms. Cf. A132454, similar, with restriction to minimal number of terms.

i2px[i_]:=If[i>1,BitAnd[i,1]+i2px[BitShiftRight[i,1]]x,i ];s={1};For[n=2,n<69,++n,For[i=3,!PrimitivePolynomialQ[i2px[i]+x^n,2],i+=2];AppendTo[s,i]];s (* Francois R. Grieu, Jan 15 2021 *)

More terms from Francois R. Grieu, Jan 12 2021

A132449 First primitive GF(2)[X] polynomial of degree n with at most 5 terms.

Original entry on oeis.org

3, 7, 11, 19, 37, 67, 131, 285, 529, 1033, 2053, 4179, 8219, 16427, 32771, 65581, 131081, 262183, 524327, 1048585, 2097157, 4194307, 8388641, 16777243, 33554441, 67108935, 134217767, 268435465, 536870917, 1073741907, 2147483657

Offset: 1

Francois R. Grieu, Aug 22 2007

nonn

More precisely: minimum value for X=2 of primitive GF(2)[X] polynomials of degree n with at most 5 terms. Applications include maximum-length linear feedback shift registers with efficient implementation in both hardware and software. The limitation to 5 terms occurs first for a(32), which is 4294967493 representing X^32+X^7+X^6+X^2+1, rather than 4294967471 representing X^32+X^7+X^5+X^3+X^2+X^1+1. Proof is needed that there exists a primitive GF(2)[X] polynomial P[X] of degree n and at most 5 terms for all positive n.

			a(5)=37, or 100101 in binary, representing the GF(2)[X] polynomial X^5+X^2+1, because it has degree 5 and no more than 5 terms and is primitive, contrary to X^5, X^5+1, X^5+X^1, X^5+X^1+1 and X^5+X^2.

Index entries for sequences operating on GF(2)[X]-polynomials

Subset of A091250. A132450(n) = a(n)-2^n, giving a more compact representation. Cf. A132447, similar, with no restriction on number of terms. Cf. A132451, similar, with restriction to exactly 5 terms. Cf. A132453, similar, with restriction to minimal number of terms.

A132452 First primitive GF(2)[X] polynomials of degree n with exactly 5 terms, X^n suppressed.

Original entry on oeis.org

15, 27, 15, 29, 27, 27, 23, 83, 27, 43, 23, 45, 15, 39, 39, 83, 39, 57, 43, 27, 15, 71, 39, 83, 23, 83, 15, 197, 83, 281, 387, 387, 83, 99, 147, 57, 15, 153, 89, 101, 27, 449, 51, 657, 113, 29, 75, 75, 71, 329, 71, 149, 45, 99, 149, 53, 39, 105, 51, 27, 27, 833, 39, 163, 101, 43, 43, 1545, 29

Offset: 5

Francois R. Grieu, Aug 22 2007

nonn

More precisely: minimum value for X=2 of GF(2)[X] polynomials P[X] of degree less than n and exactly 4 terms such that X^n+P[X] is primitive.
Applications include maximum-length linear feedback shift registers with efficient implementation in both hardware and software.
Proof is needed that there exists a primitive GF(2)[X] polynomial P[X] of degree n and exactly 5 terms for all n>4.

			a(11)=23, or 10111 in binary, representing the GF(2)[X] polynomial X^4+X^2+X^1+1, because X^11+X^4+X^2+X^1+1 has exactly 5 terms and it is primitive, contrary to X^11+X^3+X^2+X^1+1.

For n>4, 2^n+a(n) belongs to A091250. A132451(n) = a(n)+2^n and gives the corresponding primitive polynomial. Cf. A132448, similar, with no restriction on number of terms. Cf. A132450, similar, with restriction to at most 5 terms. Cf. A132454, similar, with restriction to minimal number of terms.

Edited and extended by Max Alekseyev, Feb 06 2010

A132453 First primitive GF(2)[X] polynomial of degree n and minimal number of terms.

Original entry on oeis.org

3, 7, 11, 19, 37, 67, 131, 285, 529, 1033, 2053, 4179, 8219, 16427, 32771, 65581, 131081, 262273, 524327, 1048585, 2097157, 4194307, 8388641, 16777243, 33554441, 67108935, 134217767, 268435465, 536870917, 1073741907, 2147483657

Offset: 1

Francois R. Grieu, Aug 22 2007

nonn

More precisely: minimum value for X=2 of primitive GF(2)[X] polynomials of degree n and minimal number of terms for such polynomials. Applications include maximum-length linear feedback shift registers with efficient implementation in both hardware and software.

			a(10)=1033, or 10000001001 in binary, representing the GF(2)[X] polynomial X^10+X^3+1, because this polynomial has degree 10, it has 3 terms and no degree 10 polynomial with less terms than that is primitive and it is primitive, contrary to X^10+X^1+1, X^10+X^2+1 and X^10+X^2+X^1.

Subset of A091250. A132454(n) encodes a(n) in a more compact representation. Cf. A132447, similar, with no restriction on number of terms. Cf. A132449, similar, with restriction to at most 5 terms. Cf. A132451, similar, with restriction to exactly 5 terms.

A091252 Nonprimitive irreducible polynomials over GF(2).

Original entry on oeis.org

2, 31, 73, 87, 117, 283, 313, 319, 375, 379, 395, 415, 419, 433, 445, 471, 477, 499, 505, 515, 535, 587, 613, 665, 769, 841, 929

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

a(n) = A014580(A091251(n)). Cf. A091250. In binary format: A091253.

A132450 First primitive GF(2)[X] polynomials of degree n with at most 5 terms, X^n suppressed.

Original entry on oeis.org

1, 3, 3, 3, 5, 3, 3, 29, 17, 9, 5, 83, 27, 43, 3, 45, 9, 39, 39, 9, 5, 3, 33, 27, 9, 71, 39, 9, 5, 83, 9, 197, 83, 281, 5, 387, 83

Offset: 1

Francois R. Grieu, Aug 22 2007

More precisely: minimum value for X=2 of GF(2)[X] polynomials P[X] with at most 4 terms such that X^n+P[X] is primitive. Applications include maximum-length linear feedback shift registers with efficient implementation in both hardware and software. The limitation of the number of terms occurs first for a(32), which is 197 representing X^7+X^6+X^2+1, rather than 175 representing X^7+X^5+X^3+X^2+X^1+1. Proof is needed that there exists a primitive GF(2)[X] polynomial P[X] of degree n and at most 5 terms for all positive n.

			a(11)=5, or 101 in binary, representing the GF(2)[X] polynomial X^2+1, because X^11+X^2+1 has no more than 5 terms and X is primitive, contrary to X^11, X^11+1, X^11+X^1, X^11+X^1+1 and X^11+X^2.

Index entries for sequences operating on GF(2)[X]-polynomials

2^n+a(n) belongs to A091250. A132449(n) = a(n)+2^n and gives the corresponding primitive polynomial. Cf. A132448 (similar, with no restriction on number of terms). Cf. A132452 (similar, with restriction to exactly 5 terms).

A132451 First primitive GF(2)[X] polynomials of degree n with exactly 5 terms.

Original entry on oeis.org

0, 0, 0, 0, 47, 91, 143, 285, 539, 1051, 2071, 4179, 8219, 16427, 32791, 65581, 131087, 262183, 524327, 1048659, 2097191, 4194361, 8388651, 16777243, 33554447, 67108935, 134217767, 268435539, 536870935, 1073741907, 2147483663

Offset: 1

Francois R. Grieu (f(AT)grieu.com), Aug 22 2007

nonn

More precisely: minimum value for X=2 of primitive GF(2)[X] polynomials of degree n with exactly 5 terms, or 0 if no such polynomial exists. Applications include maximum-length linear feedback shift registers with efficient implementation in both hardware and software. Proof is needed that there exists a primitive GF(2)[X] polynomial P[X] of degree n and exactly 5 terms for all n>4.

			a(6)=91, or 1011011 in binary, representing the GF(2)[X] polynomial X^6+X^4+X^3+X^1+1, because it has degree 6 and exactly 5 terms and is primitive, contrary to X^6+X^3+X^2+X^1+1 and X^6+X^4+X^2+X^1+1.

Index entries for sequences operating on GF(2)[X]-polynomials

For n>4, a(n) belongs to A091250. A132452(n) = a(n)-2^n, giving a more compact representation. Cf. A132447, similar, with no restriction on number of terms. Cf. A132449, similar, with restriction to a most 5 terms. Cf. A132453, similar, with restriction to minimal number of terms.

cp's OEIS Frontend

A014580 Binary irreducible polynomials (primes in the ring GF(2)[X]), evaluated at X=2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A058947 Coefficients of primitive irreducible polynomials over GF(2) listed in lexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A132447 First primitive GF(2)[X] polynomial of degree n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A132448 First primitive polynomial over GF(2) of degree n, X^n suppressed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A132449 First primitive GF(2)[X] polynomial of degree n with at most 5 terms.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A132452 First primitive GF(2)[X] polynomials of degree n with exactly 5 terms, X^n suppressed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A132453 First primitive GF(2)[X] polynomial of degree n and minimal number of terms.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A091252 Nonprimitive irreducible polynomials over GF(2).

Views

Author

Keywords

Links

Crossrefs

A132450 First primitive GF(2)[X] polynomials of degree n with at most 5 terms, X^n suppressed.

Views

Author

Keywords

Comments

Examples