Information Technology Reference
In-Depth Information
value
q
determines the feedback positions of the automata, depending on the
setup used. In this article, we consider
-sequences
,
i.e.
sequences with maximal
period
ϕ
(
q
), where
ϕ
denotes Euler's phi function. This is equivalent to the
case that
q
is a prime power and 2 has multiplicative order
ϕ
(
q
) modulo
q
.For
simplicity reasons, we restrict ourselves also to the case where the generated
sequence is strictly periodic. This property is equivalent to
−
q
≤
h
≤
0, which is
always the case for Galois FCSRs but not necessarily for Fibonacci FCSRs. The
2
-adic complexity
[5] of a sequence is defined as the size of the smallest FCSR
which produces this sequence. In the periodic case, this is equivalent to the bit
length of
q
.
3 Sub-sequences Generators and
m
-Sequences
The decimation of LFSR sequences has been used in cryptography in the design
of new stream ciphers [18]. There exists two approaches to use decimation theory
to define the automata associated to the sub-sequences.
Construction using LFSR synthesis.
This first solution associates an LFSR to
each sub-sequence. It is based on well-known results on the decimation of LFSR
sequences. It can be applied to both Fibonacci and Galois representation without
any distinction.
Theorem 1 ([19,13]).
Let
S
be a sequence produced by an LFSR whose char-
acteristic polynomial
Q
(
x
)
is irreducible in
F
2
of degree
m
.Let
α
be a root of
Q
(
x
)
and let
T
be the period of
Q
(
x
)
.Let
S
d
be a sub-sequence resulting from
the
d
-decimation of
S
.Then,
S
d
can be generated by an LFSR with the following
properties:
-
The minimum polynomial of
α
d
in
F
2
m
is the characteristic polynomial
Q
(
x
)
of the resulting LFSR.
-
The period
T
of
Q
(
x
)
is equal to
T
gcd
(
d,T
)
.
-
The degree
m
of
Q
(
x
)
is equal to the multiplicative order of
Q
(
x
)
in
Z
T
.
In practice, the characteristic polynomial
Q
(
x
) can be determined using the
Berlekamp-Massey algorithm [1]. The sub-sequences are generated using
d
LF-
SRs defined by the characteristic polynomial
Q
(
x
) but initialized with differ-
ent values. In the case of LFSRs, the degree
m
∗
must always be smaller or
equal to
m
.
Construction using a multiple steps LFSR.
This method was first proposed by
Lempel and Eastman [11]. It consists in clocking the LFSR
d
times in one clock
cycle by changing the connections between the memory cells and by some dupli-
cations of the feedback function. We obtain a network of linearly interconnected
shift registers. This method differs for Galois and Fibonacci setup. The transfor-
mation of an
m
-bit Fibonacci LFSR into an automaton which generates
d
bits
per cycle is achieved using the following equations:
