Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
+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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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