Information Technology Reference
In-Depth Information
Note that it is irrelevant to use (
x
i
,...,x
i
+
k−
1
)asthe
i
-th output
k
-bit inte-
ger of the pseudorandom number generator, since the consecutive outputs are
overlapped. However, such an LFSR is used in stream cipher (pseudorandom bit
generator), with suitably chosen nonlinear output function
o
:
S
→
F
2
,seefor
example [14].
5 Application to the Mersenne Twister
The Mersenne Twister (MT) generator can be described as follows [4]. Let
w
bethewordsizeofthemachine(e.g.,
w
= 32). The row vector space
W
:=
2
is identified with the set of words. For fixed integers
n>m
, MT generates a
sequence
x
0
,
x
1
,...
of elements of
W
by the following recurrence:
F
(
x
w−r
j
|
x
j
+1
)
A,
x
j
+
n
:=
x
j
+
m
⊕
j
=0
,
1
,...,
where (
x
w−r
j
|
x
j
+1
) denotes the concatenation of the upper (
w
r
)bit(
x
w−r
j
−
)
and the lower
r
bit (
x
j
+1
)of
x
j
+1
,andthe
w
of
x
j
w
matrix
A
is defined
indirectly as follows: For any
w
-dimensional row vector
x
,
x
A
=
shiftright(
x
)
×
if the SBof
x
=0
,
shiftright(
x
)
⊕
a
if the LSB of
x
=1
,
where LSB means the least significant bit (i.e., the rightmost bit), and
a
is a
suitably chosen constant. This generator has the state transition function
f
(
x
w−r
0
,
x
1
,...,
x
n−
1
)=(
x
w−r
,
x
2
,...,
x
n
)
,
1
where
x
n
is determined by the above recursion with
j
= 0, and the state space
is
S
=
nw−
2
.
The most popular instance, named MT19937, uses the parameters
n
= 624,
w
= 32,
r
= 31. Its sequence has a maximal period equal to the Mersenne prime
2
19937
F
1. Because of its high speed and good distribution property, MT19937
is widely used as a standard PRNG. However, is had been lacking an ecient
jumping-ahead method, and this was a motivation for the work of [6].
−
Proposition 2.
For the MT generator, if we choose the output function
o
:(
x
w−r
0
,
x
1
,...,
x
n−
1
)
→
the LSB of
x
1
,
then the inverse image by
o
(
k
)
is computable with time complexity
O
(
k
)
.Asa
result, jumping ahead can be done in
O
(
k
1
.
59
)
time if we use Karatsuba's poly-
nomial multiplication, and in
O
(
k
log
k
)
time if we use a fast Fourier transform.
Proof.
A tricky algorithm that does that is described in [4, Section 4.3,
Proposition 4.2].
The twisted GFSR generator [15] is based on the same construction as MT, but
with
r
= 0. Thus, the proposition also applies to it.
