

A316970


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


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

If a binary polynomial P of degree n is irreducible, then demonstrably P divides the polynomial X^(2^n1)+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



