Information Technology Reference
In-Depth Information
Acknowledgements
Thanks to Dr. Andrew Klapper for several helpful suggestions during the prepa-
ration of this paper. Thanks to Dr. Zongming Fei for providing o
ce space and
resources while researching for this paper. Thanks to anonymous reviewers for
their careful proofreading.
References
1. Cusick, T.W., Ding, C., Renvall, A.: Stream Ciphers and Number Theory. North-
Holland, Amsterdam (1998)
2. Ding, C., Xiao, G., Shan, W.: The Stability Theory of Stream Ciphers. Springer,
Heidelberg (1991)
3. Fu, F.-W., Niederreiter, H., Su, M.: The characterization of 2
n
-periodic binary se-
quences with fixed 1-error linear complexity. In: Gong, G., Helleseth, T., Song, H.-
Y., Yang, K. (eds.) SETA 2006. LNCS, vol. 4086, pp. 88-103. Springer, Heidelberg
(2006)
4. Games, R.A., Chan, A.H.: A fast algorithm for determining the complexity of a
pseudo-random sequence with period 2
n
. IEEE Trans. Inform. Theory 29(1), 144-
146 (1983)
5. Kurosawa, K., Sato, F., Sakata, T., Kishimoto, W.: A relationship between linear
complexity and
k
-error linear complexity. IEEE Trans. Inform. Theory 46(2), 694-
698 (2000)
6. Meidl, W.: On the stability of 2
n
-periodic binary sequences. IEEE Trans. Inform.
Theory 51(3), 1151-1155 (2005)
7. Rueppel, R.A.: Analysis and Design of Stream Ciphers. Springer, Heidelberg (1986)
8. Stamp, M., Martin, C.F.: An algorithm for the
k
-error linear complexity of binary
sequences with period 2
n
. IEEE Trans. Inform. Theory 39(4), 1398-1401 (1993)
A Proof of Theorem 1
For any sequence
S
∈A
(
L
), consider the corresponding polynomial
S
(
x
)=
x
)
2
n
−L
a
(
x
), where
a
(
x
)
(1
−
∈
F
2
[
x
] such that deg(
a
(
x
))
≤
L
−
1and
a
(1)
=0.
L<
2
n−r
,wehave2
n
L>
2
n
2
n−r
. The generating function for
Since 1
≤
−
−
S
is given by
1)
(2
n
−
2
n
−
r
)+(2
n
−
r
−L
)
a
(
x
)
(
x
S
(
x
)
x
2
n
(
x
−
1
=
−
−
1)
2
n
1)
2
n
−
r
−L
a
(
x
)
x
2
n
−
r
(
x
−
=
,
−
1
which implies 2
n−r
is a period of
S
.
Corresponding to any sequence
S
∈A
(
L
), let
S
denote the 2
n−r
-periodic
L<
2
n−r
, from Lemma 3 we know
that
w
H
(
S
1
)and
w
H
(
S
2
) are even. Hence the Hamming distance between
S
1
and
S
2
is even. That is
d
H
(
S
1
,
S
2
)=2
t
,s
2
n
−
r
−
1
)
∞
.Since1
sequence (
s
0
,s
1
,
···
≤
,
2
n−r−
1
for some
t
∈{
1
,
2
,
3
,
···
}
.
