Counter-based random number generator

<h2 id="background">Background</h2>
We can think of a pseudorandom number generator (PRNG) as a function that transforms a series of bits known as the state into a new state and a random number.
That is, given a PRNG function and an initial state 
 
 
 
 
 
 s
 t
 a
 t
 e
 
 
 0
 
 
 
 
 {\displaystyle \mathrm {state} _{0}}
 
, we can repeatedly use the PRNG to generate a sequence of states and random numbers.

 
 
 
 
 
 
 
 
 P
 R
 N
 G
 
 (
 
 
 s
 t
 a
 t
 e
 
 
 0
 
 
 )
 
 
 
 =
 
 
 s
 t
 a
 t
 e
 
 
 1
 
 
 ,
  
 
 
 n
 u
 m
 
 
 1
 
 
 
 
 
 
 
 P
 R
 N
 G
 
 (
 
 
 s
 t
 a
 t
 e
 
 
 1
 
 
 )
 
 
 
 =
 
 
 s
 t
 a
 t
 e
 
 
 2
 
 
 ,
  
 
 
 n
 u
 m
 
 
 2
 
 
 
 
 
 
 
 P
 R
 N
 G
 
 (
 
 
 s
 t
 a
 t
 e
 
 
 2
 
 
 )
 
 
 
 =
 
 
 s
 t
 a
 t
 e
 
 
 3
 
 
 ,
  
 
 
 n
 u
 m
 
 
 3
 
 
 
 
 
 
 
 P
 R
 N
 G
 
 (
 
 
 s
 t
 a
 t
 e
 
 
 3
 
 
 )
 
 
 
 =
 …
 
 
 
 
 
 
 {\displaystyle {\begin{aligned}\mathrm {PRNG} (\mathrm {state} _{0})&=\mathrm {state} _{1},\ \mathrm {num} _{1}\\\mathrm {PRNG} (\mathrm {state} _{1})&=\mathrm {state} _{2},\ \mathrm {num} _{2}\\\mathrm {PRNG} (\mathrm {state} _{2})&=\mathrm {state} _{3},\ \mathrm {num} _{3}\\\mathrm {PRNG} (\mathrm {state} _{3})&=\ldots \end{aligned}}}

In some PRNGs, such as the <a href="/facts/Mersenne_Twister/R6Knca0q">Mersenne Twister</a>, the state is large, more than 2048 bytes. In other PRNGs, such as <a href="/facts/Xorshift/N6cr5Tfw">xorshift</a>, 
 
 
 
 
 
 s
 t
 a
 t
 e
 
 
 i
 
 
 
 
 {\displaystyle \mathrm {state} _{i}}
 
 and 
 
 
 
 
 
 n
 u
 m
 
 
 i
 
 
 
 
 {\displaystyle \mathrm {num} _{i}}
 
 are one and the same (and so the state is small, just 4, 8, or 16 bytes, depending on the size of the numbers being generated). But in both cases, and indeed in most traditional PRNGs, the state evolves unpredictably, so if you want to calculate a particular 
 
 
 
 
 
 s
 t
 a
 t
 e
 
 
 i
 
 
 
 
 {\displaystyle \mathrm {state} _{i}}
 
 given an initial state 
 
 
 
 
 
 s
 t
 a
 t
 e
 
 
 0
 
 
 
 
 {\displaystyle \mathrm {state} _{0}}
 
, you have to calculate 
 
 
 
 
 
 s
 t
 a
 t
 e
 
 
 1
 
 
 
 
 {\displaystyle \mathrm {state} _{1}}
 
, 
 
 
 
 
 
 s
 t
 a
 t
 e
 
 
 2
 
 
 
 
 {\displaystyle \mathrm {state} _{2}}
 
, and so on, running the PRNG 
 
 
 
 i
 
 
 {\displaystyle i}
 
 times.
Such algorithms are inherently sequential and not amenable to running on parallel machines like <a href="/facts/Multi-core_CPU/ABNb65hQ">multi-core CPUs</a> and <a href="/facts/GPU/PTK1RQVp">GPUs</a>.
In contrast, a counter-based random number generator (CBRNG) is a PRNG where the state "evolves" in a particularly simple manner: 
 
 
 
 
 
 s
 t
 a
 t
 e
 
 
 i
 
 
 =
 i
 
 
 {\displaystyle \mathrm {state} _{i}=i}
 
. This way you can generate each number independently, without knowing the result of the previous call to the PRNG.
This property make it easy to run a CBRNG on a multiple CPU threads or a GPU. For example, to generate 
 
 
 
 n
 
 
 {\displaystyle n}
 
 random numbers on a GPU, you might spawn 
 
 
 
 n
 
 
 {\displaystyle n}
 
 threads and have the 
 
 
 
 i
 
 
 {\displaystyle i}
 
th thread calculate 
 
 
 
 
 P
 R
 N
 G
 
 (
 i
 )
 
 
 {\displaystyle \mathrm {PRNG} (i)}
 
.

<h2 id="cbrngs-based-on-block-ciphers">CBRNGs based on block ciphers</h2>
Some CBRNGs are based on reduced-strength versions of <a href="/facts/Block_cipher/MJywAyfQ">block ciphers</a>. Below we explain how this works.
When using a cryptographic <a href="/facts/Block_cipher/MJywAyfQ">block cipher</a> in <a href="/facts/Block_cipher_mode_of_operation/vIUabB2z">counter mode</a>, you generate a series of blocks of random bits. The 
 
 
 
 i
 
 
 {\displaystyle i}
 
