IEICE TRANS. FUNDAMENTALS, VOL.Exx–??, NO.xx XXXX 200x
1
LETTER
Linear complexity of n-periodic cyclotomic sequences over F
p
Qiuyan WANG
†a)
, Member and Yang YAN
††b)
, Nonmember
SUMMARY Periodic sequences, used as keys in cryptosystems, plays
an important role in cryptography. Such periodic sequences should possess
high linear complexity to resist B-M algorithm. Sequences constructed by
cyclotomic cosets have been widely studied in the past few years. In this
paper, the linear complexity of n-periodic cyclotomic sequences of order
2 and 4 over F
p
has been calculated, where n and p are two distinct odd
primes. The conclusions reveal that the presented sequences have high
linear complexity in many cases, which indicates that the sequences can
resist the linear attack.
key words: Legendre sequences Cyclotomic sequences Linear complexity
Gauss periods
1. Introduction
Periodic sequences used for stream ciphers are required to
have qualities of unpredictability. The linear complexity
is shown to have valuable properties as a measure for the
randomness (or equivalently the unpredictability) of peri-
odic sequences. Let c = (c
i
)
∞
i=0
be a sequence of peri-
od n over the finite field F
q
. The linear complexity (also
called linear span) of c over F
q
, denoted by L
q
(c), is de-
fined to be the smallest positive integer l such that there
are constants a
0
, 0, a
1
, . . ., a
l
∈ F
q
satisfying −a
0
c
i
=
a
1
c
i−1
+ a
2
c
i−2
+ ···+ a
l
c
i−l
= 0 for all i ≥ l. The Berlekamp-
Massey algorithm [1], [10] states that if L
q
(c) > n/2, then c
is considered good with respect to its linear complexity.
For an odd prime n, let n −1 = ek (e ≥ 2) and F
n
be the
finite field with n elements. Suppose θ is a primitive element
of F
∗
n
= F
n
\{0}. Let
C
λ
= C
(e)
λ
= θ
λ
C
0
, (0 ≤ λ ≤ e − 1),
where C
0
= hθ
e
i is the subgroup of F
∗
n
generated by θ
e
and
C
λ
(0 ≤ λ ≤ e − 1) are the cosets of C
0
in F
∗
n
. Let S be a
subset of {0, 1, . . . , e − 1} and
Σ
S
=
[
λ∈S
C
λ
.
We define the following binary periodic sequence c
S
=
(c
i
)
∞
i=0
with period n by
Manuscript received 0, 0.
Manuscript revised 0, 0.
†
School of Computer Science and Technology, Tiangong Uni-
versity, Tianjin, China
††
School of Information Technology Engineering, Tianjin Uni-
versity of Technology and Education, Tianjin, China
a) E-mail: wangyan198801@163.com
b) E-mail: yanyangucas@126.com
DOI: 10.1587/transfun.E0.A.1
c
i
=
(
1, if (i mod n) ∈ Σ
S
,
0, otherwise,
for all i ≥ 0.
Such sequences are called binary cyclotomic sequences of
order e and used as keys in cryptography since they have
good pseudo-random properties and correlation properties
[6], [8], [11]–[13]. The linear complexity of such sequences
over F
2
has been determined by Ding et al. [5] for order
2 case (Legendre sequences) and Edemskii [7] for order 4
case. Since c
i
is either 0 or 1, such sequences can be viewed
over F
q
, where q = p
m
and p is a prime number. When
(n − 1)/4 ≡ 0 (mod p), Ding [4] has determined the lin-
ear complexity of cyclotomic sequences of order 4 over F
p
m
from the view point of coding theory. In this paper, our
first contribution is to give a general formula on the linear
complexity of cyclotomic sequences by using Gauss period-
s. Our second contribution is to determine the linear com-
plexity of binary n-periodic cyclotomic sequences of order
2 and 4 over a finite field F
p
m
, where p and n are two distinct
odd primes. The results show that the linear complexity of
c over F
p
m
is nearly equal to the period n in many cases so
that they can resist the linear attack in cryptography.
This paper is organized as follows. Section 2 contains
the definitions and formulas of linear complexity of periodic
sequences and Gauss periods. In section 3, we determine
the linear complexity of the binary cyclotomic sequences of
order 2 and 4 over F
q
.
2. Preliminaries
Firstly, we introduce the definition and formula of linear
complexity of periodic sequences over a finite field. See
[3] or [9] for more details.
Let q be a power of a prime p and let c = (c
i
)
∞
i=0
be a
periodic sequence over F
q
with period n, where c
i
∈ F
q
(i ≥
0). The sequence c can be viewed as a power series
c
∞
(x) =
∞
X
n=0
c
n
x
n
=
u(x)
1 − x
n
,
u(x) = c
0
+ c
1
x + c
2
x
2
+ ··· + c
n−1
x
n−1
∈ F
q
[x]
in the power series ring F
q
[[x]].
Let h(x) = gcd(u(x), 1 − x
n
) , then
c
∞
(x) =
w(x)
v(x)
, v(x) =
1 − x
n
h(x)
w(x) =
u(x)
h(x)
where u(x), v(x), h(x) ∈ F
q
[x].
Copyright
c
200x The Institute of Electronics, Information and Communication Engineers
剩余6页未读，继续阅读
资源评论
