Pseudo-random number generation based on digit isolation referenced to entropy buffers

Abstract

Unpredictable pseudo-random number generators (PRNGs) are presented based on dissociated components with only coincidental interaction. The first components involve pointers taken from series of floating point numbers (float streams) arising from arithmetic. The pointers are formed by isolating generalized digits sufficiently far from the most significant digits in the float streams and may be combined into multi-digit pointers. The pointers indicate draw locations from the second component which are entropy decks having one or more cards corresponding to the elements used to assemble random numbers. Like playing cards, decks are cut and riffle-shuffled based on rules using digits appearing in the simulations. The various ordering states of the cards provide entropy to the PRNGs. The dual nature of the PRNGs is novel since they can operate either entirely on pointer variability to fixed decks or on shuffling variability using fixed pointer locations. Each component, pointers and dynamic entropy, is dissociated from the other and independently shown to pass stringent statistical tests with the other held as fixed; a “gold standard” mode involves changing the coincidental interaction between these two strong emulators of randomness by either cutting or shuffling prior to each draw. Gold standard modes may be useful in cryptography and in assessing tests themselves. One PRNG contains $O (10^{629675})$ states in the entropy pool, another generates integers approximately 50% faster than the Advanced Encryption Standard (AES) PRNG with similar empirical performance, and a third generates full double-precision floats at speeds comparable to unsigned integer rates of the AES PRNG.

Keywords

Random number generation Monte Carlo simulations Dieharder cryptography

1. Introduction

The development of pseudo-random number generators (PRNGs) has advanced so that now several PRNGs generate integers on the interval [0,2³²–1] at rates exceeding 10⁸ s⁻¹ on common desktop computers through efficient programming and limited operation counts or bit manipulations, although often at the expense of experiencing predictability. Many modern and formerly popular PRNGs are included in the GNU Scientific Library (GSL).¹ Three such families which are fast and which perform well on tests for the appearance of randomness are the generalized phase shift register,² variants of the Mersenne Twister,³ and the Tausworthe PRNGs.⁴ Also within the GSL, the Randlux PRNGs⁵ perform well on empirical tests, although with slower generation. The Dieharder project software used in this effort⁶ includes the GSL PRNGs along with several others including the Advanced Encryption Standard (AES) PRNG.⁷ Marsaglia⁸ has given a review of PRNGs including his “multiply-with-carry” and KISS PRNGs, both of which perform well on empirical tests.

With hardware improvement, PRNGs are subjected to increased scrutiny for patterns observable at longer stream lengths. Evidence for this trend is apparent from empirical testing of the GSL PRNGs using Dieharder. Only the four aforementioned PRNGs out of sixty-two PRNGs included are not flagged by at least one of the well-functioning tests under default conditions. Presumably, PRNGs in the GSL once represented strong similarities to randomness under testing of streams considered to be long at the time of their development.

In comparison to the ability to emulate randomness, one might contend that generation rates are occasionally overemphasized, particularly since PRNG speeds rarely limit the overall speed of scientific computation as programming statements based on various physical laws are usually far more expensive. In addition to speed, PRNG selection may also be based on attributes such as unpredictability, period, equidistribution, and spectral characteristics.

The present effort presents a general class of PRNGs which should remain relevant through hardware advances by offering considerable levels of tunability. This tunability involves options including but not limited to choices in arithmetic and updates to constants, variations in mixing of pointer streams, and rates and types of transitions for the dissociated data. The use of dissociated data structures allows the performance of each component to be verified by testing under conditions holding the other as fixed. With each stream verified under empirical testing, the PRNGs described here present a coincidental interaction between two excellent sources of apparent randomness, introducing an element of “chance.”

Options for generation schemes exist which provide generation rates of the same order of magnitude as the fastest known predictable PRNGs and faster than the best cryptographic PRNG. A “gold standard” mode will also be described in which both dissociated data streams are updated on each call. With no correlation between the two streams other than through pure coincidence, the gold standard mode should be beneficial in testing the empirical tests which themselves may be suspect. The PRNGs presented here are unpredictable from observation of the output stream so that they might be useful in cryptography and games of chance. A basic overview of elements of these PRNGs will now be given.

2. Digit streams and entropy pool draws

The digits in a stream of pseudo-random numbers (PRNs) should be uniformly distributed and uncorrelated with all other digits. In support of this, the present PRNGs are assembled as digit combinations, each developed from an unbiased entropy source, meaning that the source holds an equal number of each of the digits and there is no preferred location for these digits within the source so that, over time, no location is any more or less likely to hold any given digit. Just as the outcomes of a roll of an unbiased die are equally probable, the entropy sources have an equal likelihood of being in any of their possible states.

The presentation here outlines a broad overview of similar PRNGs that can be developed with the common feature that they consist of two independent components brought together to output a random variable. Rather than presenting an outline of one specific algorithm, an overview of the steps which may be used to design any one of similar algorithms is given as follows:

Select a class of digits as a basis for the random variable, for example, octal, hexadecimal, or base-256.

Develop pointers to the digits:

Select a range for each pointer based on the size of its target of candidate digits.

Design a stream of computations to provide numbers as a source for the pointers.

Isolate certain digits from numbers in the stream suitable to form pointers of appropriate range.

Verify that these digits are uniformly distributed; modify computations or digit locations if not.

Form pointers from digits or their combinations.

Develop a dynamic entropy source:

Based on the number system to be used, assign a complete range of “place values” to multiple entropy vectors.

Similar to cutting or shuffling playing cards, set up a scheme to transition this entropy through its possible states.

Program the draw of contributions from each entropy deck using the pointers developed.

Assemble the random number from the components drawn.

Figure 1 illustrates this operation. For simplicity, the figure illustrates a PRNG developed using a decimal system, although faster approaches will utilize other systems with bases only containing prime factors of two. The top box in Figure 1 shows a series of floating point numbers which may be taken as arising from simple arithmetic. While this arithmetic will be discussed later for the specific examples, generally, many types of successive operations which include conditional statements to modify coefficients on occasion and possibly rescale terms in the stream as needed will suffice. While the distributions of digits in arithmetic streams modified by conditional transitions are generally unknown, the suitability of any particular digit should be verified with digit histograms. Consistent with Benford’s “law,” it might be expected that the distributions of individual digits approach a uniform distribution with increasing distance from the leading digit, particularly when the floating point numbers involved span several orders of magnitude. However, this should be confirmed through numerical experimentation.

Figure 1.

Illustration of process for assembling a random variable u from two streams of floating point numbers, showing determination of third significant figure using base-10 digits.

As indicated in Figure 1, any patterns which might appear in one of the streams may be mitigated by combination with a digit from another stream. For example, if the digit in the given upper stream position was slightly biased toward the current digit “6,” various combinations of this digit with others from the lower stream could largely mask this so that pointers on the interval [0,99] were nearly uniform. Figure 1 shows a pairing in one of many possible configurations, using the circled “8” in the second stream as the digit in the “ones” position and the digit “6” in the “tens” position. Other possibilities include reversal of the digits, different pairings, and so on, all of which can change on different calls.

The sets of pointers isolated from digits in this fashion can be used to point to a fixed source, meaning that the entropy vector to be discussed next is held fixed throughout all generation of PRNs. Under this operation, variability is only through the pointers themselves and testing will show that, taken by themselves, the isolated digits described above provide a very strong emulation of randomness.

The other component of the PRNGs shown in Figure 1 is one or more digit entropy pools containing the digits used to assemble either pseudo-random integers or floats. Similar to the definition of entropy S in statistical thermodynamics, $S = k \ln Ω$ , where k is the Boltzmann constant and Ω denotes the number of states, the entropy pools here offer a number of different states as the vectors of digits may assume different orderings through cutting and shuffling. The entropy pools serve three purposes. First, the entropy pools provide a means for the PRNGs to take on massive numbers of states, meaning that their periods are greatly extended by their use. Second, again similar to the physical case of a $pH$ buffer solution used in chemistry, the entropy pools can “buffer” small amounts of bias or patterns in the sets of digit pointers by transitioning to new states before any such patterns may be observed. Third, since the entropy pools are dissociated from the arithmetic streams, their interaction with the pointers from the arithmetic streams is purely coincidental, which is an attractive feature when attempting to emulate randomness.

As indicated in Figure 1, these pools may show a redundancy of digits under the obvious restriction that each digit has equal representation in each pool so that the pools are never biased toward more frequent drawing of any given digit. Also as indicated in the figure, pointers from the float streams are used to “draw cards” from the entropy pools which are then combined into random numbers. The entropy pools or “decks” are transitioned similar to the “cutting” and “riffle shuffling” of playing cards such that any card may be in any position, completely independent of its value. As discussed previously, the pointers to the decks are designed to appear to be uniformly random over the draw locations. It will be shown that excellent results are obtained with occasional cutting or shuffling, relying on variability in the pointer streams.

