Permuted congruential generator

Last updated February 01, 2024

A permuted congruential generator (PCG) is a pseudorandom number generation algorithm developed in 2014 by Dr. M.E. O'Neill which applies an output permutation function to improve the statistical properties of a modulo-2ⁿ linear congruential generator. It achieves excellent statistical performance^[1]^[2]^[3]^[4] with small and fast code, and small state size.^[5]

the LCG modulus and state is larger, usually twice the size of the desired output,
it uses a power-of-2 modulus, which results in a particularly efficient implementation with a full period generator and unbiased output bits, and
the state is not output directly, but rather the most significant bits of the state are used to select a bitwise rotation or shift which is applied to the state to produce the output.

It is the variable rotation which eliminates the problem of a short period in the low-order bits that power-of-2 LCGs suffer from.^[5]^: 31–34

Variants

The PCG family includes a number of variants. The core LCG is defined for widths from 8 to 128 bits, although only 64 and 128 bits are recommended for practical use; smaller sizes are for statistical tests of the technique.

The additive constant in the LCG can be varied to produce different streams. The constant is an arbitrary odd integer,^[6] so it does not need to be stored explicitly; the address of the state variable itself (with the low bit set) can be used.

There are several different output transformations defined. All perform well, but some have a larger margin than others.^[5]^: 39 They are built from the following components:

RR: A random (input-dependent) rotation, with output half the size of input. Given a 2^b-bit input word, the top b−1 bits are used for the rotate amount, the next-most-significant 2^b−1 bits are rotated right and used as the output, and the low 2^b−1+1−b bits are discarded.
RS: A random (input-dependent) shift, for cases where rotates are more expensive. Again, the output is half the size of the input. Beginning with a 2^b-bit input word, the top b−3 bits are used for a shift amount, which is applied to the next-most-significant 2^b−1+2^b−3−1 bits, and the least significant 2^b−1 bits of the result are output. The low 2^b−1−2^b−3−b+4 bits are discarded.
XSH: An xorshift operation, x ^= x >> constant. The constant is chosen to be half of the bits not discarded by the next operation (rounded down).
XSL: A simplified version of xorshift, folding the value in half by XORing the high half into the low. The folded value is used for subsequent rotations.
RXS: An xorshift by a random (input-dependent) amount.
M: A multiply by a fixed constant.

These are combined into the following recommended output transformations, illustrated here in their most common sizes:

XSH-RR: An xorshift mixes some high-order bits down, then bits 63–59 select a rotate amount to be applied to bits 27–58.
(64→32 bits)count = (int)(x >> 59); x ^= x >> 18; return rotr32((uint32_t)(x >> 27), count);.
XSH-RS: Similar, but fewer bits select the shift amount.
(64→32 bits)count = (int)(x >> 61); x ^= x >> 22; return (uint32_t)(x >> (29 - count));.
XSL-RR: A simplified version of XSH-RR, this is optimized for 128-bit states implemented using two words on 64-bit machines.
(128→64 bits)count = (int)(x >> 122); x64 = (uint64_t)(x ^ (x >> 64)); return rotr64(x64, count);
RXS-M-XS: The slowest and strongest output transformation when used to produce half-size output, this becomes the weakest when used as intended, to produce an output the same size as the state. For use when the state size must be limited to 32 or 64 bits.
(32→32 bits)count=(int)(x >> 28); x ^= x >> (4 + count); x *= 277803737u; return x ^ (x >> 22);
(64→64 bits)count=(int)(x >> 59); x ^= x >> (5 + count); x *= 12605985483714917081u; return x ^ (x >> 43);
XSL-RR-RR: Similar to the preceding, this turns 128 bits of state into 128 bits of output, when the application demands it.
(128→128 bits)count = (int)(x >> 122); low64 = rotr64((uint64_t)(x ^ (x >> 64)), count); high64 = rotr64((uint64_t)(x >> 64), low64 & 63); return (uint128_t)high64 << 64 | low64;

Each step of these output transformations is either invertible (and thus one-to-one) or a truncation, so their composition maps the same fixed number of input states to each output value. This preserves the equidistribution of the underlying LCG.

Finally, if a cycle length longer than 2¹²⁸ is required, the generator can be extended with an array of sub-generators. One is chosen (in rotation) to be added to the main generator's output, and every time the main generator's state reaches zero, the sub-generators are cycled in a pattern which provides a period exponential in the total state size.

