Cryptography Reference
In-Depth Information
Due to the finite number of recurring states, the output sequence of an LFSR re-
peats periodically. This was also illustrated in Example 2.3. Moreover, an LFSR can
produce output sequences of different lengths, depending on the feedback coeffi-
cients. The following theorem gives us the
maximum length
of an LFSR as function
of its degree.
Theorem 2.3.1
The maximum sequence length generated by an
LFSR of degree m is
2
m
−
1
.
It is easy to show that this theorem holds. The
state
of an LFSR is uniquely deter-
mined by the
m
internal register bits. Given a certain state, the LFSR deterministi-
cally assumes its next state. Because of this, as soon as an LFSR assumes a previous
state, it starts to repeat. Since an
m
-bit state vector can only assume 2
m
−
1 nonzero
states, the maximum sequence length before repetition is 2
m
1. Note that the all-
zero state must be excluded. If an LFSR assumes this state, it will get “stuck” in
it, i.e., it will never be able to leave it again. Note that only certain configurations
(
p
0
,...,
p
m
−
1
) yield maximum length LFSRs. We give a small example for this be-
low.
−
Example 2.4.
LFSR with maximum-length output sequence
Given an LFSR of degree
m
= 4 and the feedback path (
p
3
= 0
,
p
2
= 0
,
p
1
=
1
,
p
0
= 1), the output sequence of the LFSR has a period of 2
m
−
1 = 15, i.e., it
is a maximum-length LFSR.
Example 2.5.
LFSR with non-maximum output sequence
Given an LFSR of degree
m
= 4 and (
p
3
= 1
,
p
2
= 1
,
p
1
= 1
,
p
0
= 1), then the output
sequence has period of 5; therefore, it is not a maximum-length LFSR.
The mathematical background of the properties of LFSR sequences is beyond
the scope of this topic. However, we conclude this introduction to LFSRs with some
additional facts. LFSRs are often specified by polynomials using the following no-
tation: An LFSR with a feedback coefficient vector (
p
m
−
1
,...,
p
1
,
p
0
) is represented
by the polynomial
P
(
x
)=
x
m
+
p
m
−
1
x
m
−
1
+
...
+
p
1
x
+
p
0
For instance, the LFSR from the example above with coefficients (
p
3
= 0
,
p
2
=
0
,
p
1
= 1
,
p
0
= 1) can alternatively be specified by the polynomial
x
4
+
x
+ 1.
This seemingly odd notation as a polynomial has several advantages. For instance,
maximum-length LFSRs have what is called
primitive polynomials
. Primitive poly-
nomials are a special type of irreducible polynomial. Irreducible polynomials are
roughly comparable with prime numbers, i.e., their only factors are 1 and the
polynomial itself. Primitive polynomials can relatively easily be computed. Hence,
maximum-length LFSRs can easily be found. Table 2.3 shows one primitive poly-
nomial for every value of
m
in the range from
m
= 2
,
3
,...,
128. As an example,
