peteroupc.github.io

Examples of High-Quality PRNGs

Besides cryptographic random number generators (RNGs), the following are examples of high-quality pseudorandom number generators (PRNGs). The “Fails PractRand Starting At” column in this and other tables in this page means the number of bytes (rounded up to the nearest power of two) at which PractRand detects a failure in the PRNG. (Note that high-quality PRNGs, as I define them, are not necessarily appropriate for information security.)

PRNG Seeds Allowed Cycle Length Fails PractRand Starting At Notes
xoshiro256** 2^256 - 1 2^256 - 1 ??? TiB  
xoshiro256+ 2^256 - 1 2^256 - 1 ??? TiB Lowest bits have low linear complexity (see (Blackman and Vigna 2019)(1) and see also “Testing low bits in isolation”); if the application or library cares, it can discard those bits before using this PRNG’s output.
xoshiro256++ 2^256 - 1 2^256 - 1 ??? TiB  
xoshiro512** 2^512 - 1 2^512 - 1 ??? TiB  
xoshiro512+ 2^512 - 1 2^512 - 1 ??? TiB Lowest bits have low linear complexity
xoshiro512++ 2^512 - 1 2^512 - 1 ??? TiB  
xoroshiro128++ 2^128 - 1 2^128 - 1 ??? TiB  
xoroshiro128** 2^128 - 1 2^128 - 1 ??? TiB  
SFC64 (C. Doty-Humphrey) 2^192 At least 2^64 per seed ??? TiB 256-bit state
Philox4×64-7 2^128 At least 2^256 per seed ??? TiB 384-bit state
Velox3b 2^64 At least 2^128 per seed ??? TiB 256-bit state
gjrand named after Geronimo Jones 2^128 At least 2^64 per seed ??? TiB 256-bit state
MRG32k3a (L’Ecuyer 1999; L’Ecuyer et al. 2002)(2) Near 2^192 2 cycles with length near 2^191 ??? TiB 192-bit state
MRG31k3p (L’Ecuyer and Touzin 2000)(3) Near 2^186 2 cycles with length near 2^185 ??? TiB 192-bit state
JLKISS (Jones 2007/2010)(4) 2^64 * (2^64 - 1)^2 At least (2^128 - 2^64) ??? TiB 192-bit state
JLKISS64 (Jones 2007/2010)(4) 2^64 * (2^64 - 1)^3 At least (2^128 - 2^64) ??? TiB 256-bit state
A multiplicative linear congruential generator (LCG) with prime modulus greater than 263 described in Table 2 of (L’Ecuyer 1999)(5) Modulus - 1 Modulus - 1 ??? TiB Memory used depends on modulus size
XorShift* 128/64 2^128 - 1 2^128 - 1 ??? TiB 128-bit state. Described by M. O’Neill in “You don’t have to use PCG!”, 2017.(6)
XorShift* 64/32 2^64 - 1 2^64 - 1 ??? TiB 64-bit state. Described by M. O’Neill in “You don’t have to use PCG!”, 2017.

PRNGs with Stream Support

Some PRNGs support multiple “streams” that behave like independent random number sequences. The test for independence involves interleaving two “streams”’ outputs and sending the interleaved outputs to the PractRand tests.

The following lists high-quality PRNGs that support streams and their PractRand results for different strategies of forming random number “streams”.

PRNG Fails PractRand Starting At Notes
xoshiro256** Jump-ahead by 2^64: ??? TiB
Jump-ahead by 2^128: ??? TiB
Jump-ahead by 2^256/φ: ??? TiB
Consecutive seeds: ??? TiB
 
xoshiro256++ Jump-ahead by 2^64: ??? TiB
Jump-ahead by 2^128: ??? TiB
Jump-ahead by 2^256/φ: ??? TiB
Consecutive seeds: ??? TiB
 