Example code

The generator recommended for most users^[5]^: 43 is PCG-XSH-RR with 64-bit state and 32-bit output. It can be implemented as:

#include<stdint.h>staticuint64_tstate=0x4d595df4d0f33173;// Or something seed-dependentstaticuint64_tconstmultiplier=6364136223846793005u;staticuint64_tconstincrement=1442695040888963407u;// Or an arbitrary odd constantstaticuint32_trotr32(uint32_tx,unsignedr){returnx>>r|x<<(-r&31);}uint32_tpcg32(void){uint64_tx=state;unsignedcount=(unsigned)(x>>59);// 59 = 64 - 5state=x*multiplier+increment;x^=x>>18;// 18 = (64 - 27)/2returnrotr32((uint32_t)(x>>27),count);// 27 = 32 - 5}voidpcg32_init(uint64_tseed){state=seed+increment;(void)pcg32();}

The generator applies the output transformation to the initial state rather than the final state in order to increase the available instruction-level parallelism to maximize performance on modern superscalar processors.^[5]^: 43

A slightly faster version eliminates the increment, reducing the LCG to a multiplicative (Lehmer-style) generator with a period of only 2⁶², and uses the weaker XSH-RS output function:

staticuint64_tmcg_state=0xcafef00dd15ea5e5u;// Must be oddstaticuint64_tconstmultiplier=6364136223846793005u;uint32_tpcg32_fast(void){uint64_tx=mcg_state;unsignedcount=(unsigned)(x>>61);// 61 = 64 - 3mcg_state=x*multiplier;x^=x>>22;return(uint32_t)(x>>(22+count));// 22 = 32 - 3 - 7}voidpcg32_fast_init(uint64_tseed){mcg_state=2*seed+1;(void)pcg32_fast();}

The time saving is minimal, as the most expensive operation (the 64×64-bit multiply) remains, so the normal version is preferred except in extremis. Still, this faster version also passes statistical tests.^[4]

When executing on a 32-bit processor, the 64×64-bit multiply must be implemented using three 32×32→64-bit multiply operations. To reduce that to two, there are 32-bit multipliers which perform almost as well as the 64-bit one, such as 0xf13283ad^[6], 0xffffffff0e703b65 or 0xf2fc5985.

Comparison with other pseudorandom number generators

Melissa O'Neill proposes testing PRNGs by applying statistical tests to their reduced-size variants and determining the minimum number of internal state bits required to pass.^[7] TestU01's BigCrush examines enough data to detect a period of 2³⁵, so even an ideal generator requires 36 bits of state to pass it. Some very poor generators can pass if given a large enough state;^[8] passing despite a small state is a measure of an algorithm's quality, and shows how large a safety margin exists between that lower limit and the state size used in practical applications.

PCG-RXS-M-XS (with 32-bit output) passes BigCrush with 36 bits of state (the minimum possible), PCG-XSH-RR (pcg32() above) requires 39, and PCG-XSH-RS (pcg32_fast() above) requires 49 bits of state. For comparison, xorshift*, one of the best of the alternatives, requires 40 bits of state,^[5]^: 19 and Mersenne twister fails despite 19937 bits of state.^[9]

Prediction and seed-recovery

It has been shown that it is practically possible (with a large computation) to recover the seed of the pseudo-random generator given 512 consecutive output bytes.^[10] This implies that it is practically possible to predict the rest of the pseudo-random stream given 512 bytes.

Related Research Articles

Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in software, and no effective cryptanalysis of it has been found to date. However, the Advanced Encryption Standard (AES) now receives more attention, and Schneier recommends Twofish for modern applications.

A hash function is any function that can be used to map data of arbitrary size to fixed-size values, though there are some hash functions that support variable length output. The values returned by a hash function are called hash values, hash codes, hash digests, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.

A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility.

A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modular arithmetic by storage-bit truncation.

The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by Makoto Matsumoto and Takuji Nishimura. Its name derives from the fact that its period length is chosen to be a Mersenne prime.

In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.

<span class="mw-page-title-main">Serpent (cipher)</span>

Serpent is a symmetric key block cipher that was a finalist in the Advanced Encryption Standard (AES) contest, in which it ranked second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen.

