Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
From what I understand an LFSR produces a maximal length sequence if its characteristic polynomial $p(x)$ of degree $n$ is irreducible, i.e. if it cannot be factored and the smallest integer $k$ for which $p(x)$ divides $x^k – 1$ is $2^n – 1.$
I understand $2^n -1$ has to do with the period, but how is it calculated whether the polynomial is irreducible? Thank you.
Actually the property you mention
$p(x)$ of degree $n$ cannot be factored, and divides $x^k-1$ for the first time when $k=2^n-1$
means the polynomial $p(x)$ of degree $n$ is primitive. If $p(x)$ cannot be factored into a product of polynomials of lower degree then it is irreducible. It is enough to consider irreducible polynomials of lower degree (like prime numbers) as possible factors.
Therefore one could check whether $p(x)$ factors by methods similar to checking whether a number is prime. However, the following helps:
For $i ≥ 1$ the polynomial $x^{2^i}-x \in \mathbf{F}_2[x]$ is the product of all monic irreducible polynomials in $\mathbf{F}_2[x]$ whose degree divides $i$.
So, you could compute $x^{2^n}-x$ modulo $p(x)$ by the division algorithm and declare $p(x)$ irreducible if the answer is zero.