As previously discussed, while the pointers can be set to point to fixed entropy pools to test the strength of the pointer streams, the pointers may also be taken as fixed, drawing from the same positions each time. The notion of fixed pointers here is used to imply that the PRNGs are compiled with the pointers hard-coded to some fixed value location, typically one-quarter of the way through the entropy vectors, which never changes. By fixing draw locations and relying only on cutting or shuffling of the entropy pools on each draw, one may test the apparent randomness of the cutting and shuffling scheme, and this case will also be shown to perform as well as any known PRNG. With both pointer variability and continual entropy state transitions vetted as passing stringent tests to detect any discernible patterns, gold standard modes of generation exist where there is only purely coincidental interaction between these two sources, which might prompt one to ask the question of how any patterns could arise. An attractive feature of the PRNGs to be presented is that users can easily increase shuffling frequency, ranging from the expense of the gold standard mode to rather rare shuffles simply to extend the period of these generators based on one’s needs in any given simulation.

All PRNGs described here and all data to be shown are completely repeatable since all starting point data are taken from a single unsigned integer seed. The choice to use a single seed was made for compatibility with testing software since the vast majority of PRNGs in the literature seem to use a single seed. However, limiting the various deterministic PRNGs to a small number of patterns arising from a relatively small number of starting configurations seems rather restrictive and the present PRNGs could be easily modified to include much more data. These data, in the form of a seed vector, could include information on both arithmetic constants and information for the entropy pools such as shuffling frequency and cutting location.

It is also mentioned that, if desired, the present PRNGs implemented in C are well-suited to operate using true sources of randomness. As an example, entropy transitions could be reprogrammed to run entirely on data from the system clock and one or more thermal sensors available in most computers. The computer thermal data as a function of time are affected by the random nature of weather and its effects on room temperatures, ultimately affecting processor temperatures. Obviously, operation in fully nondeterministic modes would have some limitations regarding lack of repeatability, but could be useful, for example, in various games of chance and in some Monte Carlo applications where repeatability is not of specific interest. In this fashion, the present PRNGs could provide some of the advantages sought in the true randomness of hardware generators while being much faster and unencumbered with concerns over possibilities of non-uniform distributions. This inclusion is only mentioned for possible future use and is not considered further herein.

Regardless of operation, the PRNGs here are practically unpredictable from the output stream. Such knowledge would require the identification of dozens of floating point numbers, the correct identification of an extremely large number of possibilities for shuffling combinations, all in conjunction with entropy pool states which may be as high as $O (10^{629675})$ possibilities.

2.1. Single-source float base-256 integer PRNG (SS4x256)

The first PRNG described provides integers on (0,2³²–1) to facilitate comparisons with PRNGs producing large unsigned integers using the Dieharder test suite. A floating point number is used for the pointers in conjunction with four 256-digit entropy decks in this PRNG, termed as the SS4x256 PRNG. Since all the new PRNGs have common features, this PRNG is described in the most detail beginning with a discussion of the pointer data source.

2.1.1. Pointers isolated from floating point streams

The C programming language facilitates digit isolation using an array of char pointers. The following short program demonstrates an example of the isolation of certain base-256 digits of 31.4039061899269498.

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

int main()

