Information Technology Reference
In-Depth Information
Corollary 1 ([21]).
Let
S
be the 2-adic representation of
h/q
,where
q
=
p
e
is a prime power with
p
prime,
e
≥
1
and
−
q
≤
h
≤
0
.Let
d>
0
be relatively
prime to
T
=
p
e
p
e−
1
, the period of
S
.Let
S
d
be a
d
-decimation of
S
with
−
≤
i<d
and let
h
/q
be its 2-adic representation such that
−
q
≤
h
≤
0
0
and
gcd(
q
,h
)=1
.Then
q
divides
2
T/
2
+1
.
If the following conjecture is true, we have more information on the new value
q
.
Conjecture 1 ([21]).
Let
S
be an
-sequence with connection number
q
=
p
e
and
period
T
. Suppose
p
is prime and
q
.Let
d
1
and
d
2
be relatively
prime to
T
and incongruent modulo
T
. Then for any
i
and
j
,
S
d
1
∈{
5
,
9
,
11
,
13
}
and
S
d
2
are
is equivalent to
S
d
2
0 such that
S
d
1
cyclically distinct,
i.e.
there exists no
τ
≥
shifted by
τ
positions to the left.
This conjecture has already been proved for many cases [20,22] but not yet for
all. If it holds, this implies that for any
d>
1,
S
d
is cyclically distinct from
our original
-sequence. We chose
q
such that the period was maximal, thus,
any other sequence with the same period which is cyclically distinct must have
avalue
q
>q
. This means that the complexity of the FCSR producing the
subsequence
S
d
will be larger than the original FCSR,
if
d
and
T
are relative
prime
.
Remark 1.
Let us consider the special case where
q
is prime and the period
T
=
q
1=2
p
is twice a prime number
p>
2, as recommended for the stream
cipher proposed in [23]. The only possibilities in this case for
gcd
(
d, T
)
>
1is
d
=2or
d
=
T/
2.
For
d
=
T/
2, we will have
T/
2 FCSRs where each of them outputs either
0101
...
or 1010
...
,sinceforan
-sequence the the second half of the period is
the inverse of the first half [21]. Thus, the size of the sub-sequences generator
will be in the magnitude of
T
which is exponentially bigger than the 2-adic
complexity of
S
which is log
2
(
q
).
In the case of
d
= 2, we get two new sequences with period
T
=
p
. As for any
FCSR, it must hold that
T
−
ord
q
(2), where
ord
q
(2) is the multiplicative order
of 2 modulo
q
.Let
ϕ
(
n
) denote Euler's function,
i.e.
the number of integers
smaller than
n
which are relative prime to
n
.Itiswellknown,
e.g.
[16], that
ord
q
(2)
|
has the prime factorization
p
e
1
p
e
2
ϕ
(
q
)andif
q
p
e
r
r
then
ϕ
(
q
)=
|
···
i
=1
p
e
i
−
1
=
ϕ
(
q
), because otherwise (
p
+1)
must be a prime number, which is not possible since
p>
2isaprime.Wealso
know that
T
∗
=
p
(
p
i
−
1). From this follows that
p
i
|
ϕ
(
q
∗
), thus 2
×
p
=
q
−
≤
ϕ
(
q
∗
) . This implies that
q
>q
,
1
since from
T
=
T/
2 follows that
q
=
q
.
Together with Conjecture 1, we obtain that for such an FCSR any decimation
would have a larger complexity than the original one. This is also interesting
from the perspective of stream ciphers, since any decimated subsequence of such
an FCSR has larger 2-adic complexity than the original one, except for the trivial
case with
d
=
T/
2.
