Information Technology Reference
In-Depth Information
3
Jumping by Fast Polynomial Multiplication
A linear recurrence over
F
2
can be represented in different spaces and it is not
dicult (at least in principle) to switch from one representation to the other
[8,9]. The basic PRNG implementation usually represents the state as a
k
-bit
vector and computes the matrix-vector product in (1) by just a few elementary
operations. In other representations, used for example to verify maximal period
conditions and to analyze the multidimensional uniformity of the output values,
the state is represented as a polynomial or as a formal series [10,9]. Here, we will
use a formal series representation of the state, switch to that representation to
perform the jumping ahead, and then recover the state in the original represen-
tation. A key practical requirement is the availability of an ecient method to
perform this last step.
For our purpose, we assume that the linear output function
o
returns a single
bit; that is, we have
o
:
S
→
F
2
. Here, we may choose any
o
satisfying the
injective condition stated below, for the purpose of jump computation. For the
Mersenne twister, for example, the output at each step is a block of 32 bits
and we can just pick up the most significant bit.
We also assume that the
mapping
S
2
which maps the generator's state to the next
k
bits of output
is one-to-one, so we can recover the state from
k
successive bits of output. This
assumption is not restrictive: for example, if the period of this single-bit output
is 2
k
→
F
−
1, which is usually the case in practice, then the assumption is satisfied
by comparing the cardinality of the state space and the set of the
k
successive
bits.
More specifically, let
G
(
s, t
)=
∞
o
(
s
i−
1
)
t
−i
,
i
=1
which is the generating function of the output sequence when the initial state is
s
0
=
s
.Notethat
G
(
s
1
,t
)=
tG
(
s
0
,t
)(mod
F
2
[
t
]), so that
G
(
s
J
,t
)=
t
J
G
(
s
0
,t
)(mod
F
2
[
t
]) =
g
(
t
)
G
(
s
0
,t
)(mod
F
2
[
t
])
,
because
ϕ
F
(
t
)
∈
F
2
[
t
]. To recover the state
s
J
,weonlyneedthecoecientsof
t
−
1
,...,t
−k
in
G
(
s
J
,t
)=
g
(
t
)
G
(
s
0
,t
), i.e., the truncation of
G
(
s
J
,t
)toitsfirst
k
terms. This means that we can replace
G
(
s
0
,t
) by its truncation to its first
2
k
terms, or equivalently by the truncation of
t
2
k
G
(
s
0
,t
)toitsfirst2
k
terms,
which gives the polynomial
2
k−
1
o
(
s
i
)
t
2
k−
1
−i
.
h
(
s
0
,t
)=
i
=0
We can then compute the polynomial product
g
(
t
)
h
(
s
0
,t
), and observe that
the coecients of
t
2
k−
1
,...,t
k
in this polynomial are exactly the output bits
o
(
s
J
)
,...,o
(
s
J
+
k−
1
), from which we can recover the state
s
J
.
With the classical (standard) method, we need
O
(
k
2
) bit operations just to
multiply the polynomials
g
(
t
)and
h
(
s
0
,t
), so we are doing no better than with