{

static double V1;

unsigned char *id = (unsigned char *)&V1;

V1 = 31. + (103./256.) + (102./65536.)

+ (101./16777216.) + (100./4294967296.)

+ (99./1099511627776.)

+ (98./281474976710656.);

printf(“Chars isolated from \n”);

printf(“%.16f are:\n,”V1);

printf(“%u %u %u \n”,id[0],id[1],id[2]

printf(“%u %u %u \n”,id[3],id[4],id[5]

}

For machines with little-endian architecture, this simple program has the following output:

Chars isolated from

31.4039061899269498 are:

98 99 100

101 102 103

The PRNGs presented here will typically not use a full set of digits from any floating point number, so the preceding example is limited to only six base-256 digits. The constant 31 in the preceding program was chosen to demonstrate ordering of the remaining portion of the significand under the IEEE standard; the program output is unchanged when the constant is chosen as any whole number from 16 through 31. The present work was limited to little-endian architectures; a first call test for “endianness” could be added for portability. Alternatively, digits may be accessed through other means as described later in section 2.3.

The arithmetic in the SS4x256 PRNG involves seven additional floating numbers, $V_{2}$ through $V_{8}$ , and two unsigned integers, $K_{1}$ and $K_{2}$ , which are all static. The pointer source $V_{1}$ is initialized on the first call with an unsigned integer seed $(I_{seed})$ :

\begin{matrix} V_{1} = {I_{seed}} \times 1.8345322353 \times 10^{- 11} \\ + 0.45078321324899 \end{matrix}

(1)

where the general use of braces such as those around $I_{seed}$ will be used throughout to indicate casting of an integer to the type double. Again, the new PRNGs here could incorporate more external data than an unsigned integer introduced as a seed in Equation (1); this restriction in the present case is for historic compatibility with existing PRNGs used in the testing software.

Constants $V_{2}$ through $V_{6}$ are initialized between 0.1 and 1.0 on the first call, the specific choices of which are unremarkable since they change on each call. The two unsigned integers are arbitrarily initialized on the first call as $K_{1} = 1, 234, 567$ and $K_{2} = 8, 901, 234$ . General use of this PRNG could also allow these two integers to be initialized with seeding.

Constants $V_{7}$ and $V_{8}$ are used later to advance the arithmetic into the next call,

V_{7} = V_{4} + {K_{1}} \times 2.37459832134869329 \times 10^{- 9}

(2)

V_{8} = V_{3} + {K_{2}} \times 1.534225242358739 \times 10^{- 9}

(3)

In the previous expressions, digits other than the most significant were obtained through nearly simultaneous “keyboard mashes.” In other words, the most significant digit, which includes placement of the decimal point, scales the recursive arithmetic, but the digits used in the PRNGs which are far from the leading significant figures are acceptable as keyboard mashes; the method should work well with any combination of numbers.

The next assignments give the pointer source, $V_{1}$ ,

V_{2} = 0.4083419347851282 + V_{5} \times (V_{2} + V_{3})

(4)

V_{3} = 0.4005684737219317 + V_{6} \times (V_{3} + V_{4})

(5)

V_{4} = 0.4098342351328341 + V_{5} \times (V_{3} + V_{4})

(6)

\begin{matrix} V_{1} = V_{2} \times (V_{7} + V_{1}) \\ + 1.03238 \times 10^{- 8} \times (V_{3} + V_{4}) \end{matrix}

(7)

The small constant in Equation (7) introduces variety into the least significant digits of $V_{1}$ . Prior to the next call, $V_{5}$ and $V_{6}$ are updated through $V_{5} = V_{7} + 1.0$ and $V_{6} = V_{8} + 1.0$ and the unsigned integers $K_{1}$ and $K_{2}$ are updated from the char array isolated from $V_{1}$ according to,

\begin{matrix} K_{1} = (id [0]) << 24 + (id [2]) << 16 \\ + (id [3]) << 8 \end{matrix}

(8)

K_{2} = (id [1]) << 24 + (id [4]) << 8

(9)

where id denotes the array of base-256 digits taken from $V_{1}$ as illustrated in the previous example code and $<<$ denotes the bit shift operation. As indicated, the leading significant digits $K_{1}$ and $K_{2}$ are assembled from the trailing significant digits of $V_{1}$ .

Finally, the static doubles may be modified depending on an arbitrary range,

{\begin{matrix} V_{1 new} = 0.013203858620139 \times V_{1 old} \\ + 1.3453945798 \times 10^{- 3} \times V_{5} \\ (i f V_{1 old} > 380.0) \\ V_{1 new} = 0.25 + 1.07112238951 \times V_{1 old} \\ + 0.003 \times V_{6} \\ (i f V_{1 old} < 0.5) \\ V_{1 new} = V_{1 old}, (o therwise) \end{matrix}

(10)

{\begin{matrix} V_{2 new} = 0.35234356236 \\ + . 002492349783407 \times V_{7} \\ (i f V_{2 old} > 16.6) \\ V_{2 new} = V_{2 old}, (o therwise) \end{matrix}

(11)

{\begin{matrix} V_{3 new} = 0.3023458329429 \\ + . 00531234859223 \times V_{8} \\ (i f V_{3 old} > 16.6) \\ V_{3 new} = V_{3 old}, (o therwise) \end{matrix}

(12)

{\begin{matrix} V_{4 new} = 0.3883256924853947 \\ + 1.0988923 \times 10^{- 12} \times V_{4 old} \\ (i f V_{4 old} > 16.8) \\ V_{4 new} = V_{4 old}, (o therwise) \end{matrix}

(13)

As previously, many of the trailing digits in the preceding expressions were programmed by “keyboard mashes.” This scheme provides variety in the double $V_{1}$ as shown in Figure 2, giving 500 successive values of $V_{1}$ following a run-off of 9×10⁷ calls, by which it is meant that the data presented begins after 10⁷ calls to the PRNG were made and all data up to that point discarded. This should provide a measure of how this process continues on long runs of PRN generation. The figure shows that $V_{1}$ varies over several orders of magnitude with the trend that lower values are more common. It has generally been found to be favorable to have large variety in the magnitude of $V_{1}$ , although an example PRNG will draw from floats on the interval (0,1). The fact that $V_{1}$ spans a large range of scales may enhance the tendency of its digits to follow Benford’s law commonly observed for physical data spanning several orders. Regardless of whether $V_{1}$ exactly follows Benford’s law, it could be expected that the distribution of digits in $V_{1}$ would become increasingly uniform for digits increasingly removed from the most significant and, as previously mentioned, this is verified experimentally. The SS4x256 PRNG only uses data from the least significant part of $V_{1}$ , beginning with the base-256 digit in the $1 / (256)^{3}$ $(\approx 6 \times 10^{- 8})$ position for a float in the range (16,31) through to the smallest digit in the significand.

Figure 2.

Variation in $V_{1}$ for the next 500 calls after 9 × 10⁷ calls into the stream. (a) Plot showing all values of $V_{1}$ and (b) plot showing values of $V_{1}$ zoomed in below $V_{1} = 5000$ .

Figure 3 shows base-256 digit histograms for the least and most significant digits used over 10⁷ draws following a run-off of 9×10⁷ draws, indicating a reasonable approximation to uniform randomness. Table 1 presents the statistical data in the histograms computed using the xmgrace plotting software. The measured standard deviation for the bin frequency counts is consistent with the expected binomial standard deviation of bin frequency of approximately 197.3. While verification of PRNGs requires stringent testing, a check of bin variances may be used to determine whether any given digit is sufficiently far from the leading figure to be useful. The pointers described here will be independently verified in section 6 with entropy pools held as fixed. A discussion of these entropy pools now follows.

Table 1.

Histogram data for four sets of 10⁷ base-256 digits. Mean occurrences: $μ_{b in} = 39062.5$ ; standard deviation for target binomial distribution $B (10^{7}, 1 / 256) : σ_{b inomial} \approx 197.256$ .

Array position	Minimum occurrence (below mean)	Maximum occurrence (above mean)	Standard deviation
id[0]	38,484 (−578.5)	39,712 (+649.5)	214.053
id[1]	38,653 (−409.5)	39,610 (+547.5)	191.315
id[2]	38,436 (−626.5)	39,639 (+576.5)	201.816
id[3]	38,524 (−538.5)	39,693 (+630.5)	198.236

Figure 3.

Base-256 digit histograms of $V_{1}$ for 10⁷ numbers in the stream after initially drawing 9 × 10⁷ numbers in the sequence; horizontal line indicates the uniform bin size for the samples. (a) Least significant digit histogram. Base-256 digits are integers on the interval [0,255] and (b) most significant digit used histogram. Base-256 digits are integers on the interval [0,255].

2.1.2. Dynamic digit entropy pools

Entropy pools serve both to mitigate possible patterns in the pointers and to extend the period. One may consider the entropy pools as an ensemble of digit cards, possibly containing multiple copies of each digit card, which are shuffled and cut, in virtual fashion similar to the mixing of playing cards prior to various card games. Other than the fact that the SS4x256 PRNG decks lack digit redundancy, a detailed discussion of the entropy pools can take this particular PRNG as a representative example.

The SS4x256 PRNG produces large unsigned integers which are represented as four-digit base-256 numbers. Its entropy pools are four decks, each containing 256 digits. The first deck $I_{1}$ contains base-256 digits from 0 through 255. Decks used for other columns of the integer contain multiples of the “ones deck,” successively obtained by multiplication by 256. For example, the second deck $I_{2}$ includes the set of integers $[0, 256, 512, \dots]$ , the third deck $I_{3}$ includes the set of integers $[0, 65536, 131072, \dots]$ , and so on. The SS4x256 PRNG may operate by cutting or shuffling on each draw, cutting or shuffling on conditional triggers, as well as never cutting nor shuffling.

The entropy may be viewed as virtual decks of playing cards with face values and positions within each deck. As such, many elements of shuffling employed here likely have similarities to shuffling schemes used in video card games. Many options have been tested for transitioning, and they all seem to work equally well as long as they involve combinations of deck cuts at pseudo-random locations and riffle shuffles. Although results from an expensive verification mode will be presented in which cards are taken from fixed locations while continuously shuffling, the primary and faster mode of operation is to vary the selection locations while occasionally refreshing the decks. This section will give one specific example of an instruction set for shuffling used in the SS4x256, followed by some more general comments on shuffling.

The numerical results from testing for patterns to be presented later for the SS4x256 are based on the following strategy, designed to reorder the decks approximately once every sixteen draws. The configuration described here will only involve cutting of the decks. One integer, $J_{1}$ is produced by bit shifting the char pointer $id [4] \in [0, 255]$ according to,

J_{1} = (id [4]) >> 4

(14)

so that $J_{1} \in [0, 15]$ . A second integer $J_{2}$ is based on the integer deck $I_{1}$ , referencing the location 133 in that deck; the choice to use location 133 was entirely arbitrary. $J_{2}$ is also placed on the interval [0,15],

J_{2} = (I_{1} [133]) >> 4

(15)

The trigger to cut the decks is then based on a conditional statement testing for the equivalence of $J_{1}$ and $J_{2}$ which should occur approximately once every sixteen draws. The integer $J_{1}$ will likely change with each new value of $V_{1}$ and the value for $J_{2}$ will likely change each time the deck $I_{1}$ is cut. Here, it is noted that the random variable itself will contribute somewhat to the cutting strategy. One mode of operation will be described later where either cutting or shuffling occurs on every draw and is completely independent of the streaming arithmetic.

When cutting does occur, the locations for cuts are determined by the values of cards occupying a changing set of locations with bit shifting done where needed to place values in the range [0,255]. For the specific case of the SS4x256, the values of the deck cards themselves completely prescribe the cutting, once triggered. The cut locations, $L_{i}$ , for each of the four decks are computed through the following instruction set:

\begin{matrix} M_{1} = (I_{4} [77]) >> 24 \\ M_{2} = (I_{3} [120]) >> 16 \\ M_{3} = (I_{2} [135]) >> 8 \\ M_{4} = I_{1} [189] \\ N_{i} = (I_{2} [M_{i}]) >> 8, f or i = 1 \dots 4 \\ K_{i} = (I_{3} [N_{i}]) >> 16, f or i = 1 \dots 4 \\ L_{i} = I_{1} [K_{i}], f or i = 1 \dots 4 \end{matrix}

(16)

Obviously, the preceding represents one of many possibilities which should be fully expected to work well. The SS4x256 also uses some conditional statements which occasionally will alter the cut locations when they are true.

For each value of the integer $i \in [1 \dots 4]$ , the $L_{i}$ value is used to cut the $i t h$ deck which may be considered as having cards in positions 1 through 256. The cuts are programmed by relocation of the cards formerly occupying the positions $(L_{i} + 1)$ through 256 to the first $(256 - L_{i})$ deck positions in the same relative order, while moving the cards formerly in the first $L_{i}$ positions to the positions $(256 - L_{i} + 1)$ through 256, also in the same relative order. This process is computationally similar to the physical act of cutting a deck of playing cards.

While the particular mode of operation currently described bypasses riffle shuffles, shuffling is used in other modes and may be reinstated by changing a single line of code in the presently discussed PRNG. Since other modes, including a gold standard mode to be described later, will use shuffling, the snippet of C code used to shuffle four sets of entropy decks, Icards, each having 256 elements, is given as follows:

for(j = 0;j < 4;j++)

{for(n = 0;n < 255;n++)

{Jwork[n] = Icards[j][n];}

Jwork[255] = Icards[j][255];

for(m = 0;m < 128;m++)

{J = 2*m;K = J + 1;

Icards[j][J] = Jwork[m];

Icards[j][K] = Jwork[m + 128];

}

The cutting and shuffling parameters previously described are easily changed, typically with a line or two of code to increase or decrease frequency by either conditional placement of values within a larger range or by adding additional match conditions to reduce their frequency of occurrence. Numerical results will be presented later for three modes of operation: fixed or never shuffling, cutting the decks at pseudo-random locations as described above, and alternating pseudo-random cuts and riffle shuffles on each draw.

It is again noted that all of the cutting and shuffling schemes in conjunction with their triggers are completely repeatable here. However, if one requires an element of true randomness at the expense of repeatability, for example, as required in an online game of chance, the inputs for shuffling could easily be drawn from a small amount of sensor data, though this will be reserved for future effort.

As a final point, the entropy values and the assembly of their data to produce PRNs is now discussed. Since the Dieharder software operates on streams of unsigned integers from 0 through 2³²–1, it is noted that these integers are developed from values of the cards drawn from each of the four decks according to,

\begin{matrix} RAND = I_{1} (id [0]) + I_{2} (id [1]) + I_{3} (id [2]) \\ + I_{4} (id [3]) \end{matrix}

(17)

In the previous expression, $I_{n} (id [m])$ denotes the integer drawn from the $n th$ deck from the position indicated by the value of the “char” integer $id [m]$ accessed by pointers as one of the trailing digits of the floating point stream of $V_{1}$ values discussed in the previous section. Also as previously discussed, the face values of $I_{1}$ cards are the integers given by $I_{1} \in [0, 1, 2, \dots, 255]$ , the face values of $I_{2}$ cards are $I_{2} \in [0, 256, 512, 1024, \dots, 65280]$ , and so on, so that each card represents the contribution from each of the four “positions” in a four-digit base-256 integer.

The SS4x256 is unpredictable from observation of its output, and its period is also unknown. Each of the 256 card entropy pools has $256! \approx 8.578 \times 10^{506}$ states for a total of approximately 5.415 × 10²⁰²⁷ states for the four entropy pools alone for each configuration of the floating point stream variables.

This description of the SS4x256 PRNG has presented the main details regarding the design of a number of similar PRNGs. The following sections will briefly highlight the small modifications required to develop two similar PRNGs, each offering different qualities.

2.2. Twin-source base-256 integer PRNG (TS4x65,536)

The next PRNG differs from the SS4x256 PRNG in two ways. First, two-digit streams are taken from two floating point sources and combined to form sets of two-digit base-256 pointers $\in [0, \dots 65535]$ . The pairing of digits should reduce the likelihood for patterns which might appear in a single-digit pointer. Second, the four decks contain 256 copies of each digit in each deck, greatly increasing the number of states in the PRNG. Redundancy of digits in the pools should make prediction nearly impossible from observation of the output stream since, for each configuration of the entropy pools, there are a high number of pointer combinations producing identical integers. This PRNG uses twin floating point sources and four pools with 65,536 cards in each deck, and is therefore called the TS4x65,536 PRNG.

The pointers in the TS4x65,536 PRNG are isolated from the floating point numbers using two integer arrays, $i d_{1}$ and $i d_{2}$ , each in generally similar fashion as described for the SS4x256 PRNG. The arrays, whose elements have possible values 0 through 255, are combined into pointers $K$ , $L$ , $M$ and $N$ ranging from 0 to 65,535 used to build an integer according to,

K = i d_{1} [1] \times 256 + i d_{2} [3]

(18)

L = i d_{1} [4] \times 256 + i d_{2} [2]

(19)

M = i d_{2} [4] \times 256 + i d_{1} [3]

(20)

N = i d_{2} [1] \times 256 + i d_{1} [2]

(21)

RAND = I_{1} (K) + I_{2} (L) + I_{3} (M) + I_{4} (N)

(22)

where the array numbers begin at 0 in the C programming language and where the pools $I_{1}$ through $I_{4}$ are similarly defined as in the SS4x256 PRNG with redundancy as the only difference. The TS4x65,536 PRNG uses the fifth least significant digit and discards the least significant. One can easily shuffle the array elements used in the formation of pointers in Equations (18)–(21) although the presentation here is for the fixed case shown. The standard mode for the TS4x65,536 PRNG is to shuffle the entropy with a trigger which occurs approximately once every 65,536 draws. This low shuffling rate indicates the strength of the pointers given in Equations (18)–(21) since they are the primary source of apparent randomness. The cards of the entropy pools alternate between inversion on each side of a cut and riffle shuffles on successive triggers.

Each pool with a redundancy of 256 has $n$ states given by

n = \frac{65, 536!}{{(256!)}^{256}} \approx 5.805 \times 10^{157418}

(23)

The four pools have $n^{4} \approx 1.135 \times 10^{629675}$ states. The number of states in the pools alone is approximately one-thousand orders of magnitude larger than the period of the Mersenne Twister. The total number of states in the TS4x65,536 is at least one-hundred orders of magnitude more than the pool states alone due to a number of floating point numbers.

2.3. Twin-source base-256 float PRNG (TS7x256)

Inasmuch as Fortran remains in wide use for computations in physics and engineering due to its speed and simplicity, a final PRNG is presented here programmed in Fortran, set up to directly produce double-precision floating point numbers. Since pointers are not used in Fortran as commonly as they are in C, a different strategy is presented to isolate digits, which will be one of the main differences from the PRNGs previously presented. This PRNG draws base-256 numbers from two floating point sources, X1 and X2. The arithmetic is generally similar to that used for other PRNGs described previously. A difference is that the two floating point numbers are maintained on the interval [0,1] by taking their reciprocal if they exceed unity. In order to extract specific digits at a high level of speed, the two floating point numbers are assigned to four integers in order to use Fortran’s bit manipulation intrinsics. The following section of Fortran assigns the real number X1 $\in [0, 1]$ to two integers, I1 and I2:

Y1 = 2.68435456D8*X1

I1 = INT(Y1)

Y1 = Y1-DFLOAT(I1)

I2 = INT(2.68435456D8*Y1)

Similar statements assign the second variable X2 to two other integers, I3 and I4. The choice to use $2.68435456 \times 10^{8} = 2^{28}$ is made on the basis of isolation into base-256 digit data segments with values which range from 0 to 255 = 2⁸–1. The specific value of 28 positions in binary form allows isolation into three eight-digit binary numbers, each ranging from 0 to 255, plus one four-digit binary number ranging from 0 to 15. Two four-digit binaries are combined with bit shifting to produce a two-digit hexadecimal number also ranging from 0 to 255.

This process is described as follows. The leading parts of significands of X1 and X2 are mapped to the integers I1 and I3, respectively, while the least significant parts are mapped to the I2 and I4. Only the last eight bits of I1 and I3 are used; the leading significant figures of X1 and X2 are discarded, consistent with the expectation that digits become more nearly uniformly distributed with increasing distance from the most significant digit. The trailing bits in I2 and I4 are discarded so rounding concerns are eliminated. The next two data segments in I2 and I4 are retained. Finally, the first four bits in I2 and I4 are combined as previously discussed. Digit isolation of the previous expressions is through bit manipulation to create a seven-element pointer array I. The following Fortran statements provide the isolations and assignments,

I(LCOL(1)) = IBITS(I1,0,8)+1

I(LCOL(2)) = IBITS(I2,8,8)+1

I(LCOL(3)) = IBITS(I2,16,8)+1

I(LCOL(4)) = IBITS(I3,0,8)+1

I(LCOL(5)) = IBITS(I4,8,8)+1

I(LCOL(6)) = IBITS(I4,16,8)+1

I(LCOL(7)) = IBITS(I2,24,4) +

A ISHFT(IBITS(I4,24,4),4)+1

where one is added in accordance with the Fortran array convention. The integer vector LCOL contains the elements 1 through 7 and is often shuffled so that the pointer values for each deck are not limited to a fixed position within the two floating point numbers.

The TS7x256 PRNG produces double-precision floating point numbers using seven entropy pools of floating point numbers. The pools have a dual array of integers from 1 through 256 which are involved in shuffling rather than the floating point numbers themselves. The seven entropy pools Q_i contain elements formed from dividing each of the integers 0 through 255 by the following denominators on the first call to the PRNG as shown as follows:

DENOM(1) = 256.D0

DENOM(2) = 65536.D0

DENOM(3) = 16777216.D0

DENOM(4) = 4294967296.D0

DENOM(5) = 1099511627776.D0

DENOM(6) = 281474976710656.D0

DENOM(7) = 72057594037927936.D0

The Q_i are directly ready to be added since the division just described scales the given card to its appropriate “positions value” in the floating point number. In terms of the Q_i, the PRN is determined through,

HEX256F = Q1(J1(I(1))) + Q2(J2(I(2)))

A + Q3(J3(I(3))) + Q4(J4(I(4)))

B + Q5(J5(I(5))) + Q6(J6(I(6)))

C + Q7(J7(I(7)))

where HEX256F is the pseudo-random variable on [0,1) and the J arrays are the integer dual array used for shuffling the values of the floating point parts Q_i since the shuffling of integers is notably faster than the shuffling of double-precision floating point numbers.

3. Generation rates

This section provides speed comparisons with other PRNGs. Two issues are considered in the comparisons. First, the present PRNGs offer various shuffling frequencies so that several rates are given. Second, the TS7x256 Fortran PRNG generates float streams in which the smallest non-zero float is $1 / (256^{7}) \approx 1.4 \times 10^{- 17}$ . Integer PRNGs cannot generate floats smaller than $1 / (2^{32} - 1) \approx 2.3 \times 10^{- 10}$ using a single integer, which means that more data are required.

For speed benchmarks, testing was performed on a machine with Intel^® Xeon^® CPU E3-1230 3.30 GHz processors running Debian Linux 7. The compilers used were gcc and gfortran bundled for Debian. Table 2 gives rates of generation for several of the “good” PRNGs included in Dieharder. For this architecture, the table shows that strong, but predictable PRNGs generate at approximately 2 × 10⁸ to 3 × 10⁸ random numbers per second (rnps), that the leading encryption PRNG generates at approximately 5 × 10⁷ rnps, and that efforts to produce high-quality random streams have produced PRNGs which produce slightly less than 10⁷ rnps. The slower Randlux rates are an indication of the extent to which expert users may be willing to sacrifice speed for quality.

Table 2.

Rates of generation for PRNGs in Dieharder and GSL.

PRNG	Generation rate (×10⁶ s⁻¹)
gfsr4	304
mt19937	211
AES	53.6
randlux389	24.7
ranlxd2	8.86

PRNG: pseudo-random number generator; GSL: GNU Scientific Library; AES: advanced encryption standard.

The rates of generation for the new PRNGs described here are shown in Table 3 including entries for different rates of entropy mixing. All of the PRNGs reported in Table 3 will be shown to perform as well as the best PRNG included in Dieharder, the AES PRNG. A comparison of the rates between Tables 2 and 3 shows that a number of the implementations compare well. The fastest mode for a PRNG generating long unsigned integers is the TS4x65,536 when it is triggered to shuffle on one of the 65,536 pointer possibilities, which is approximately 38% of the rate of the widely used and predictable Mersenne Twister.

Table 3.

Generation rates for new PRNGs based on unpredictable entropy transitions observed in 10⁸ calls.

PRNG name	Observed transitions: draws ratio	Generation rate (×10⁶ s⁻¹)	Type of random number
SS4x256	0	78.9	Integer
SS4x256	1:15.996^a	23.9	Integer
SS4x256	1:1^b	1.085	Integer
TS4x65,536	1:63,694.3^b	79.9	Integer
TS7x256	0	50.9	Double
TS7x256	1:257.7^c	41.4	Double

PRNG: pseudo-random number generator.

Cuts at random locations.

Alternating cuts and riffle shuffles on successive triggers.

Both a cut and riffle shuffle on each trigger.

At approximately 25% of the speed of the Mersenne Twister, the AES cryptographic PRNG gives indication of the sacrifice in generation rates which have been accepted as a compromise in return for an unpredictable stream suitable for encryption. Table 3 shows that the only PRNGs presented here which are not as fast as the AES PRNG are the two SS4x256 implementations in which the entropy decks change at a rate greater than or equal to approximately every sixteenth draw. As previously discussed, the two Fortran implementations of the TS7x256 effectively have a higher rate of data generation than the AES PRNG since they are generating a full “double” float as opposed to an unsigned integer.

The tables show that the two high shuffling variations of the SS4x256 are comparable with the Randlux family. The implementation which cuts the entropy pools approximately every sixteenth draw is nearly identical in speed to the Randlux389. The implementation of the SS4x256 applying either a cut or a riffle shuffle on every draw is approximately one-eighth of the speed of the ranlxd2 PRNG and should offer a purely coincidental stream which will be shown as a possible outlier in performance among all PRNGs on at least one test in section 6.

The present class of PRNGs was designed to be free of patterns as the primary objective and then revised to enhance speed. Their rates of generation are fast enough that they are competitive options since bottlenecks in computer simulation are rarely associated with sources of random numbers. In applications in which there is a need for an unpredictable source for any reason such as is necessary in games of chance or for encryption purposes, the present PRNGs are shown to offer a speed advantage over the AES PRNG.

4. Background on Dieharder

This section provides an overview of Dieharder (v. 3.31.1-4) used in testing along with empirical benchmarks from some well-known PRNGs. For reference, it is noted that Dieharder is also offered for use with the R package⁹ although the implementation used here was to pipe random numbers directly into Dieharder using the standard output from C or a C wrapper around the Fortran generators. Dieharder offers more than a straightforward re-programming of Marsaglia’s¹⁰ original Diehard suite. One of its key features is the ability to remove ambiguity over a single test result which may have a high or low p-value by allowing the user to repeat the tests and assess the distribution of p-values using the Kolmogorov–Smirnov (K–S) test on the resulting data. The default specification in Dieharder on many of the tests is 100 replications, which fails the vast majority of the PRNGs in the GSL. In addition, the software may be run using the “ $- m 100$ ” option which multiplies the default value of replications of each test by 100 to give 10,000 samples in many of the K–S tests, which provides an extremely stringent threshold.

In addition to these and other improvements to the original Diehard suite, Dieharder includes tests from the Statistical Test Suite (STS)¹¹ developed at the National Institute of Standards and Technology which were primarily developed to be sufficiently stringent to investigate the suitability of a given PRNG for cryptographic purposes. Finally, Dieharder also includes several tests developed and implemented by the Dieharder team which are discussed in the manual released with Dieharder Brown.⁶ The option “ $- a$ ” to run a PRNG through all of the tests in Dieharder produces ASCII files which are 125 lines long including a small header. For compact representation, the STS Serial tests, the RGB Bit Distribution tests, and the RGB Lagged Sum tests will be summarized in tabular form.

4.1. Performance of control PRNGs

Since only four PRNGs from the GSL pass the well-functioning tests along with variants of the KISS PRNG and the AES cryptographic PRNG, which the Dieharder manual describes as having “the strongest proof of randomness” the discussion of control PRNGs is limited. An investigation of their performance through Dieharder will lend appreciation to the stringent nature of the tests and to identify tests which seem to be flawed. In section 6, the gold standard mode of the SS4x256 PRNG will be used to assess the tests themselves.

Dieharder assigns a “WEAK” assessment when the p-value from the K–S tests is either less than 0.005 or greater than 0.995. Testing may flag stretches in very good PRNGs with low values as shown in Figure 4, representing an excerpt from the full test list at default values for the Mersenne Twister. The low p-values likely reflect a portion of the sequence where the Mersenne Twister may contain some apparent serial correlation.

Figure 4.

Excerpt of Dieharder report ( $- a$ option) for the Mersenne Twister with seed of 479,582,749 showing a stretch of questionable performance in several of the STS Serial tests.

For the $- m 100$ option, the increased sensitivity causes several trends to emerge which may reflect shortcomings in either the PRNGs or in the tests. In section 6, evidence will be presented that the latter must hold in certain instances. The Dieharder software description lists the Diehard Overlapping Pairs Sparse Occupancy (OPSO) test, the Diehard Overlapping Quadruples Sparse Occupancy test, and the Diehard DNA test each as suspect. The software also instructs users not to use the Diehard Sums Test. As will be shown in section 6, the gold standard form of the SS4x256 PRNG passes both the Overlapping Pairs Sparse Occupancy (OPSO) and OQSO tests, but confirms that the DNA test and the Sums test are flawed. In addition, extensive testing with a variety of PRNGs including the AES PRNG suggests that several other tests are either biased or impossible to pass. This will be confirmed with the gold standard PRNG. For reference, test results from reports generated using the “ $- m 100$ ” option are shown in Table 4 for the cryptographic AES PRNG as well as for the widely used Mersenne Twister. Consistent with considerable experimentation, Table 4 indicates low p-values for the following Diehard tests: Parking Lot, Runs, the second Marsaglia and Tsang Greatest Common Denominator test and the RGB Minimum Distance with four n-tuples. The RGB Minimum Distance test using five n-tuples and the RGB K–S Test fail all good PRNGs with the $- m 100$ option. There are other tests which may be biased low for the good PRNGs, but not so low that they often are assessed as “WEAK.” The performance of the AES and Mersenne Twister PRNGs provides the background to interpret the results from the new PRNGs described here. It is noted that the results shown in Table 4 for the AES PRNG generally represent the highest performance by any previously described PRNG through the test suite and that, with the exception of a few other good PRNGs, most previously described PRNGs fail numerous tests with the $- m 100$ option. For reference, the results for 75 serial tests of the two control PRNGs not shown in Table 4 are summarized in Table 5. These tests include a number of implementations of the sts_serial, rgb_bitdist, and rgb_lagged_sum tests.

Table 4.

Portion of results for Dieharder reports on two control PRNGs using the $- m 100$ option.

				AES_OFB (AES cryptographic) (seed = 1,113,335,640)		mt19937 (Mersenne Twister) (seed = 140,801,672)
Dieharder test	n-tup	t-samples	p-samples	p-value	Assessment	p-value	Assessment
diehard_birthdays	0	100	10,000	0.41427053	PASSED	0.00322514	WEAK
diehard_operm5	0	1,000,000	10,000	0.62580208	PASSED	0.14294130	PASSED
diehard_rank_32 × 32	0	40,000	10,000	0.17590803	PASSED	0.16212206	PASSED
diehard_rank_6 × 8	0	100,000	10,000	0.18513622	PASSED	0.91737713	PASSED
diehard_bitstream	0	2,097,152	10,000	0.59432462	PASSED	0.57851707	PASSED
diehard_opso	0	2,097,152	10,000	0.09298510	PASSED	0.58361641	PASSED
diehard_oqso	0	2,097,152	10,000	0.02495767	PASSED	0.06694080	PASSED
diehard_dna^a	0	2,097,152	10,000	0.00000000	FAILED	0.00000000	FAILED
diehard_count_1s_str	0	256,000	10,000	0.00856493	PASSED	0.61093582	PASSED
diehard_count_1s_byt	0	256,000	10,000	0.15919625	PASSED	0.04360375	PASSED
diehard_parking_lot^b	0	12,000	10,000	0.00000314	WEAK	0.00003159	WEAK
diehard_2dsphere	2	8000	10,000	0.95507037	PASSED	0.15828017	PASSED
diehard_3dsphere	3	4000	10,000	0.56452394	PASSED	0.10665728	PASSED
diehard_squeeze	0	100,000	10,000	0.75744546	PASSED	0.68306810	PASSED
diehard_sums^a	0	100	10,000	0.00000000	FAILED	0.00000000	FAILED
diehard_runs^b	0	100,000	10,000	0.22168658	PASSED	0.00111806	WEAK
diehard_runs^b	0	100,000	10,000	0.03530241	PASSED	0.01545259	PASSED
diehard_craps	0	200,000	10,000	0.00086003	WEAK	0.05606678	PASSED
diehard_craps	0	200,000	10,000	0.97651162	PASSED	0.05627737	PASSED
marsaglia_tsang_gcd	0	10,000,000	10,000	0.15522965	PASSED	0.74900325	PASSED
marsaglia_tsang_gcd^b	0	10,000,000	10,000	0.00012418	WEAK	0.00084663	WEAK
sts_monobit	1	100,000	10,000	0.54819042	PASSED	0.53906961	PASSED
sts_runs	2	100,000	10,000	0.40981248	PASSED	0.14016670	PASSED
rgb_minimum_distance	2	10,000	100,000	0.27259701	PASSED	0.46652678	PASSED
rgb_minimum_distance	3	10,000	100,000	0.07747515	PASSED	0.20249782	PASSED
rgb_minimum_distance	4	10,000	100,000	0.00312124	WEAK	0.00161349	WEAK
rgb_minimum_distance^a	5	10,000	100,000	0.00000000	FAILED	0.00000000	FAILED
rgb_permutations	2	100,000	10,000	0.19338533	PASSED	0.26920572	PASSED
rgb_permutations	3	100,000	10,000	0.07180373	PASSED	0.25969608	PASSED
rgb_permutations	4	100,000	10,000	0.62421087	PASSED	0.56025408	PASSED
rgb_permutations	5	100,000	10,000	0.45492578	PASSED	0.31520599	PASSED
rgb_kstest_test^a	0	10,000	100,000	0.00000000	FAILED	0.00000000	FAILED
dab_bytedistrib	0	51,200,000	100	0.10308341	PASSED	0.67945179	PASSED
dab_dct	256	50,000	100	0.35999500	PASSED	0.75738057	PASSED
dab_filltree	32	15,000,000	100	0.91872173	PASSED	0.26025865	PASSED
dab_filltree	32	15,000,000	100	0.96853469	PASSED	0.75262115	PASSED
dab_filltree2	0	5,000,000	100	0.93489658	PASSED	0.56946308	PASSED
dab_filltree2	1	5,000,000	100	0.85704208	PASSED	0.73317895	PASSED
dab_monobit2	12	65,000,000	100	0.48822226	PASSED	0.00176648	WEAK

AES: advanced encryption standard.

Test fails other control PRNGs.

Test is biased low for other control PRNGs.

Table 5.

Summary of 75 tests excluded from Table 4 for control PRNGs: sts_serial (n-tup = 1, 2 and two runs each at 3 through 16), rgb_bitdist (n-tup = 1 through 12), and rgb_lagged_sum (n-tup = 0 through 32).

PRNG	Minimum p-value	Maximum p-value	Mean	Standard deviation
AES_OFB	0.00919752	0.991389	0.457959	0.305433
mt19937	0.0207138	0.960034	0.520886	0.276917

PRNG: pseudo-random number generator.

Arguably, the most attractive feature of Dieharder lies in its capability to run a large number of repetitions of the same test followed by a K–S test on the resulting data sets in order to unambiguously resolve an isolated low or high p-value. While this K–S test is an excellent summary by itself, it may also be attractive to examine histograms of the individual test results, either to elucidate the mode of failure or to gage the general level of uniformity in histograms which would be consistent with “passing.” Dieharder includes an option to generate histograms in text format.

Some of the original tests from Diehard used empirical results from sources thought to be random. While these tests worked well at the time of their development, the improvements in both hardware and software now show shortcomings in the original empirical distributions of test results. As an example, the Parking Lot Test shows a non-uniform distribution of p-values when tested by strong PRNGs such as the AES encryption PRNG. A histogram from conducting the Parking Lot Test with the $- m 100$ is shown in Figure 5.

Figure 5.

Text histogram from AES PRNG subjected to Parking Lot Test with $- m 100$ option.

The histogram shows some indication of non-uniformity in the p-values and the K–S test returns a p-value of 0.00754409; this particular seed for testing was selected as being very near the 0.005 threshold to be considered to have “passed” by Dieharder. The same test was repeated with the $- m 1000$ flag which represents a 10-fold increase in the number of p-samples. A histogram of the results is shown in Figure 6.

Figure 6.

Text histogram from AES PRNG subjected to Parking Lot Test with $- m 1000$ option.

As shown, the bins are clearly non-uniform and the Dieharder assessment is “FAILED” with a p-value of 0.0. The unusual nature of the distribution, such as the low number of p-values falling between 0.4 and 0.5, is a likely indication that the empirical data used in assessing the test need to be improved. For reference, the original Diehard test would have only conducted the Parking Lot Test once and this non-uniformity would not have been noticeable.

While the level of acceptable bin variance in a uniform distribution may be directly assessed analytically, a visual depiction of the lower threshold is provided for reference. As an example, a histogram for the RGB Generalized Minimum Distance Test with n-tuple set to four and with the $- m 100$ option is shown in Figure 7. The histogram shown is consistent with a p-value of 0.00299093 in the K–S test, resulting in a Dieharder assessment of “WEAK.”

Figure 7.

Text histogram from AES PRNG subjected to the RGB Generalized Minimum Distance Test with n-tuple set to four and with the $- m 100$ option.

As seen in the histogram, only one bin is slightly lower than the others, although only by the minimum resolution which could be shown in the text plot. For histograms with an expected number of 10⁴ samples per bin, the example shows that no visible variation in bin height would be seen at the levels of resolution provided in the text plot for PRNGs considered to have “PASSED” a given test. While more variation in bin height would be considered acceptable on a limited number of tests, any test passed with the $- m$ flag set sufficiently high has to show very strong similarities to a uniform distribution in order to pass the K–S test.

5. Empirical tests for non-linear PRNGs

The performance of the new PRNGs will be assessed using the $- m 100$ option, taking 100 times the default number of tests in the K–S assessment. Unless otherwise noted, a moderate entropy transition rate will be specified. In cases where a particular test result may be suspect, the same PRNG may be re-tested using either higher or lower shuffling rates.

Test results for the new PRNGs are either listed in Table 6 or summarized in Table 7. The entropy triggers used to produce the results in Tables 6 and 7 were a pseudo-random cut of all four decks on approximately every sixteenth draw for the SS4x256 PRNG, alternating pseudo-random cuts or riffle shuffles for each of the four decks approximately once every 65,536 draws for the TS4x65,536 PRNG, and both a pseudo-random cut and riffle shuffle approximately once every 256 draws for each of the seven decks in the TS7x256 PRNG. In addition, the TS7x256 PRNG shuffles a dual-integer vector for the floating point data, and this dual association was shuffled approximately six out of every 256 draws.

Table 6.

Portion of results for Dieharder reports the three new PRNGs presented using the $- m 100$ option.

Test	t-samples	p-samples	SS4x256	SS4x256	TS4x65,536	TS4x65,536	TS7x256	TS7x256
Test	t-samples	p-samples	p-value	Assessment	p-value	Assessment	p-value	Assessment
DH_birthdays	100	10,000	0.03058032	PASSED	0.37837322	PASSED	0.22121615	PASSED
DH_operm5	1,000,000	10,000	0.66997849	PASSED	0.88022808	PASSED	0.61822295	PASSED
DH_rank_32×32	40,000	10,000	0.61723075	PASSED	0.76049194	PASSED	0.17115487	PASSED
DH_rank_6×8	100,000	10,000	0.0624513	PASSED	0.4347788	PASSED	0.45914406	PASSED
DH_bitstream	2,097,152	10,000	0.07621794	PASSED	0.87260319	PASSED	0.4992824	PASSED
DH_opso	2,097,152	10,000	0.05924627	PASSED	0.3736167	PASSED	0.40372974	PASSED
DH_oqso	2,097,152	10,000	0.79145424	PASSED	0.58035566	PASSED	0.58932615	PASSED
DH_dna^a	2,097,152	10,000	0.00000000	FAILED	0.00000000	FAILED	0.00000000	FAILED
DH_count_1s_str	256,000	10,000	0.75490046	PASSED	0.85580132	PASSED	0.24411523	PASSED
DH_count_1s_byt	256,000	10,000	0.0457136	PASSED	0.84898287	PASSED	0.72020514	PASSED
DH_parking_lotc^b	12,000	10,000	0.00937682	PASSED	0.01671387	PASSED	0.00293782	WEAK
DH_2dsphere	8000	10,000	0.62417626	PASSED	0.18359302	PASSED	0.86768533	PASSED
DH_3dsphere	4000	10,000	0.97181107	PASSED	0.87912271	PASSED	0.00268696	WEAK
DH_squeeze	100,000	10,000	0.04719762	PASSED	0.19972725	PASSED	0.06230689	PASSED
DH_sums^a	100	10,000	0.00000000	FAILED	0.00000000	FAILED	0.00000000	FAILED
DH_runs^b	100,000	10,000	0.02128071	PASSED	0.12461674	PASSED	0.2845878	PASSED
DH_runs^b	100,000	10,000	0.04913783	PASSED	0.04606102	PASSED	0.00518617	PASSED
DH_craps	200,000	10,000	0.54177455	PASSED	0.27817763	PASSED	0.67996237	PASSED
DH_craps	200,000	10,000	0.97182617	PASSED	0.414805	PASSED	0.62495629	PASSED
M_T_gcd	10,000,000	10,000	0.80764205	PASSED	0.51104249	PASSED	0.80084528	PASSED
M_T_gcd^b	10,000,000	10,000	0.03443375	PASSED	0.00190914	WEAK	0.00666731	PASSED
sts_monobit	100,000	10,000	0.54053452	PASSED	0.49972432	PASSED	0.36543866	PASSED
sts_runs	100,000	10,000	0.03951243	PASSED	0.32874282	PASSED	0.06924944	PASSED
rgb_min_dist(2)	10,000	100,000	0.02330312	PASSED	0.08361269	PASSED	0.03014255	PASSED
rgb_min_dist(3)	10,000	100,000	0.45199216	PASSED	0.89602617	PASSED	0.38080931	PASSED
rgb_min_dist(4)	10,000	100,000	0.02306176	PASSED	0.00605503	PASSED	0.00016839	WEAK
rgb_min_dist(5)^a	10,000	100,000	0.00000000	FAILED	0.00000000	FAILED	0.00000000	FAILED
rgb_permut(2)	100,000	10,000	0.41072173	PASSED	0.00049069	WEAK	0.41364923	PASSED
rgb_permut(3)	100,000	10,000	0.16564243	PASSED	0.1669055	PASSED	0.19348018	PASSED
rgb_permut(4)	100,000	10,000	0.98309075	PASSED	0.45854063	PASSED	0.26037907	PASSED
rgb_permut(5)	100,000	10,000	0.06951748	PASSED	0.87154296	PASSED	0.84053281	PASSED
rgb_kstest_test^a	10,000	100,000	0.00000022	FAILED	0.00000048	FAILED	0.00000000	FAILED
dab_bytedistrib	51,200,000	100	0.68220793	PASSED	0.27821562	PASSED	0.23666233	PASSED
dab_dct(256)	50,000	100	0.45144398	PASSED	0.25894981	PASSED	0.81578428	PASSED
dab_filltree(32)	15,000,000	100	0.94166785	PASSED	0.78501426	PASSED	0.05896983	PASSED
dab_filltree(32)	15,000,000	100	0.94253846	PASSED	0.16757061	PASSED	0.39664631	PASSED
dab_filltree2(0)	5,000,000	100	0.66355925	PASSED	0.14429106	PASSED	0.37077254	PASSED
dab_filltree2(1)	5,000,000	100	0.59259346	PASSED	0.19060094	PASSED	0.47273977	PASSED
dab_monobit2(12)	65,000,000	100	0.00037297	WEAK	0.00553826	PASSED	0.04611525	PASSED

Test fails all control PRNGs.

Test is biased low for all control PRNGs.

Table 7.

Summary of tests with $- m 100$ option: sts_serial (n-tup = 1, 2 and two runs each at 3 through 16), rgb_bitdist (n-tup = 1 through 12), and rgb_lagged_sum (n-tup = 0 through 32).

PRNG	Test name	Number of tests	Minimum p-value	Maximum p-value	Mean	Standard deviation
SS4x256	STS Serial	30	0.00076407	0.998555	0.540535	0.320426
	RGB Bit Distribution	12	0.0411885	0.893357	0.430098	0.327439
	RGB Lagged Sum	33	0.0021083	0.998726	0.473693	0.282742
TS4x65,536	STS Serial	30	0.104474	0.998496	0.586418	0.308782
	RGB Bit Distribution	12	0.0344366	0.802618	0.404199	0.191101
	RGB Lagged Sum	33	0.0784664	0.936467	0.500505	0.272344
TS7x256	STS Serial	30	0.0575054	0.999575	0.500997	0.314038
	RGB Bit Distribution	12	0.0403411	0.970640	0.439420	0.292537
	RGB Lagged Sum	33	0.0366322	0.978498	0.531887	0.281410

PRNG: pseudo-random number generator; STS: statistical test suite; RGB: Robert G. Brown.

As seen in columns four and five of Table 6, the performance of the SS4x256 is strong on the well-functioning tests, even using 100 times the default level of p-samples. Only one test, the “dab_monobit2,” was assessed as “WEAK,” although this seems to be an acceptable, but low p-value. Rationale for the interpretation that the result happens to be an acceptable low p-value will be presented in more detail in section 6, where a modified form of the SS4x256 PRNG is used which never cuts or shuffles the entropy decks, giving a p-value of 0.61054454. Since the entropy cuts are decoupled from the pointer streams and the PRNG performs well in testing when only using shuffling with fixed pointers as will be shown in section 6, the low p-value in Table 6 is considered likely to be acceptable. Three of the serial correlation tests were removed from Table 6 for brevity and summarized in Table 7, showing that the p-values from testing at this high level are consistent with a uniform variable on (0,1) which would have an expected mean of 0.5 and an expected standard deviation of $1 / \sqrt{12} \approx 0.2887$ .

For the TS4x65,536 PRNG, the sixth and seventh columns of Table 6 show an assessment of “PASS” assigned on the well-functioning tests with one exception. This PRNG can also be run in different modes and, in this case, when the entropy is held as fixed, the test shows,

rgb_permutations| 2| 100000| 10000 ....

...| 0.70711757| PASSED.

This suggests that the low p-value is likely an acceptable outcome for the reason previously discussed. The results summarized in Table 7 are consistent with a uniform random variable.

Finally, the eighth and ninth columns of in Table 6 show that the TS7x256 PRNG also performed well on the well-functioning tests, with the exception of two “WEAK” assessments for the diehard_3dsphere and the rgb_minimum_distance, n-tup = 4 tests. An altered shuffling scheme was again used to check whether these low p-values are cause for concern. When the TS7x256 PRNG was run with entropy shuffling completely removed and the tests repeated with the same seed, the two tests in question return p-values as shown as follows:

diehard_3dsphere| 3| 4000| 10000 ....

...| 0.98822137| PASSED.

rgb_permutations| 4| 100000| 10000 ....

...| 0.16072568| PASSED.

Again, the resulting p-values are much higher without shuffling and the low p-value is likely to be an acceptable outcome. The results in Table 7 are consistent with uniform p-values.

6. Gold standard for PRNGs

The SS4x256 PRNG may be set to either cut or shuffle the entropy on every draw so that the pointers never point to entropy in the same state on successive draws. The SS4x256 PRNG may be tested in three modes: running only on the random pointers with the entropy held constant, running only on the shuffling scheme ignoring the pointers and drawing from fixed locations, and in a gold standard mode where the entropy is either cut or shuffled on every draw in conjunction with full use of the random pointers to the entropy. The latter case is termed as a gold standard. It will be shown that the two partially functioning modes show excellent results under empirical testing. Since there is no correlation whatsoever between the pointer values and the entropy states, the gold standard mode represents purely coincidental interaction between two excellent sources of apparent randomness.

Reports from each mode are combined in Table 8. The second and third columns in Table 8 correspond to drawing the cards from a fixed position, arbitrarily chosen as element 63 in the entropy decks. The strong results shown in the first two columns are only due to shuffling of the entropy. With a single low p-value, the SS4x256 PRNG operating only on the shuffling scores as well as the best PRNGs included in Dieharder and the GSL.

Table 8.

Test data on various modes of operation for the SS4x256 PRNG using $- m 100$ option.

Test_name	Static pointers		Static entropy		Gold standard
Test_name	p-value	Assessment	p-value	Assessment	p-value	Assessment
diehard_birthdays	0.10471915	PASSED	0.08311901	PASSED	0.10980129	PASSED
diehard_operm5	0.86063069	PASSED	0.11927565	PASSED	0.00738445	PASSED
diehard_rank_32 × 32	0.52529972	PASSED	0.61229565	PASSED	0.72037757	PASSED
diehard_rank_6 × 8	0.02941813	PASSED	0.59499705	PASSED	0.17443768	PASSED
diehard_bitstream	0.65720425	PASSED	0.21065617	PASSED	0.99009258	PASSED
diehard_opso	0.56832620	PASSED	0.15988914	PASSED	0.26253176	PASSED
diehard_oqso	0.40336379	PASSED	0.91999608	PASSED	0.37058155	PASSED
diehard_dnaf^a	0.00000000	FAILED	0.00000000	FAILED	0.00000000	FAILED
diehard_count_1s_str	0.66577413	PASSED	0.11138346	PASSED	0.53068815	PASSED
diehard_count_1s_byt	0.81923708	PASSED	0.45019089	PASSED	0.58861666	PASSED
diehard_parking_lot^b	0.00121663	WEAK	0.05284251	PASSED	0.00361700	WEAK
diehard_2dsphere	0.36901907	PASSED	0.52750206	PASSED	0.08143639	PASSED
diehard_3dsphere	0.58567182	PASSED	0.33426376	PASSED	0.71959209	PASSED
diehard_squeeze	0.75382111	PASSED	0.39326502	PASSED	0.09595744	PASSED
diehard_sums^a	0.00000000	FAILED	0.00000000	FAILED	0.00000000	FAILED
diehard_runs^b	0.00044465	WEAK	0.63366484	PASSED	0.00003200	WEAK
diehard_runs^b	0.00535737	PASSED	0.00299446	WEAK	0.02800121	PASSED
diehard_craps	0.57725999	PASSED	0.23469887	PASSED	0.51687300	PASSED
diehard_craps	0.81707712	PASSED	0.68258640	PASSED	0.52083790	PASSED
marsaglia_tsang_gcd	0.98801200	PASSED	0.16828071	PASSED	0.56565025	PASSED
marsaglia_tsang_gcd^b	0.00000598	WEAK	0.00031066	WEAK	0.08076890	PASSED
sts_monobit	0.58908069	PASSED	0.06243728	PASSED	0.49880536	PASSED
sts_runs	0.42627149	PASSED	0.80074048	PASSED	0.85205871	PASSED
rgb_min_dist2	0.43323639	PASSED	0.36686754	PASSED	0.79623440	PASSED
rgb_min_dist3	0.20284185	PASSED	0.58414043	PASSED	0.30250779	PASSED
rgb_min_dist4	0.05563335	PASSED	0.12590913	PASSED	0.38598271	PASSED
rgb_min_dist5^a	0.00000000	FAILED	0.00000000	FAILED	0.00000000	FAILED
rgb_permut2	0.41418881	PASSED	0.02504907	PASSED	0.29188664	PASSED
rgb_permut3	0.22652895	PASSED	0.60146354	PASSED	0.53221609	PASSED
rgb_permut4	0.09163819	PASSED	0.99714286	WEAK	0.77833530	PASSED
rgb_permut5	0.95031695	PASSED	0.58183383	PASSED	0.17283754	PASSED
rgb_kstest_test^a	0.00000000	FAILED	0.00000000	FAILED	0.00000000	FAILED
dab_bytedistrib	0.56041951	PASSED	0.49953976	PASSED	0.91042657	PASSED
dab_dct	0.47051231	PASSED	0.04885619	PASSED	0.71440763	PASSED
dab_filltree	0.79939149	PASSED	0.17816386	PASSED	0.77136763	PASSED
dab_filltree	0.82584171	PASSED	0.94384820	PASSED	0.90826535	PASSED
dab_filltree2	0.50368150	PASSED	0.99662948	WEAK	0.04330603	PASSED
dab_filltree2	0.16191534	PASSED	0.45821357	PASSED	0.15654570	PASSED
dab_monobit2	0.00095433	WEAK	0.61054454	PASSED	0.30524221	PASSED

Test also fails control PRNGs.

Test is biased low for control PRNGs.

The fourth and fifth columns in Table 8 show the SS4x256 PRNG in normal operation of pointers to draw “cards” for the case in which the entropy decks are neither cut nor shuffled. The very strong performance shown in the fourth and fifth columns is only due to the appearance of randomness in the pointers taken from the arithmetic streams. With two high p-values, this mode is also similar in performance to the best-known PRNGs.

Finally, the sixth and seventh columns represent the gold standard mode in which the pointers as shown in the fourth and fifth columns are used to point to the fully shuffled data as shown in the second and third columns with the only exception that riffle shuffles and cuts are alternated on each successive draw since this mode is rather slow. As previously stated, there is no correlation whatsoever between the operations leading to the p-values in the second column and those leading to the p-values in fourth column. Any patterns would be a purely coincidental occurrence between these streams, each of which independently performs extremely well on the tests as shown in columns two through five in Table 8. The results of the gold standard mode can be used to confirm the shortcomings in the highlighted tests in Table 8 and may suggest that other tests such as the diehard_birthdays may be biased low.

Alternatively, the gold standard mode may also suggest that certain tests are functioning well in spite of the performance of some of the best PRNGs. As an example, the rgb_minimum_distance, (n-tup = 4) test gives consistently low results at the $- m 100$ level, examples of which are seen in Table 4 and confirmed by extensive testing. However, Table 8 shows that exclusive use of shuffling produces a p-value which is somewhat low, that the exclusive use of dynamic pointers gives a higher p-value (as might be expected), and that the gold standard mode gives a p-value of 0.38598271. The gold standard p-value is considered to have passed and is considerably higher than p-values shown for both the AES and Mersenne Twister PRNGs in their full reports presented as Table 4. It is noted, however, that a number of subsequent runs of the gold standard mode for this particular test generally showed p-values below 0.410, and a large number of runs of the AES PRNG showed p-values below 0.15 so that the suggestion is made here that this test could be questioned. The gold standard mode, along with the other two modes of operation shown in Table 8, also suggests that the diehard_opso and diehard_oqso tests are functioning correctly, at least with the $- m 100$ option. Tests omitted from Table 8 are summarized in Table 9, including all 75 runs of the sts_serial, rgb_bitdist and rgb_lagged_sum tests as noted in the caption. The table indicates that p-values for the three operational modes were consistent with a uniform random variable on [0,1].

Table 9.

Summary of tests excluded from Table 8 for various operational modes of the SS4x256 PRNG: sts_serial (n-tup = 1, 2 and two runs each at 3 through 16), rgb_bitdist (n-tup = 1 through 12), and rgb_lagged_sum (n-tup = 0 through 32).

Mode of operation	Minimum p-value	Maximum p-value	Mean	Standard deviation
Static pointer	0.014094	0.994640	0.494104	0.306707
Static entropy	0.012648	0.996126	0.531295	0.296427
Gold standard	0.000096	0.990275	0.485903	0.285323

7. Conclusion

Avoiding the difficulties associated with attempts to emulate randomness in simple algorithms, the present effort has highlighted an alternative strategy with three main features. First, the digits sufficiently far removed from the most significant in many streams of numbers arising from computations will pass tests based on similarity to apparent randomness. Second, entropy sources of digits may be shuffled in similar fashion to playing cards, and drawing from this process also passes tests seeking to identify patterns not representative of apparent randomness. Third, when the former digits are used to form pointers to the entropy pool locations of the latter digits, with no correlation between the two sets of digits, the interaction can only be purely coincidental. The claim is made that the coincidental interaction between two sources which each, independently, strongly emulate random behavior, is also an excellent model for apparently random behavior. Numerical test results were presented in support of these claims.

Expanding on the composition of a PRNG as two dissociated components, pointers and entropy sources, an attractive feature is that both the pointers and the dynamic entropy may each be verified in isolation. Each was shown to perform well in isolation under empirical testing at test levels similar to the best-known PRNGs. Thus, it was shown that the pointer generation schemes generally emulated uniform randomness over the draw locations when entropy shuffling was completely suppressed and that the entropy shuffling schemes also emulated uniform randomness in at least one of the draw positions when the pointers were set to point to the same draw location on every call. A gold standard mode of operation was presented in which both the pointers and the entropy decks were varied on every draw, giving purely coincidental interaction between the two excellent dissociated sources. The gold standard mode was used to assess the tests in Dieharder themselves and showed acceptable results in at least one test (rgb_minimum_distance, n-tup = 4), although this particular test is biased low for both the AES PRNG and the Mersenne Twister as well as for the gold standard mode itself. While the expense of gold standard modes may not be required in all applications, they should be able to provide strong similarities to randomness under the increased scrutiny made possible by future hardware improvements.

Using various shuffling rates, the new PRNGs perform at least as well as the AES PRNG on empirical tests, yet one integer PRNG was 49% faster than the AES PRNG and another PRNG produced 14-digit hexadecimal floats at rates comparable to the AES PRNG’s production of 8-digit hexadecimal integers. The fastest unpredictable integer PRNG is approximately 38% of the speed of the predictable Mersenne Twister. The PRNG designed to have the longest period has approximately 1.135 × 10⁶²⁹⁶⁷⁵ states in the entropy pool alone in addition to a number of floating point stream and parameter states.

Footnotes

Acknowledgements

The author acknowledges the thoroughness of the referees and is most appreciative of their work in suggesting improvements for the manuscript.

Funding

This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

ORCID iD

Joseph D Richardson

Author biography

Dr. Joseph D Richardson is an Assistant Professor in the William B. Burnsed Jr. Mechanical, Aerospace, and Biomedical Engineering Department at the University of South Alabama. He has held positions at the University of Alabama in Huntsville, Tennessee Tech University, Oak Ridge National Laboratory, and has worked as a NASA subcontractor. His interests include computational mechanics, boundary element methods, and most aspects of computer simulation. He holds a PhD in Mechanical Engineering from Vanderbilt University.

References

Free Software Foundation. GNU Scientific Library (GSL), version 1.16, 2013, http://www.gnu.org/software/gsl/

Ziff

. Four-tap shift-register-sequence random-number generators. Comput Phys 1998; 12: 385–392.

Matsumoto

Nishimura

. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM T Model Comput S 1998; 8: 3–30.

L’Ecuyer

. Maximally equidistributed combined Tausworthe generators. Math Comput 1996; 65: 203–213.

Lüscher

. A portable high-quality random number generator for lattice field theory simulations. Comput Phys Commun 1994; 79: 100–110.

Brown

. Dieharder: a random number test suite, 2015, https://webhome.phy.duke.edu/~rgb/General/dieharder.php

Hellekalek

Wegenkittl

. Empirical evidence concerning AES. ACM T Model Comput S 2003; 13: 322–333.

Marsaglia

. Random number generators. J Mod Appl Stat Meth 2003; 2: 2–13.

Brown

Bauer

. RDieHarder: R interface to the “DieHarder” RNG test suite, 2018, https://cran.r-project.org/web/packages/RDieHarder/index.html

10.

Marsaglia

. The Marsaglia random number CDROM including the diehard battery of tests of randomness, 1995, http://ftpmirror.your.org/pub/misc/diehard/

11.

Bassham

Rukhin

Soto

, et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications. National Institute of Standards and Technology (NIST) special publication 800-22, revision 1a, April 2010. Gaithersburg, MD: NIST.