1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Sep 8, 2011 at 3:03
  • 1
    $\begingroup$ You are trying to compute the minimal distance of certain cyclic codes. Look first in MacWilliams and Sloane. $\endgroup$ Sep 8, 2011 at 10:21
  • $\begingroup$ @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... $\endgroup$ Sep 11, 2011 at 14:22

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ +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$. $\endgroup$ Sep 13, 2011 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.