### G-2006-62

# Efficient Jump Ahead for F_{2} -Linear Random Number Generators

## Hiroshi Haramoto, Makoto Matsumoto, Takuji Nishimura, François Panneton, and Pierre L'Ecuyer

The fastest long-period random number generators currently available are based on
linear recurrences modulo 2. So far, software that provides multiple disjoint streams
and substreams has not been available for these generators because of the lack of efficient jump-ahead facilities. In principle, it suffices to multiply the state (a *k*-bit vector)
by an appropriate *k* x *k* binary matrix to find the new state far ahead in the sequence.
However, when *k* is large (e.g., for a generator such as the popular Mersenne twister,
for which *k* = 19937), this matrix-vector multiplication is slow and a large amount of
memory is required to store the *k* x *k* matrix. In this paper, we provide a faster algorithm
to jump ahead by a large number of steps in a linear recurrence modulo 2. The
method uses much less than the *k*^{2} bits of memory required by the matrix method. It
is based on polynomial calculus modulo the characteristic polynomial of the recurrence
and uses a sliding window algorithm for the multiplication.

Published **October 2006**
,
15 pages