Information Technology Reference
In-Depth Information
the method of [6]. Polynomial multiplication can be done with only
O
(
k
log
k
)
bit operations using fast Fourier transforms, but the hidden constants are larger
and the corresponding algorithm turns out to be slower when implemented, for
the values of
k
that we are interested in. A third approach, implemented in
the NTL library [11], is Karatsuba's algorithm (see, e.g., [12]), which requires
O
(
k
log
2
3
)
O
(
k
1
.
59
) bit operations. This algorithm is faster than the classical
method even for moderate values of
k
, and this is the one we adopt for this step
of our method.
The last ingredient we need is a fast method to compute the inverse image of
the mapping
≈
o
(
k
)
:
s
(
o
(
s
)
,o
(
Fs
)
,o
(
F
2
s
)
,...,o
(
F
k−
1
s
))
,
→
to be able to recover the state
s
J
from the coecients of
g
(
t
)
h
(
s
0
,t
). For impor-
tant classes of PRNGs such as the twisted GFSR and Mersenne twister, there is
a simple algorithm to compute this inverse image in
O
(
k
) time. Then, our entire
procedure works in
O
(
k
log
2
3
)
O
(
k
1
.
59
)time.
The procedure is summarized in Algorithm 1.. It assumes that
g
(
t
) has been
precomputed in advance.
≈
Algorithm 1.
Jump ahead by polynomial multiplication
Input
the state
s
=
s
0
;
Compute
the polynomial
steps;
Compute
the product
g
(
t
)
h
(
s
0
,t
) and extract the coecients
o
(
s
J
)
,...,o
(
s
J
+
k
−
1
);
Compute
the state
s
J
h
(
s
0
,t
) by advancing the generator for 2
k
from the bits
o
(
s
J
)
,...,o
(
s
J
+
k
−
1
);
Return
s
J
.
4
Illustrative Example by LFSR
The Linear Feedback Shift Register (LFSR) is a most classical and widely spread
generator. Here, we use the term LFSR in the following limited sense (see [13]),
although sometimes LFSR refers to a wider class of generators.
The state space is the row vector space
S
:=
2
, and the state transition
F
function is defined by
k−
1
(
x
0
,...,x
k−
1
)
→
(
x
1
,x
2
,...,x
k−
1
,
a
i
x
i
)
,
i
=0
where
a
0
,...,a
k−
1
are constants in
F
2
.Ifwechoose
o
:(
x
0
,...,x
k−
1
)
→
x
0
,
then it directly follows that
o
(
k
)
:
S
→
F
2
is the identity function. Thus, we can
skip the computation of its inverse.
Proposition 1.
The computational complexity of PM-Jump for LFSR is the
same with that for the polynomial multiplications of degree
2
k
.Asaresult,
jumping ahead can be done in
O
(
k
1
.
59
)
time if we use Karatsuba's polynomial
multiplication, and in
O
(
k
log
k
)
time if we use a fast Fourier transform.
