A132448 -id:A132448 - cp's OEIS frontend

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

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

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

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

A132454 First primitive GF(2)[X] polynomials of degree n and minimal number of terms, expressed as -k for X^n+X^k+1, else with X^n suppressed.

Original entry on oeis.org

1, -1, -1, -1, -2, -1, -1, 29, -4, -3, -2, 83, 27, 43, -1, 45, -3, -7, 39, -3, -2, -1, -5, 27, -3, 71, 39, -3, -2, 83, -3, 197, -13, 281, -2, -11, 83

Offset: 1

Francois R. Grieu, Aug 22 2007

More precisely: when there exists k, 0

			a(10)=-3, representing the GF(2)[X] polynomial X^10+X^3+1, because this degree 10 trinomial is primitive, contrary to X^10+X^1+1, X^10+X^2+1 and X^10+X^2+X^1.

Either of 2^n+2^(-a(n))+1 or 2^n+a(n) belongs to A091250. If there exists m such that n = A073726(m), then a(n) = -A074744(m); otherwise a(n) = A132450(n). A132453(n) gives the primitive polynomial corresponding to a(n). Cf. A132448, similar, with no restriction on number of terms. Cf. A132450, similar, with restriction to at most 5 terms. Cf. A132452, similar, with restriction to exactly 5 terms.

Showing 1-4 of 4 results.

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A132454 First primitive GF(2)[X] polynomials of degree n and minimal number of terms, expressed as -k for X^n+X^k+1, else with X^n suppressed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs