Intereting Posts

Subgroups of $S_n$ of index $n$ are isomorphic to $ S_{n-1}$
Why is $\lim_{x \to c}g(f(x)) = g(\lim_{x \to c}f(x))$
Cardinalities of $\mathbb{R^{2}}$ and $\mathbb{C}$ and isomorphisms
Understanding the multiplication of fractions
Log integrals I
Cutting a square of area $A$ through It's mid point yields two polygons of area $A/2$ for arbitrary cuts?
Is the restriction map of structure sheaf on an irreducible scheme injective?
Is there a formula for the inverse of Hadamard product?
Decomposition of a prime number in a cyclotomic field
How do I solve this exponential equation? $5^{x}-4^{x}=3^{x}-2^{x}$
another balls and bins question
Lagrange multipliers finding the maximum and minimum.
When do we have $\liminf_{n\to\infty}(a_n+b_n)=\liminf_{n\to\infty}(a_n)+\liminf_{n\to\infty}(b_n)$?
Learning Complex Geometry – Textbook Recommendation Request
How to prove that: $\tan(3\pi/11) + 4\sin(2\pi/11) = \sqrt{11}$

This is an entire field over my head right now, but my research into LFSRs has brought me here.

It’s my understanding that a primitive polynomial in $GF(2)$ of degree $n$ indicates which taps will create an LFSR. Such as $x^4+x^3+1$ is primitive in $GF(2)$ and has degree $4$, so a 4 bit LFSR will have taps on bits 4 and 3.

Let’s say I didn’t have tables telling me what taps work for what sizes of LFSRs. What process can I go through to determine that $x^4+x^3+1$ is primitive and also show that $x^4+x^2+x+1$ is not (I made that equation up off the top of my head from what I understand about LFSRs, I think it’s not primitive)?

- $K$-monomorphism $L\rightarrow L$ is $K$-automorphism if finite extension $L:K$
- Factoring $X^{16}+X$ over $\mathbb{F}_2$
- Primitive polynomials of finite fields
- Number of monic irreducible polynomials of prime degree $p$ over finite fields
- Constructing a finite field
- Intermediate fields of a finite field extension that is not separable

Several pages online say that you should divide $x^e+1$ (where e is $2^n-1$ and $n$ is the degree of the polynomial) by the polynomial, e.g. for $x^4+x^3+1$, you do $(x^{15}+1)/(x^4+x^3+1)$. I can divide polynomials but I don’t know what the result of that division will tell me? Am I looking for something that divides evenly? Does that mean it’s not primitive?

- Finding cubic function from points?
- Irreducibility of $X^{p-1} + \cdots + X+1$
- Irreducible factors of $X^p-1$ in $(\mathbb{Z}/q \mathbb{Z})$
- The degree of a polynomial which also has negative exponents.
- Exhibiting an isomorphism between two finite fields
- What are the common solutions of $x^2+y=31$ and $y^2+x=41$?
- How to prove that $\,\,f\equiv 0,$ without using Weierstrass theorem?
- Let $f(x) =x^5+x^2+1$ with $a, b, c, d, e$ as zeros. . .
- Factor $x^4+1$ over $\mathbb{R}$
- Units of polynomial rings over a field

For a polynomial $p(x)$ of degree $n$ with coefficients in $GF(2)$ to be primitive, it must satisfy the condition that $2^n-1$ is the smallest positive integer $e$ with the property that

$$

x^e\equiv 1\pmod{p(x)}.

$$

You got that right.

For a polynomial to be primitive, it is necessary (but not sufficient) for it to be irreducible. Your “random” polynomial

$$

x^4+x^2+x+1=(x+1)(x^3+x^2+1)

$$

fails this lithmus test, so we don’t need to check anything more.

Whenever I am implementing a finite field of characteristic two in a computer program at the beginning I generate a table of discrete logarithms. While doing that I also automatically verify that $2^n-1$ is, indeed, the smallest power of $x$ that yield remainder $=1$. For an *in situ* example see the latter half of my answer to this question, where I verify that $x^3+x+1$ is primitive by showing that we need to go up to $x^7$ to get remainder equal to $1$.

Doing it by hand becomes tedious after while. There are several shortcuts available, if you know that $p(x)$ is irreducible and if you know the prime factorization of $2^n-1$. These depend on the fact the multiplicative group of $GF(2^n)$ is always cyclic. Your example of $p(x)=x^4+x^3+1$ is a case in point. It is relatively easy to decide that it is

irreducible. Then the theory of cyclic groups tells that the smallest $e$ will be factor of $15$. So to prove that it is actually equal to fifteen it suffices to check that none of

$e=1,3,5$ work. This is easy. The only non-trivial check is that

$$

x^5\equiv x^5+x(x^4+x^3+1)=x^4+x\equiv x^4+x+(x^4+x^3+1)=x^3+x+1\not\equiv1\pmod{x^4+x^3+1},

$$

and this gives us the proof.

Even with the shortcuts, finding a primitive polynomial of a given degree is a task I would rather avoid. So I use look up tables. My favorite on-line source is at

http://web.eecs.utk.edu/~plank/plank/papers/CS-07-593/primitive-polynomial-table.txt

After you have one primitive polynomial, you often want to find other closely related ones. For example, when calculating generating polynomials of a BCH-code or an LFSR of a Gold sequence (or other sequence with known structure) you encounter the following task. The given primitive polynomial is the so called minimal polynomial of any one of its roots, say $\alpha$. Those constructions require you to find the minimal polynomial of $\alpha^d$ for some $d$. For example $d=3$ or $d=5$ are very common. The minimal polynomial of $\alpha^d$ will be primitive, iff $\gcd(d,2^n-1)=1$, and this often holds.

Then relatively basic algebra of field extensions gives you an algorithm for finding the desired minimal polynomial. Space won’t permit me to get into that here, though.

A good (not too theoretical) oveview is Kerl’s “Computation in finite fields” (it is incomplete, sadly). It looks a bit at LFSRs too. BTW, any polynomial defines a LFSR, the point is that primitive polynomials give ones with nice properties.

- Are there any examples of non-computable real numbers?
- Solve trigonometric equation: $1 = m \; \text{cos}(\alpha) + \text{sin}(\alpha)$
- Which Lie groups have Lie algebras admitting an Ad-invariant inner product?
- Null-recurrence of a random walk
- Zero Cohomology means zero homology?
- Find the $44{th}$ digit of a $80$ digit number if number is divisible by $13$
- $y'=$ ${-x+\sqrt{(x^2+4y)}}\over 2$ , $y(2)=-1$
- An exercise about finite intersection property in $T_1$ space
- Limit $\frac{x^2y}{x^4+y^2}$ is found using polar coordinates but it is not supposed to exist.
- Proof of the inequality $2\uparrow^n 4 < 3\uparrow^n 3 < 2\uparrow^n 5$
- Probability of two people meeting in a given square grid.
- Confusion on the proof that there are “arbitrarily large gaps between successive primes”
- How can I know if $2^{2^{2^{2^{2}}}}+1=?$ is prime?
- Notation for fields
- Idempotent matrix is diagonalizable?