A316970 Reducible binary polynomials P of degree n>0 with P dividing the polynomial X^(2^n-1)+1, evaluated at X=2 (pseudo-primes in the ring GF(2)[X]).

83, 101, 127, 279, 443, 465, 1137, 1207, 1219, 1395, 1453, 1503, 1547, 1561, 1653, 1667, 1787, 1897, 1903, 1975, 2013, 4111, 4169, 4191, 4231, 4255, 4377, 4415, 4445, 4585, 4599, 4673, 4681, 4699, 4763, 4779, 4819, 4849, 4867, 4881, 4895, 4917, 5013, 5021, 5113, 5167, 5173, 5187, 5207, 5339, 5389, 5433, 5447

Offset

1,1

Comments

If a binary polynomial P of degree n is irreducible, then demonstrably P divides the polynomial X^(2^n-1)+1.

All irreducible polynomials A014580 pass this test, requiring O(n^3) bit operations and O(n) bits with classical algorithms.

Polynomials which pass this test but are not irreducible form the sequence.

Analog for GF(2)[X] of Fermat pseudoprimes A001567.

When P includes the constant term 1 (as all primitive polynomials do), the test is equivalent to X^(2^n)=X(mod P), which is easier to compute.

Links

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

Francois R. Grieu, Test of irreducibility of a binary polynomial, Math StackExchange July 2018.

Index entries for sequences related to polynomials in ring GF(2)[X]

Example

83, that is 1010011 in binary, represents the polynomial P(X)=X^6+X^4+X+1 of degree n=6. It is in the sequence because X^63+1 == 0 (mod P), and P is reducible since P(X)=(X+1)(X^2+X+1)(X^3+X+1) in GF(2)[X].

Mathematica

For[p=3, p<5449, p+=2, P=0; Y=1; m=p; While[m>0, If[OddQ[m], P+=Y; m-=1]; Y*=x; m/=2]; If[PolynomialRemainder[x^(2^Exponent[P, x]-1), P, x, Modulus->2]==1&&!IrreduciblePolynomialQ[P, Modulus->2], Print[p]]]

Crossrefs

Cf. A014580. Subsequence of A091242.

Sequence in context: A158719 A160028 A115258 * A139965 A180523 A139765

Adjacent sequences: A316967 A316968 A316969 * A316971 A316972 A316973

Keyword

nonn

Author

Francois R. Grieu, Jul 17 2018

Status

approved