Question

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.

Answer 1

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.

Answer 2

$W_{min}(f)$ is independent of $f$. So $W_n$ is just the minimal weight among all polynomials of $P_n$, which is conjectured to be at most $5$. I am not sure what's the best proved upper bound.

Let me show, for example, that if there is trinomial $g=x^n + x^k +1 \in P_n$, then $W_{min}(f)=3$.

Let $\zeta$ be a root of $f$ in an extension field. Then $\zeta^r$ is a root of $g$ for some $r$. Define $u \equiv rn, v \equiv rk \mod N, u,v < N$. Then $\zeta$ is a root of $x^u+x^v+1$, so this polynomial is divisible by $f$ and $W_{min}(f)=3$.

Answer 3

@Jyrki

Thanks, I was going to object that the code wasn't cyclic, but you beat me to it, and gave a very nice answer which works regardless of that fact.