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.



Minimum Growth Rate of Hamming Weight of Multiples of Primitive Polynomials
Scratch the use of the parity check matrix. Combine Felipe's idea with a counting argument similar to the scratched solution.


Assume $n\ge4.$ Let $\alpha$ be a root of $f(x)$. The set $P=\{ \alpha^i\mid n+2\lt i\lt N \}$ contains $N-n-3\ge 8$ distinct elements of the field $GF(2^n)$. Therefore it must intersect non-trivially with the set $S=\{ 1+\alpha^i\mid 0\lt i\lt 2^n-1\}=GF(2^n)\setminus\{0,1\} $. So $\alpha^j=1+\alpha^i$ for some $i,j, j\ge n+2$ The trinomial $p(x)=1+x^i+x^j$ is thus divisible by $f(x)$, and the degree of the quotient $a(x)=p(x)/f(x)$ is in the prescribed range. Therefore $W\_{min}(f)=3$ for all primitive polynomials $f$. The case $n=3$ can be checked easily, and the same conclusion holds.


