Cryptography Reference
In-Depth Information
3.38. If an LFSR has period length 2
−
1, called a
maximum-length
LFSR,
show that
c
j
x
j
,
t
(
x
)=1+
j
=1
called the
tap polynomial
, is irreducible.
(
Hint: See Definition A.35 on page 486 in Appendix A. Assume that
t
(
x
)
is reducible and argue on the degrees of the individual factors in relation to
t
(
x
)
. Also, note that the individual factors generate LFSRs and the least
common multiple of their periods must be at least as big as the period for
the LFSR associated with
t
(
x
)
.
)
3.39. Is the converse of Exercise 3.38 true?
(
Hint: Look at Exercise 3.34.
)
3.40. Show that if
t
(
x
) is the tap polynomial for a maximum-length LFSR
(see Exercise 3.38), then
t
(
x
) must divide
x
2
−
1
−
1 but
t
(
x
)doesnot
divide
x
d
1 for any proper divisor
d
of 2
−
−
1. (In this case
t
(
x
) is called
primitive
.)
(
Hint: Use matrix theory employing the tap matrix
C
, defined on page 157,
and the matrix theory in Appendix A, especially on page 493, to conclude
that
C
2
1
=
I
, where
I
is the identity matrix and all entries are reduced
modulo
2
. Note that since
t
(
x
)
must be irreducible by Exercise 3.38, then
it divides every polynomial that has the root
C
of
C
2
−
−
1
=
I
in common
with it, where
t
(
x
)
is viewed as the determinant of the matrix
C
−
Ix
.
Thus,
t
(
x
)
will divide
x
2
−
1
−
1
in this case.
)
3.41. Show that if
n
(1) denotes the number of ones output by a maximum
length LFSR, and
n
(0) denotes the number of zeros output by it, then
n
(1)
n
(0) = 1.
(
Hint: The zero sequence cannot be included.
)
−
3.42. Show that if
t
(
x
) is irreducible as the tap polynomial of an LFSR, then
the period length is a factor of 2
1.
(
Hint: Use similar techniques to those suggested in the hint for Exercise
3.40.
)
−
Show that if 2
3.43.
1 is prime (called a
Mersenne prime
), then every
irreducible polynomial of degree
is the tap polynomial of a maximum-
length LFSR.
−
3.44. Suppose that
r
is a factor of 2
1 but
r
is not a factor of 2
d
1 for
any positive integer
d<
. Show that there is an irreducible polynomial
of degree
that is the tap polynomial of an LFSR of period length
r
.
(
Hint: You can actually show that there are
φ
(
r
)
/
irreducible polynomials
of degree
as tap polynomials of LFSRs of period length
r
, for each such
−
−
Search WWH ::
Custom Search