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

Author

Francois R. Grieu, Jul 17 2018

Keywords

• nonn

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.

Examples

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

Links

• 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]

Crossrefs

Cf. A014580. Subsequence of A091242.

Programs

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]]]