Exhaustive
 Index
 LowSubDeg
 Primitive
 PrimitiveTri
 Tables
 Trinomials

Irreducible polynomials over GF(2) with lowest subdegree

The form of these polynomials is P(x)=xd+f(x) with f(x) a polynomial of small degree. For a given degree d, the given polynomial is those of smallest sub-degree deg(f(x)). These irreducible polynomials can be displayed in Maple format to allow easy check. The following table gives the first occurence of a sub-degree as d increases.

 sub-degree 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 degree 2 5 - 8 14 - 32 85 149 256 467 768 1532 2996 4759 ??

That means for instance that there exists irreducible polynomials of sub-degree less than 14 for all degrees up to degree 2995 and that there is no such polynomial for degree 2996.

On october 2nd 2008, in an effort to completely cover the range 4000 to 6000, I found that the smallest degree whose subdegree is 15 is 4759. This is by far less than the conjecture I made 8 years ago which was degree 5969. With the computers of that time, it was the smallest degree I have found whose sub-degree was 15 starting around degree 6000. This conjecture was based on the observation that the smallest degree was roughly doubling with the subdegree. It appears today that for degrees less than 6000, eight values have a sub-degree of 15: 4759, 4800, 5187, 5197, 5312, 5838, 5875 and 5969.

Please select range to display irreducible polynomials over GF(2) of lowest subdegree.
 first degree last degree Output format: HTML Maple LaTeX
 Exhaustive
 Index
 LowSubDeg
 Primitive
 PrimitiveTri
 Tables
 Trinomials

Florent Chabaud
E-mail: florent.chabaud@m4x.org
GPG key: