# Minimum Growth Rate of Hamming Weight of Multiples of Primitive Polynomials

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.

-
I find this problem similar to the following: given n odd, find l and k at most n such that n divides 2^l + 2^k + 1. While the arithmetic is different, I would be surprised if in your problem the growth rate is larger than log(n), and I expect more like log(log(n)). But that is a guess on my part. Start by considering x^k mod f and see how few k you need to add up to something with low Hamming weight which is also 0 mod f. Gerhard "Ask Me About System Design" Paseman, 2011.09.07 – Gerhard Paseman Sep 8 '11 at 3:03
You are trying to compute the minimal distance of certain cyclic codes. Look first in MacWilliams and Sloane. – Felipe Voloch Sep 8 '11 at 10:21
@Felipe: Almost but not quite. The code is not cyclic, because those multiples of the generator polynomial $f(x)$, where the other factor $a(x)$ is at most linear are apparently left out. Anyway, I'm fairly sure that you are correct in that this sequence $W_n$ is bounded. I need to think of suitable coding theoretical bound... – Jyrki Lahtonen Sep 11 '11 at 14:22

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.

-

$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$.

-
+1: A nice idea. Combinining this with a counting argument (see my answer) shows that $W_{min}(f)=3$ irrespective of whether there is a trinomial in $P_n$. – Jyrki Lahtonen Sep 13 '11 at 7:08