Information Technology Reference
In-Depth Information
To bound the summation in the last line, it suces to bound
k
log
2
(
|
N
(
z
)
|
)
A
de
=
|
N
(
z
)
|
=1
,where
w
=
i
z
i
. The function log
2
(
x
)
/x
is
N
(
π
n
in terms of
|
−
1)
|≥|
N
(
w
)
|
decreasing for integers
x
consists of the
k
irreducible and pairwise relatively prime elements of
R
with smallest norms.
Let
j
be a positive integer and consider the irreducible elements with norms
between 2
j
and 2
j−
1
. By Landau's prime ideal theorem there are asymptotically
≥
3. Thus we may assume that
{
z
}
2
j
ln(2
j
)
2
j
j
ln(2)
=
1)
/
2
j−
1
to
A
, so the total
contribution to
A
for each
j
is at most 2
/
ln(2). It also follows that the largest 2
j
we must consider is asymptotically
Θ
(
k
log(
k
)). It follows that
A
such elements [8]. Each contributes at most (
j
−
∈
O
(log(
k
)).
from the irreducible ele-
ments with norms between 2
m
and 2
m
+1
is asymptotically at least
Now consider
|
N
(
w
)
|
. The contribution to
|
N
(
w
)
|
(2
m
)
2
m
/
(
m
ln(2))
=2
2
m
/
ln(2)
.
The largest
m
we need is at most log(
k
ln(
k
))
<
2 log(
k
). Thus
⎛
2
2
m
/
ln(2)
⎞
log(
k
)
⎠
=
Ω
(2
(
log(
k
)
⎝
2
m
/
ln(2))
)=
Ω
(2
2
k/
ln(2)
)
.
|N
(
w
)
|∈Ω
m
=1
m
=1
N
(
π
n
Therefore
A
∈
O
(log log
|
N
(
w
)
|
⊆
O
(log log
|
−
|
)=
O
(log(
n
)).
)
1)
5 Conclusions
We have expanded our understanding of average behavior of generator-based
security measures for sequences to the case of AFSRs based on rings of the form
Z
[
p
1
/d
]. We have only fully analyzed the case when
p
=
d
= 2. This analysis
used specialized algebraic properties of this ring that do not hold in general. It
is not clear what can be said for more general
p
and
d
. Even more problematic
is the general case of AFSRs. In the most general setting there may not even be
an algebraic notion of
-span.
In the case
p
=
d
= 2, we have seen that
E
n
is asymptotically
n
.Thissays
that random long sequences are resistant to register synthesis attacks based on
these AFSRs. It would be very interesting to find a ring
R
for which
E
n
is
asymptotically smaller than
n
, so that random sequences do not resist attack.
F
-complexity that is closely tied to
F
Acknowledgement
Thanks to Hugh Williams for suggesting the proof of part 3 of Lemma 1.
