Some pseudorandom number generators (PRNGs) have an efficient way to advance their state as though a huge number of PRNG outputs were discarded. Notes on how they work are described in the following sections.
For some PRNGs, each bit of the PRNG’s state can be described as a linear recurrence on its entire state. These PRNGs are called F2-linear PRNGs, and they include the following:
For an F2-linear PRNG, there is an efficient way to discard a given (and arbitrary) number of its outputs (to “jump the PRNG ahead”). This jump-ahead strategy is further described in (Haramoto et al., 2008)(1). See also (Vigna 2017)(2). To calculate the jump-ahead parameters needed to advance the PRNG N steps:
M, an S×S matrix of zeros and ones that describes the linear transformation of the PRNG’s state, where S is the size of that state in bits. For an example, see sections 3.1 and 3.2 of (Blackman and Vigna 2019)(3), where it should be noted that the additions inside the matrix are actually XORs.
Find the characteristic polynomial of
M. This has to be done in the two-element field F2, so that each coefficient of the polynomial is either 0 or 1.
For example, SymPy’s
charpoly() method alone is inadequate for this purpose, since it doesn’t operate on the correct field. However, it’s easy to adapt that method’s output for the field F2: even coefficients become zeros and odd coefficients become ones.
Note that for a linear feedback shift register (LFSR) generator, the characteristic polynomial’s coefficients are 1 for each of its “taps” (and “tap” 0), and 0 elsewhere. For example, an LFSR generator with taps 6 and 8 has the characteristic polynomial x8 + x6 + 1.
The section “Jump Parameters for Some PRNGs” shows characteristic polynomials for some PRNGs and one way their coefficients can be represented.
powmodf2(2, N, CP), where
powmodf2is a modular power function that calculates
2^N mod CPin the field F2, and
CPis the characteristic polynomial. Regular modular power functions, such as BigInteger’s
modPowmethod, won’t work here, even if the polynomial is represented in the manner described in “Jump Parameters for Some PRNGs”.
The result is a jump polynomial for jumping the PRNG ahead N steps.
An example of its use is found in the
long_jump functions in the
xoroshiro128plus source code, which are identical except for the jump polynomial. In both functions, the jump polynomial’s coefficients are packed into a 128-bit integer (as described in “Jump Parameters for Some PRNGs”), which is then split into the lower 64 bits and the upper 64 bits, in that order.
Counter-based PRNGs, in which their state is updated simply by incrementing a counter, can be trivially jumped ahead just by changing the seed, the counter, or both (Salmon et al. 2011)(4).
A multiple recursive generator (MRG) generates numbers by transforming its state using the following formula:
x(k) = (x(k-1)*A(1) + x(k-2)*A(2) + ... + x(k-n)*A(n)) mod modulus, where
A(i) are the multipliers and
modulus is the modulus.
For an MRG, the following matrix (
M) describes the state transition
[x(k-n), ..., x(k-1)] to
[x(k-n+1), ..., x(k)] (mod
| 0 1 0 ... 0 | | 0 0 1 ... 0 | | . . . ... ... | | 0 0 0 ... 1 | |A(n)A(n A(n ... A(1)| | -1) -2) |
To calculate the parameter needed to jump the MRG ahead N steps, calculate
modulus; the result is a jump matrix
Then, to jump the MRG ahead N steps, calculate
J * S mod
J is the jump matrix and
S is the state in the form of a column vector; the result is a new state for the MRG.
This technique was mentioned (but for binary matrices) in Haramoto, in sections 1 and 3.1. They point out, though, that it isn’t efficient if the transition matrix is large. See also (L’Ecuyer et al., 2002)(5).
A multiple recursive generator with a modulus of 1449 has the following transition matrix:
| 0 1 0 | | 0 0 1 | | 444 342 499 |
To calculate the 3×3 jump matrix to jump 100 steps from this MRG, raise this matrix to the power of 100 then reduce the result’s elements mod 1449. One way to do this is the “square-and-multiply” method, described by D. Knuth in The Art of Computer Programming: Set J to the identity matrix, N to 100, and M to a copy of the transition matrix, then while N is greater than 0:
The resulting J is a jump matrix as follows:
| 156 93 1240 | | 1389 1128 130 | | 1209 930 793 |
Transforming the MRG’s state with J (and reducing mod 1449) will transform the state as though 100 outputs were discarded from the MRG.
A linear congruential generator (LCG) generates numbers by transforming its state using the following formula:
x(k) = (x(k-1)*a + c) mod modulus, where
a is the multiplier,
c is the additive constant, and
modulus is the modulus.
An efficient way to jump an LCG ahead is described in (Brown 1994)(6). This also applies to LCGs that transform each
x(k) before outputting it, such as M.O’Neill’s PCG32 and PCG64.
An MRG with only one multiplier expresses the special case of an LCG with
c = 0 (also known as a multiplicative LCG). For
c other than 0, the following matrix describes the state transition
[x(k-1), 1] to
[x(k), 1] (mod
| a c | | 0 1 |
Jumping the LCG ahead can then be done using this matrix as described in the previous section.
There are implementations for jumping a multiply-with-carry (MWC) PRNG ahead, but only in source code form (ref. 1). I am not aware of an article or paper that describes how jumping an MWC PRNG ahead works.
I am not aware of any efficient ways to jump an add-with-carry or subtract-with-borrow PRNG ahead an arbitrary number of steps.
A combined PRNG can be jumped ahead N steps by jumping each of its components ahead N steps.
The following table shows the characteristic polynomial and jump polynomials for some PRNG families. In the table:
|PRNG||Characteristic Polynomial||Jump Polynomials|
|xoroshiro128 (except ++)||0x10008828e513b43d5095b8f76579aa001||232: 0xd4e95eef9edbdbc6fad843622b252c78
Sebastiano Vigna reviewed this page and gave comments.