xoroshiro128** Jump-ahead by 2^64: ??? TiB
Jump-ahead by 2^128/φ: ??? TiB
Consecutive seeds: ??? TiB
 
xoroshiro128++ Jump-ahead by 2^64: ??? TiB
Jump-ahead by 2^128/φ: ??? TiB
Consecutive seeds: ??? TiB
 
SFC64 Consecutive seeds: ??? TiB
Seed increment by 2^64: ??? TiB
 
Philox4×64-7 Consecutive seeds: ??? TiB
Seed increment by 2^64: ??? TiB
 
PCG64 Jump-ahead by period/φ: ??? TiB What PCG calls “streams” does not produce independent sequences.
??? Jump-ahead by period/φ: ??? TiB  

Counter-Based PRNGs

Constructions for counter-based PRNGs (using the definition from (Salmon et al. 2011)(7), section 2) include:

  1. A PRNG that outputs hash codes of a counter and the seed.
  2. A PRNG that uses a block cipher with the seed as a key to output encrypted counters.

More specifically, let C and S each be 64 or greater and divisible by 8. Then:

  1. A C-bit counter is set to 0 and an S-bit seed is chosen. In each iteration, the PRNG outputs H(seed || 0x5F || counter) (where H is a hash function, || means concatenation, 0x5F is the 8-bit block 0x5F, and seed and counter are little-endian encodings of the seed or counter, respectively), and adds 1 to the counter by wraparound addition. Or…
  2. A C-bit counter is set to 0 and an S-bit seed is chosen. In each iteration, the PRNG outputs E(counter, seed) (where E is a C-bit block cipher and seed and counter are little-endian encodings of the seed (key) or counter (cleartext), respectively), and adds 1 to the counter by wraparound addition.

The following lists hash functions and block ciphers that form high-quality counter-based PRNGs. It’s possible that reduced-round versions of these and other functions will also produce high-quality counter-based PRNGs.

Function Fails PractRand Starting At Notes
Hash Functions: BEBB4185; BLAKE2S-256; BLAKE3; CityHash64; Falkhash; FarmHash128; FarmHash32; FarmHash64; Farsh32; Farsh64; Floppsyhash; GoodOAAT; Half-SipHash; Hasshe2; MD5 (low 32 bits); Metrohash128; Mirhash; Mirhashstrict (low 32 bits); MUM; MurmurHash64A for x64; MurmurHash3 (128-bit) for x64; Seahash; Seahash (low 32 bits); SHA-256; SHA-256 (low 64 bits); SHA3-256; SipHash; Spooky64; Fast Positive Hash (32-bit big-endian); TSip; xxHash v3 64-bit (both full and low 32 bits) > 1 TiB S = 64, C = 128. Failure figure applies to regular sequence; 2, 4, and 11 interleaved streams from consecutive seeds; 2, 4, and 11 interleaved streams from counters incremented by 264; 2, 4, and 11 interleaved streams from counters incremented by 296.
??? ??? TiB (Consecutive seeds: ??? TiB)  
??? ??? TiB (Consecutive seeds: ??? TiB)  
??? ??? TiB (Consecutive seeds: ??? TiB)  

Combined PRNGs

The following lists high-quality combined PRNGs. See “Testing PRNGs for High-Quality Randomness” for more information on combining PRNGs.

Function Fails PractRand Starting At Notes
??? combined with Weyl sequence ??? TiB  
??? combined with 128-bit LCG ??? TiB  
JSF64 combined with ??? ??? TiB  
JSF64 combined with ??? ??? TiB  
Tyche combined with ??? ??? TiB  
Tyche-i combined with ??? ??? TiB  
??? combined with ??? ??? TiB  

Splittable PRNGs

The following lists high-quality splittable PRNGs. See “Testing PRNGs for High-Quality Randomness” for more information on testing splittable PRNGs, and see the appendix for splittable PRNG constructions.

Function Fails PractRand Starting At Notes
??? ??? TiB  
??? ??? TiB  
??? ??? TiB  

