Information Technology Reference
In-Depth Information
is known as the
connection element
of the AFSR. If we start with
q
,wedenote
by
D
q
the AFSR with connection element
q
1
.Wemayalsorefertoitasa
connection element for any sequence
a
generated by
D
q
. Any given sequence has
many connection elements. The connection element plays a critical role in the
analysis of AFSR sequences. We can associate a
π
-adic integer
α
=
∞
a
i
π
i
i
=0
to the sequence
a
=
a
0
,a
1
,
S
.Thesetofall
π
-adic integers is a ring in
a natural way. But note that this is not simply a power series ring — the sum or
product of two elements of
S
may not be in
S
, so expressing sums and products
of
π
-adic integers as
π
-adic integers in general involves complicated carries to
higher degree terms, perhaps even carries to infinitely many terms. Again, we
refer to [6] for more details on
π
-adic integers.
If
q
is as in equation (1), then any rational element
u/q
···
,
a
i
∈
R
canalsobeexpressedassucha
π
-adic integer
2
and it can be shown that
a
is
the output from an AFSR with connection element
q
if and only if there exists
u
∈
R
[1
/q
],
u
∈
∈
R
so that
u/q
=
α
.Infact
u
can be expressed in terms of the initial state
(
a
0
,
···
,a
r−
1
;
m
)by
r−
1
n
=0
i
=1
q
i
a
n−i
π
n
q
0
r−
1
n
=0
a
n
π
n
mπ
r
−
−
=
u
α
=
q
.
(2)
q
More discussion of AFSRs,
π
-adic numbers, and
π
-adic span can be found in a
paper by Xu and Klapper [14]. We emphasize that the
π
-adic span of an AFSR
depends both on the structure of the AFSR (that is, on the connection element
q
) and on a particular initial state.
The
π
-adic span of a sequence is important as a security measure if there is
an
AFSR synthesis algorithm
for
R
,
π
,and
S
. This is an algorithm which takes
a prefix of a sequence as input and outputs a minimal AFSR over
R
,
π
,and
S
that outputs the prefix. If the prefix is suciently large (typically a constant
times the
π
-adic span of the sequence), the AFSR in fact generates the entire
sequence. Thus if such an algorithm is known (register synthesis algorithms are
only known for certain types of AFSRs [14]), any sequence used as a key in a
stream cipher should have large
π
-adic span. It is important, then, to understand
the average behavior of
π
-adic span, as has been done for linear span and 2-adic
span [10,11,12,13].
The
π
-adic span of an infinite sequence is not always defined. As is the case
with linear feedback shift registers and feedback with carry shift registers, some
sequences are not generated by any AFSR over
R
,
π
,and
S
at all. For example,
1
We are being a little sloppy here since a given
q
may have several representations in
the form in equation (1), but this causes no problems.
2
Actually, for this statement to be true we need a
separability condition
on
R
,that
∩
i
=1
(
π
)
i
= (0). This condition always holds when
R
=
Z
[
π
]and
π
is integral
over
Q
.
