Let $F_2[x]$ denote the ring of polynomials over the field of 2 elements.

Richard Brent has a page on finding primitive trinomials in $F_2[x]$ of huge degree at http://maths.anu.edu.au/~brent/trinom.html.

My problem is different, I want to find primitive polynomials none of whose multiples--which are of course not primitive--are low weight.

Let the Hamming weight $W(f)$ of a polynomial $f \in F_2[x]$ be the number of nonzero coefficients it has, so a trinomial has Hamming weight 3. Let $P_n$ be the set of primitive polynomials in $F_2[x]$ of degree $n$. Let $N=2^n-1.$ For $f \in P_n$ let

$W_{min}(f)=\min ( W( f(x) a(x))~:~deg(a) \in [2,2^n-n-1] ).$

For each $n\geq 3$ let $W_n=\max ( W_{min}(f): f \in P_n ).$ Is anything known about the growth rate of $W_n$?

Essentially, $W_n$ represents how good the best possible primitive polynomial of degree $n$ is. The application is to cryptosystems which use primitive LFSRs as components. If there is a low weight multiple [lowest possible weight being 3] then there are linear parity checks between output bits that can be exploited for an attack.

There is related work [Blake, Gao, Lambert: "Construction and Distribution Properties for Irreducible Trinomials over Finite Fields", 1994 Finite Fields and Applications Conference, see citeseer] which shows that given $n$ there are $1\leq k < m \leq 2^n-1,$ such that $\gcd(x^m+x^k+1,x^{2^n-1}+1)=h(x)$ for some $h(x) \in P_n$. In fact, experimentally, for $n$ up to 500, $m$ is not much larger than $n$ in most cases.