PRNGs Not Preferred

Although the following are technically high-quality PRNGs, they are not preferred:

PRNG Notes
C++’s std::ranlux48 engine Usually takes about 192 8-bit bytes of memory. Admits up to 2^577 - 2 seeds; seed’s bits cannot be all zeros or all ones (Lüscher 1994)(8). The maximum cycle length for ranlux48’s underlying generator is very close to 2^576.
A high-quality PRNG that is an LCG with non-prime modulus (or a PRNG based on one, such as PCG) If the modulus is a power of 2, this PRNG can produce highly correlated “random” number sequences from seeds that differ only in their high bits (see S. Vigna, “The wrap-up on PCG generators”) and lowest bits have short cycles. What PCG calls “streams” does not produce independent sequences.

Not High-Quality PRNGs

The following are not considered high-quality PRNGs:

Algorithm Notes
Sequential counter Doesn’t behave like independent random sequence
A linear congruential generator with modulus less than 263 (such as java.util.Random and C++’s std::minstd_rand and std::minstd_rand0 engines) Admits fewer than 263 seeds
Mersenne Twister (MT19937) Shows a systematic failure in BigCrush’s LinearComp test (part of L’Ecuyer and Simard’s “TestU01”). (See also (Vigna 2019)(9).) Moreover, it usually takes about 2500 8-bit bytes of memory.
Marsaglia’s xorshift family (“Xorshift RNGs”, 2003) Shows systematic failures in SmallCrush’s MatrixRank test (Vigna 2016)(10)
System.Random, as implemented in the .NET Framework 4.7 Admits fewer than 263 seeds
Ran2 (Numerical Recipes) Minimum cycle length less than 263
msws (Widynski 2017)(11) Admits fewer than 263 seeds (about 254.1 valid seeds)
JSF32 (B. Jenkins’s “A small noncryptographic PRNG”) Admits fewer than 263 seeds; proven minimum cycle length is only 220 or more
JSF64 (B. Jenkins’s “A small noncryptographic PRNG”) No proven minimum cycle of at least 263 values
Middle square No proven minimum cycle of at least 263 values
Many cellular-automaton PRNGs (especially if they are neither reversible nor maximal-length(12)) No proven minimum cycle of at least 263 values
Tyche/Tyche-i (Neves and Araujo 2011)(13) No proven minimum cycle of at least 263 values

Notes

Appendix

Implementation Notes: Splittable PRNGs

Here are implementation notes on splittable PRNGs. The pseudocode conventions apply to this section. In addition, the following notation is used:

The splittable PRNG designs described here use keyed hash functions, which hash a message with a given key and output a hash code. An unkeyed hash function can become a keyed hash function by hashing the following data: key || TOBYTES(0x5F, 1) || message.

The Claessen–Pałka splittable PRNG (Claessen and Pałka 2013)(14) can be described as follows:

(The Claessen paper, section 5, also shows how a sequence of numbers can be generated from a state, essentially by hashing the path with the seed as the key, and in turn hashing a counter with that hash code as the key, but uses a rather complicated encoding to achieve this.)

The following helper method, in pseudocode, is used in the description above:

METHOD BitsToBytes(bits)
   // Unfortunately, the Claessen paper sec. 3.3 pads
   // blocks with zeros, creating a risk that different paths
   // encode to the same byte sequence (e.g., <1100> vs.
   // <11000> or <0011> vs. <00011>). Even without this padding,
   // this risk exists unless the underlying hash function hashes
   // bit sequences (not just byte sequences), which is rare.
   // Therefore, encode the bits to a sequence of bytes
   // rather than using the encoding given in sec. 3.3.
   v = []
   for i in 0...size(bits): v = v || TOBYTES(bits[i], 1)
   return v
END METHOD

The splittable PRNG described in “JAX PRNG Design” can be described as follows: