PRNG#
A PRNG is a
BRNG that produces a stream of variates
that are independent and statistically indistinguishable from a random sequence.
A PRNG has several advantages over a
True Random Number Generator in that the generated sequence is repeatable,
has known mathematical properties and is usually much quicker to generate.
NAG Basic#
The NAG basic generator is a linear congruential generator (LCG) and, like all LCGs, has the form:
where the \(u_i, i = 1, 2, · · ·\) form the required sequence.
The NAG basic generator takes \(a_1 = 13^{13}\) and \(m_1 = 2^{59}\), which gives a period of approximately \(2^{57}\). This generator has been part of the NAG numerical library since Mark 6 and as such has been widely used. It suffers from no known problems, other than those due to the lattice structure inherent in all LCGs, and, even though the period is relatively short compared to many of the newer generators, it is sufficiently large for many practical problems. [NAG05]
Wichmann-Hill#
The Wichmann-Hill base generator uses a combination of four linear congruential generators (LCGs) and has the form:
where the \(u_i, i = 1, 2, · · ·\) form the required sequence. There are 273 sets of parameters, {\(a_i, m_i\) : i = 1, 2, 3, 4}, to choose from. These values have been selected so that the resulting generators are independent and have a period of approximately \(2^{80}\). [Maclaren]
Mersenne Twister#
The Mersenne Twister is a twisted generalized feedback shift register generator. The algorithm is as follows: * Set some arbitrary initial values \(x_1, x_2, · · · , x_r\), each consisting of w bits. * Letting
where \(\mathbf I_{w−1}\) is the \((w-1)\times(w-1)\) identity matrix and each of the \(a_i, i = 1\ to\ w\) take a value of either 0 or 1 (i.e. they can be represented as bits).
Define
where \(\mathcal X_{i}^{(w:(l+1))} | \mathcal X_{i+1}^{(l:1)}\) indicates the concatenation of the most significant (upper) \(w − l\) bits of \(\mathcal X_i\) and the least significant (lower) \(\mathcal l\) bits of \(\mathcal X_{i+1}\).
Perform the following operations sequentially:
where \(t_1, t_2, t_3\) and \(t_4\) are integers and \(m_1\) and \(m_2\) are bit-masks and >>t and <<t represent a t bit shift right and left respectively, is bit-wise exclusively or (xor) operation and AND is a bit-wise and operation.
The \(u_{i+r} : i = 1, 2,…\) then form a pseudo-random sequence, with \(u_i \in (0, 1)\), for all i. This implementation of the Mersenne Twister uses the following values for the algorithmic constants:
where the notation \(0 \times DD \dotsc`\) indicates the bit pattern of the integer whose hexadecimal representation is \(DD \dotsc\).
This algorithm has a period length of approximately \(2^{19,937} − 1\) and has been shown to be uniformly distributed in 623 dimensions. [MT]
SFMT#
SFMT is known as SIMD-oriented Fast Mersenne Twister which is a new variant of Mersenne Twister. SFMT is a Linear Feedbacked Shift Register generator that generates 128-bit pseudorandom integer recursively. The algorithm is as follows:
Set some arbitrary initial values \(W_0, W_1, · · · , W_{N-1}\), each consisting of 128 bits.
Perform recursive operation:
Where \(W_0, W_M,…\) are 128-bit integers, and A,B,C,D are sparse
\(128 \times 128\) matrices over (0,1) for which
\(W_A,W_B,W_C,W_D\) can be computed.
The degree of recursion N is [19937/128] = 156, and the linear
transformations A,B,C,D are as follows.
This algorithm has a period length of approximately \(2^{19,937} − 1\) and has better equidistribution property than Mersenne Twister. [SFMT]
MRG32K3A#
MRG32K3A is a L’Ecuyer’s Combined Recursive Generator which combines two multiple recursive generators:
where the \(u_i, i = 1, 2, \dotsc\) form the required sequence and \(a_{11} = 0, a_{12} = 1403580,\) \(a_{13} =−810728, m_1 = 2^{32} − 209, a_{21} = 527612, a_{22} = 0, a_{23} = −1370589 \ and \ m_2 = 2^{32} − 22853\).
Combining the two multiple recursive generators (MRG) results in sequences with better statistical properties in high dimensions and longer periods compared with those generated from a single MRG. The combined generator described above has a period length of approximately \(2^{191}\). [MRG32K3A]
Blum-Blum-Shub#
Caution
This BBS generator is deprecated. It’s better to use SecureRNG instead, which provides hardware-based cryptographically secure random numbers.
A PRNG is said to be cryptographically secure if there is no polynomial-time algorithm which, on input of the first l bits of the output sequence, can predict the (l+1)st bit of the sequence with probability significantly greater than 0.5. This is equivalent to saying there exists no polynomial-time algorithm that can correctly distinguish between an output sequence from the PRNG and a truly random sequence of the same length with probability significantly greater than 0.5 [Menezes].
The Blum-Blum-Shub pseudo-random number generator is cryptographically-secure under the assumption that the quadratic residuosity problem is intractable. The algorithm consists of the following:
Generate two large and distinct primes, p and q, each congruent to 3 mod 4. Define m = pq.
Select a seed s taking a value between 1 and m-1, such that the greatest common divisor between s and m is 1. Let \(x_0 = s^2\ mod \ m\). For \(I = 1, 2,\dotsc`\) generate:
where \(v \ge 1\).
The bit-sequence \(z_1, z_2, z_3,\dotsc\) is then the output sequence used.