|
%I #22 Aug 23 2018 17:13:48
%S 83,101,127,279,443,465,1137,1207,1219,1395,1453,1503,1547,1561,1653,
%T 1667,1787,1897,1903,1975,2013,4111,4169,4191,4231,4255,4377,4415,
%U 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
%N 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]).
%C If a binary polynomial P of degree n is irreducible, then demonstrably P divides the polynomial X^(2^n-1)+1.
%C All irreducible polynomials A014580 pass this test, requiring O(n^3) bit operations and O(n) bits with classical algorithms.
%C Polynomials which pass this test but are not irreducible form the sequence.
%C Analog for GF(2)[X] of Fermat pseudoprimes A001567.
%C 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.
%H Francois R. Grieu, <a href="https://math.stackexchange.com/q/2855547/35016">Test of irreducibility of a binary polynomial</a>, Math StackExchange July 2018.
%H <a href="/index/Ge#GF2X">Index entries for sequences related to polynomials in ring GF(2)[X]</a>
%e 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].
%t 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]]]
%Y Cf. A014580. Subsequence of A091242.
%K nonn
%O 1,1
%A _Francois R. Grieu_, Jul 17 2018
|