th block is calculated by encrypting the number 
 
 
 
 i
 
 
 {\displaystyle i}
 
 using the encryption key 
 
 
 
 k
 
 
 {\displaystyle k}
 
: 
 
 
 
 
 
 B
 l
 o
 c
 k
 
 
 i
 
 
 =
 E
 (
 i
 ,
 k
 )
 
 
 {\displaystyle \mathrm {Block} _{i}=E(i,k)}
 
.
This is similar to a CBRNG, where you calculate the 
 
 
 
 i
 
 
 {\displaystyle i}
 
th random number as 
 
 
 
 
 P
 R
 N
 G
 
 (
 i
 )
 
 
 {\displaystyle \mathrm {PRNG} (i)}
 
. Indeed, any block cipher can be used as a CBRNG; simply let 
 
 
 
 
 P
 R
 N
 G
 
 (
 i
 )
 =
 E
 (
 i
 ,
 
 s
 e
 e
 d
 
 )
 
 
 {\displaystyle \mathrm {PRNG} (i)=E(i,\mathrm {seed} )}
 
!
This yields a strong, <a href="/facts/Cryptographically_secure_pseudorandom_number_generator/Kew9SdpN">cryptographically-secure source of randomness</a>. But cryptographically-secure pseudorandom number generators tend to be slow compared to insecure PRNGs, and in practice many uses of random numbers don't require this degree of security.
In 2011, Salmon et al. at <a href="/facts/D._E._Shaw_Research/FgujNE8M">D. E. Shaw Research</a> introduced<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> two CBRNGs based on reduced-strength versions of block ciphers.

<ul><li>Threefry uses a reduced-strength version of the <a href="/facts/Threefish/xGnFbEtW">Threefish</a> block cipher. (Juvenile fish are known as "<a href="/facts/Juvenile_fish/uG7v6n2X">fry</a>".)</li></ul>
<ul><li>ARS uses a reduced-strength version of the <a href="/facts/Advanced_Encryption_Standard/HdXGBY2Q">AES</a> block cipher. ("ARS" is a pun on "AES"; "AES" stands for "advanced encryption standard", and "ARS" stands for "advanced randomization system"<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>).</li></ul>
ARS is used in recent versions of Intel's <a href="/facts/Math_Kernel_Library/nwPPAUpe">Math Kernel Library</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> and gets good performance by using instructions from the <a href="/facts/AES-NI/NomFEB4w">AES-NI</a> instruction set, which specifically accelerate AES encryption.
Code implementing Threefry, ARS, and Philox (see below) is available from the authors.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="cbrngs-based-on-multiplication">CBRNGs based on multiplication</h2>
In addition to Threefry and ARS, Salmon et al. described a third counter-based PRNG, Philox,<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> based on wide multiplies; e.g. multiplying two 32-bit numbers and producing a 64-bit number, or multiplying two 64-bit numbers and producing a 128-bit number.
As of 2020, Philox is popular on CPUs and GPUs. On GPUs, <a href="/facts/NVidia/8QfCgqbu">nVidia</a>'s cuRAND library<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> and <a href="/facts/TensorFlow/kDwfBeNd">TensorFlow</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> provide implementations of Philox. On CPUs, Intel's <a href="/facts/Math_Kernel_Library/nwPPAUpe">MKL</a> provides an implementation.
A new CBRNG based on multiplication is the Squares RNG.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> This generator passes stringent tests of randomness<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> and is considerably faster than Philox.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Salmon, John; Moraes, Mark; Dror, Ron; Shaw, David (2011). "Parallel random numbers: as easy as 1, 2, 3". Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, Article No. 16. doi:10.1145/2063384.2063405. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">"Random123: A Library of Counter-Based Random Number Generators". Retrieved August 8, 2020. <a href="http://www.thesalmons.org/john/random123/releases/1.11.2pre/docs/" target="_blank">http://www.thesalmons.org/john/random123/releases/1.11.2pre/docs/</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Fedorov, Gennady; Gladkov, Eugeny (2015). "New counter-based Random Number Generators in Intel® Math Kernel Library". Intel. Retrieved August 22, 2016. <a href="https://software.intel.com/en-us/articles/new-counter-based-random-number-generators-in-intel-math-kernel-library" target="_blank">https://software.intel.com/en-us/articles/new-counter-based-random-number-generators-in-intel-math-kernel-library</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">"Random123". <a href="https://github.com/DEShawResearch/random123" target="_blank">https://github.com/DEShawResearch/random123</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Salmon, John; Moraes, Mark; Dror, Ron; Shaw, David (2011). "Parallel random numbers: as easy as 1, 2, 3". Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, Article No. 16. doi:10.1145/2063384.2063405. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">"Device API Overview". Retrieved August 8, 2020. <a href="https://docs.nvidia.com/cuda/curand/device-api-overview.html" target="_blank">https://docs.nvidia.com/cuda/curand/device-api-overview.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">"Random number generation | TensorFlow Core". <a href="https://www.tensorflow.org/guide/random_numbers#general" target="_blank">https://www.tensorflow.org/guide/random_numbers#general</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Widynski, Bernard (2020). "Squares: A Fast Counter-Based RNG". arXiv:2004.06278 [cs.DS]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">L’Ecuyer, Pierre; Nadeau-Chamard, Oliver; Chen, Yi-Fan; Lebar, Justin (2021). "Multiple streams with recurrence-based, counter-based, and splittable random number generators". 2021 Winter Simulation Conference (WSC). IEEE, 2021. <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
</ol>

Counter-based random number generator open-in-new

Counter-based random number generator