show/hide this revision's text 3 Corrected typo in the example, the new polynomial should be irreducible

Consider unitary polynomials of degree $n$ over $GF(2)$. That is, polynomials of the form $p(x) = \sum_{i=0}^n a_i x^i$ where $a_i\in GF(2)$ and $a_n=1$.

Can we always find such an irreducible polynomial $p(x)$ of degree $n$ where $\textrm{degree}(p(x)-x^n)\leq n/2$?

Example: $p(x)=1+x^2+x^5+x^{400}$ p(x)=1+x^2+x^3+x^5+x^{400}$ is an irreducible polynomial where $\textrm{degree}(p(x)-x^n)=5\leq 400/2$.

Further question: If I assume that $n$ is sufficiently large, say $n\geq 32$, is a tighter bound possible (e.g., $\textrm{degree}(p(x)-x^n)\leq n/4$)?
show/hide this revision's text 2 deleted 4 characters in body

Consider irreducible unitary polynomials of degree $n$ over $GF(2)$. That is, polynomials of the form $p(x) = \sum_{i=0}^n a_i x^i$ where $a_i\in GF(2)$ and $a_n=1$.

Can we always find such an irreducible polynomial $p(x)$ of degree $n$ where $\textrm{degree}(p(x)-x^n)\leq n/2$?

Example: $p(x)=1+x^2+x^5+x^{400}$ is an irreducible polynomial where $\textrm{degree}(p(x)-x^n)=5\leq 400/2$.

Further question: If I assume that $n$ is sufficiently large, say $n\geq 32$, is a tighter bound possible (e.g., $\textrm{degree}(p(x)-x^n)\leq n/4$)?
show/hide this revision's text 1

Can we always find such an irreducible polynomial of degree n where degree(p(x)-x^n)<= n/2?

Consider irreducible polynomials of degree $n$ over $GF(2)$. That is, polynomials of the form $p(x) = \sum_{i=0}^n a_i x^i$ where $a_i\in GF(2)$ and $a_n=1$.

Can we always find such an irreducible polynomial $p(x)$ of degree $n$ where $\textrm{degree}(p(x)-x^n)\leq n/2$?

Example: $p(x)=1+x^2+x^5+x^{400}$ is an irreducible polynomial where $\textrm{degree}(p(x)-x^n)=5\leq 400/2$.

Further question: If I assume that $n$ is sufficiently large, say $n\geq 32$, is a tighter bound possible (e.g., $\textrm{degree}(p(x)-x^n)\leq n/4$)?