Irreducible polynomials over
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.
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.