In cryptography, XTEA is a block cipher designed to correct weaknesses in TEA. The cipher's designers were David Wheeler and Roger Needham of the Cambridge Computer Laboratory, and the algorithm was presented in an unpublished technical report in 1997. It is not subject to any patents.

The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of bits, this is the number of 1's in the string, or the digit sum of the binary representation of a given number and the ℓ₁ norm of a bit vector. In this binary case, it is also called the population count, popcount, sideways sum, or bit summation.

In cryptography, a message authentication code based on universal hashing, or UMAC, is a type of message authentication code (MAC) calculated choosing a hash function from a class of hash functions according to some secret (random) process and applying it to the message. The resulting digest or fingerprint is then encrypted to hide the identity of the hash function used. As with any MAC, it may be used to simultaneously verify both the data integrity and the authenticity of a message. In contrast to traditional MACs, which are serializable, UMAC can be executed in parallel. Thus as machines continue to offer more parallel processing capabilities, the speed of implementing UMAC will increase.

SystemVerilog, standardized as IEEE 1800, is a hardware description and hardware verification language used to model, design, simulate, test and implement electronic systems. SystemVerilog is based on Verilog and some extensions, and since 2008, Verilog is now part of the same IEEE standard. It is commonly used in the semiconductor and electronic design industry as an evolution of Verilog.

Salsa20 and the closely related ChaCha are stream ciphers developed by Daniel J. Bernstein. Salsa20, the original cipher, was designed in 2005, then later submitted to the eSTREAM European Union cryptographic validation process by Bernstein. ChaCha is a modification of Salsa20 published in 2008. It uses a new round function that increases diffusion and increases performance on some architectures.

The grid method of multiplication is an introductory approach to multi-digit multiplication calculations that involve numbers larger than ten. Because it is often taught in mathematics education at the level of primary school or elementary school, this algorithm is sometimes called the grammar school method.

In computer science, multiply-with-carry (MWC) is a method invented by George Marsaglia for generating sequences of random integers based on an initial set from two to many thousands of randomly chosen seed values. The main advantages of the MWC method are that it invokes simple computer integer arithmetic and leads to very fast generation of sequences of random numbers with immense periods, ranging from around $to .$

The Lehmer random number generator, sometimes also referred to as the Park–Miller random number generator, is a type of linear congruential generator (LCG) that operates in multiplicative group of integers modulo n. The general formula is

<span class="mw-page-title-main">Xorshift</span> Class of pseudorandom number generators

Xorshift random number generators, also called shift-register generators, are a class of pseudorandom number generators that were invented by George Marsaglia. They are a subset of linear-feedback shift registers (LFSRs) which allow a particularly efficient implementation in software without the excessive use of sparse polynomials. They generate the next number in their sequence by repeatedly taking the exclusive or of a number with a bit-shifted version of itself. This makes execution extremely efficient on modern computer architectures, but it does not benefit efficiency in a hardware implementation. Like all LFSRs, the parameters have to be chosen very carefully in order to achieve a long period.

bcrypt is a password-hashing function designed by Niels Provos and David Mazières, based on the Blowfish cipher and presented at USENIX in 1999. Besides incorporating a salt to protect against rainbow table attacks, bcrypt is an adaptive function: over time, the iteration count can be increased to make it slower, so it remains resistant to brute-force search attacks even with increasing computation power.

MurmurHash is a non-cryptographic hash function suitable for general hash-based lookup. It was created by Austin Appleby in 2008 and is currently hosted on GitHub along with its test suite named 'SMHasher'. It also exists in a number of variants, all of which have been released into the public domain. The name comes from two basic operations, multiply (MU) and rotate (R), used in its inner loop.

TestU01 is a software library, implemented in the ANSI C language, that offers a collection of utilities for the empirical randomness testing of random number generators (RNGs). The library was first introduced in 2007 by Pierre L’Ecuyer and Richard Simard of the Université de Montréal.

KISS (Keep it Simple Stupid) is a family of pseudorandom number generators introduced by George Marsaglia. Starting from 1998 Marsaglia posted on various newsgroups including sci.math, comp.lang.c, comp.lang.fortran and sci.stat.math several versions of the generators. All KISS generators combine three or four independent random number generators with a view to improving the quality of randomness. KISS generators produce 32-bit or 64-bit random integers, from which random floating-point numbers can be constructed if desired. The original 1993 generator is based on the combination of a linear congruential generator and of two linear feedback shift-register generators. It has a period 2⁹⁵, good speed and good statistical properties; however, it fails the LinearComplexity test in the Crush and BigCrush tests of the TestU01 suite. A newer version from 1999 is based on a linear congruential generator, a 3-shift linear feedback shift-register and two multiply-with-carry generators. It is 10–20% slower than the 1993 version but has a larger period 2¹²³ and passes all tests in TestU01. In 2009 Marsaglia presented a version based on 64-bit integers (appropriate for 64-bit processors) which combines a multiply-with-carry generator, a Xorshift generator and a linear congruential generator. It has a period of around 2²⁵⁰ (around 10⁷⁵).

References

↑ Lemire, Daniel (22 August 2017). "Testing non-cryptographic random number generators: my results" . Retrieved 2017-10-03.
↑ Cook, John D. (7 July 2017). "Testing the PCG random number generator" . Retrieved 2017-10-03.
↑ Cook, John D. (14 August 2017). "Testing RNGs with PractRand" . Retrieved 2017-10-03.
1 2 O'Neill, M.E. (29 July 2017). "PCG Passes PractRand" . Retrieved 2017-11-03.
1 2 3 4 5 6 O'Neill, Melissa E. (5 September 2014). PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (PDF) (Technical report). Harvey Mudd College. HMC-CS-2014-0905.
1 2 O'Neill, M.E. (10 August 2017). "Critiquing PCG's streams (and SplitMix's too)" . Retrieved 2017-11-03.
↑ O'Neill, M.E. (20 August 2017). "Visualizing the Heart of Some PRNGs" . Retrieved 2017-11-03.
↑ O'Neill, M.E. (20 August 2017). "Too Big to Fail" . Retrieved 2017-11-03.
↑ L'Ecuyer, Pierre; Simard, Richard (August 2007). "TestU01: A C library for empirical testing of random number generators" (PDF). ACM Transactions on Mathematical Software . 33 (4): 22-1–22-40. CiteSeerX 10.1.1.499.2830 . doi:10.1145/1268776.1268777. S2CID 273446.
↑ Bouillaguet, Charles; Martinez, Florette; Sauvage, Julia (28 September 2020). "Practical seed-recovery for the PCG Pseudo-Random Number Generator". IACR Transactions on Symmetric Cryptology. 2020 (3): 175–196. doi:10.13154/tosc.v2020.i3.175-196. S2CID 222137612.

External links

PCG, A Family of Better Random Number Generators Website
PCG, A Family of Better Random Number Generators — inspired by /r/programming! Reddit discussion by the author

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Lemire, Daniel (22 August 2017). "Testing non-cryptographic random number generators: my results" . Retrieved 2017-10-03.

[2] Cook, John D. (7 July 2017). "Testing the PCG random number generator" . Retrieved 2017-10-03.

[3] Cook, John D. (14 August 2017). "Testing RNGs with PractRand" . Retrieved 2017-10-03.

[pcg-passes-4] 1 2 O'Neill, M.E. (29 July 2017). "PCG Passes PractRand" . Retrieved 2017-11-03.

[ONeill-5] 1 2 3 4 5 6 O'Neill, Melissa E. (5 September 2014). PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (PDF) (Technical report). Harvey Mudd College. HMC-CS-2014-0905.

[critiquing-6] 1 2 O'Neill, M.E. (10 August 2017). "Critiquing PCG's streams (and SplitMix's too)" . Retrieved 2017-11-03.

[7] O'Neill, M.E. (20 August 2017). "Visualizing the Heart of Some PRNGs" . Retrieved 2017-11-03.

[8] O'Neill, M.E. (20 August 2017). "Too Big to Fail" . Retrieved 2017-11-03.

[9] L'Ecuyer, Pierre; Simard, Richard (August 2007). "TestU01: A C library for empirical testing of random number generators" (PDF). ACM Transactions on Mathematical Software . 33 (4): 22-1–22-40. CiteSeerX 10.1.1.499.2830 . doi:10.1145/1268776.1268777. S2CID 273446.

[10] Bouillaguet, Charles; Martinez, Florette; Sauvage, Julia (28 September 2020). "Practical seed-recovery for the PCG Pseudo-Random Number Generator". IACR Transactions on Symmetric Cryptology. 2020 (3): 175–196. doi:10.13154/tosc.v2020.i3.175-196. S2CID 222137612.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]