NIST SP 800-22 Rev. 1 日本語訳

¹ Statistical Engineering Division

² Computer Security Division

Information Technology Laboratory

National Institute of Standards and Technology

Gaithersburg, MD 20899-8930

A statistical test is formulated to test a specific null hypothesis (\(\mathrm{H0}\)). For the purpose of this document, the null hypothesis under test is that the sequence being tested is random. Associated with this null hypothesis is the alternative hypothesis (\(\mathrm{Ha}\)), which, for this document, is that the sequence is not random. For each applied test, a decision or conclusion is derived that accepts or rejects the null hypothesis, i.e., whether the generator is (or is not) producing random values, based on the sequence that was produced.

In practice, the reason that statistical hypothesis testing works is that the reference distribution and the critical value are dependent on and generated under a tentative assumption of randomness. If the randomness assumption is, in fact, true for the data at hand, then the resulting calculated test statistic value on the data will have a very low probability (e.g., 0.01 %) of exceeding the critical value. On the other hand, if the calculated test statistic value does exceed the critical value (i.e., if the low probability event does in fact occur), then from a statistical hypothesis testing point of view, the low probability event should not occur naturally. Therefore, when the calculated test statistic value exceeds the critical value, the conclusion is made that the original assumption of randomness is suspect or faulty. In this case, statistical hypothesis testing yields the following conclusions: reject \(H_{0}\) (randomness) and accept \(H_{a}\) (non-randomness).

Statistical hypothesis testing is a conclusion-generation procedure that has two possible outcomes, either accept \(H_{0}\) (the data is random) or accept \(H_{a}\) (the data is non-random). The following 2 by 2 table relates the true (unknown) status of the data at hand to the conclusion arrived at using the testing procedure.

If the data is, in truth, random, then a conclusion to reject the null hypothesis (i.e., conclude that the data is non-random) will occur a small percentage of the time. This conclusion is called a Type I error. If the data is, in truth, non-random, then a conclusion to accept the null hypothesis (i.e., conclude that the data is actually random) is called a Type II error. The conclusions to accept \(H_{0}\) when the data is really random, and to reject \(H_{0}\) when the data is non-random, are correct.

Each test is based on a calculated test statistic value, which is a function of the data. If the test statistic value is \(S\) and the critical value is \(t\), then the Type I error probability is \(P(S>t\mathrel{\|}H_o\text{ is true})=P(\text{reject }H_o\mid H_0\text{ is true})\), and the Type II error probability is \(P(S\le t\mathrel{\|}H_0\text{ is false})=P(\text{accept }H_0\mid H_0\text{ is false})\). The test statistic is used to calculate a \(P\text{-value}\) that summarizes the strength of the evidence against the null hypothesis. For these tests, each \(P\text{-value}\) is the probability that a perfect random number generator would have produced a sequence less random than the sequence that was tested, given the kind of non-randomness assessed by the test. If a \(P\text{-value}\) for a test is determined to be equal to 1, then the sequence appears to have perfect randomness. A \(P\text{-value}\) of zero indicates that the sequence appears to be completely non-random. A significance level \((\alpha)\) can be chosen for the tests. If \(P\text{-value}\ge\alpha\), then the null hypothesis is accepted; i.e., the sequence appears to be random. If \(P\text{-value}<\alpha\), then the null hypothesis is rejected; i.e., the sequence appears to be non-random. The parameter \(\alpha\) denotes the probability of the Type I error. Typically, \(\alpha\) is chosen in the range [0.001, 0.01].

• An \(\alpha\) of 0.001 indicates that one would expect one sequence in 1000 sequences to be rejected by the test if the sequence was random. For a \(P\text{-value} \ge 0.001\), a sequence would be considered to be random with a confidence of 99.9%. For a \(P\text{-value} < 0.001\), a sequence would be considered to be non-random with a confidence of 99.9%.

• An \(\alpha\) of 0.01 indicates that one would expect 1 sequence in 100 sequences to be rejected. A \(P\text{-value} \ge 0.01\) would mean that the sequence would be considered to be random with a confidence of 99%. A \(P\text{-value} < 0.01\) would mean that the conclusion was that the sequence is non-random with a confidence of 99%.

1. Uniformity: At any point in the generation of a sequence of random or pseudorandom bits, the occurrence of a zero or one is equally likely, i.e., the probability of each is exactly \(1/2\). The expected number of zeros (or ones) is \(n/2\), where \(n\) = the sequence length.

A number of tests in the test suite have the standard normal and the chi-square (\(\chi^2\)) as reference distributions. If the sequence under test is in fact non-random, the calculated test statistic will fall in extreme regions of the reference distribution. The standard normal distribution (i.e., the bell-shaped curve) is used to compare the value of the test statistic obtained from the RNG with the expected value of the statistic under the assumption of randomness. The test statistic for the standard normal distribution is of the form \(z = (x - \mu)/\sigma\), where \(x\) is the sample test statistic value, and \(\mu\) and \(\sigma^2\) are the expected value and the variance of the test statistic. The \(\chi^2\) distribution (i.e., a left skewed curve) is used to compare the goodness-of-fit of the observed frequencies of a sample measure to the corresponding expected frequencies of the hypothesized distribution. The test statistic is of the form \(\chi^2 = \sum\left((o_i - e_i)^2 / e_i\right)\), where \(o_i\) and \(e_i\) are the observed and expected frequencies of occurrence of the measure, respectively.

For many of the tests in this test suite, the assumption has been made that the size of the sequence length, \(n\), is large (of the order \(10^3\) to \(10^7\)). For such large sample sizes of \(n\), asymptotic reference distributions have been derived and applied to carry out the tests. Most of the tests are applicable for smaller values of \(n\). However, if used for smaller values of \(n\), the asymptotic reference distributions would be inappropriate and would need to be replaced by exact distributions that would commonly be difficult to compute.

Note: For many of the examples throughout Section 2, small sample sizes are used for illustrative purposes only, e.g., \(n = 10\). The normal approximation is not really applicable for these examples.

\(\varepsilon\) The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; \(\varepsilon = \varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n\).

\(s_{\mathrm{obs}}\): The absolute value of the sum of the \(X_i\) (where, \(X_i = 2\varepsilon - 1 = \pm 1\)) in the sequence divided by the square root of the length of the sequence.

(1) Conversion to \(\pm 1\): The zeros and ones of the input sequence (\(\varepsilon\)) are converted to values of \(-1\) and \(+1\) and are added together to produce \(S_n = X_1 + X_2 + \cdots + X_n\), where \(X_i = 2\varepsilon_i - 1\).

For example, if \(\varepsilon=1011010101\), then \(n=10\) and \(S_n=1+(-1)+1+1+(-1)+1+(-1)+1+(-1)+1=2\).

(2) Compute the test statistic

For the example in this section,

(3) Compute

where \(\operatorname{erfc}\) is the complementary error function as defined in Section 5.5.3.

For the example in this section,

Since the \(P\text{-value}\) obtained in step 3 of Section 2.1.4 is \(\ge 0.01\) (i.e., \(P\text{-value} = 0.527089\)), the conclusion is that the sequence is random.

Note that if the \(P\text{-value}\) were small (\(< 0.01\)), then this would be caused by \(|S_n|\) or \(|s_{\mathrm{obs}}|\) being large. Large positive values of \(S_n\) are indicative of too many ones, and large negative values of \(S_n\) are indicative of too many zeros.

It is recommended that each sequence to be tested consist of a minimum of 100 bits (i.e., \(n\ge100\)).

(input) \(\varepsilon=\) 1100100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000

\(n = 100\)

(processing) \(S_{100}=-16\)

(processing) \(s_{\mathrm{obs}}=1.6\)

(conclusion) Since \(P\text{-value}\ge0.01\), accept the sequence as random.

The focus of the test is the proportion of ones within \(\mathrm{M}\)-bit blocks. The purpose of this test is to determine whether the frequency of ones in an \(\mathrm{M}\)-bit block is approximately \(\mathrm{M}/2\), as would be expected under an assumption of randomness. For block size \(M=1\), this test degenerates to test 1, the Frequency (Monobit) test.

\(\varepsilon\) The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; \(\varepsilon = \varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n\).

\(\chi^2(\mathrm{obs})\): A measure of how well the observed proportion of ones within a given \(M\)-bit block match the expected proportion (1/2).

The reference distribution for the test statistic is a \(\chi^2\) distribution.

(1) Partition the input sequence into \(N = \left\lfloor \frac{n}{M} \right\rfloor\) non-overlapping blocks. Discard any unused bits.

For example, if \(n = 10\), \(M = 3\) and \(\varepsilon = 0110011010\), 3 blocks (\(N = 3\)) would be created, consisting of 011, 001 and 101. The final 0 would be discarded.

(2) Determine the proportion \(\pi_i\) of ones in each \(M\)-bit block using the equation

for \(1 \le i \le N\).

For the example in this section, \(\pi_1 = 2/3\), \(\pi_2 = 1/3\), and \(\pi_3 = 2/3\).

(3) Compute the \(\chi^2\) statistic:

For the example in this section,

(4) Compute

where \(\operatorname{igamc}\) is the incomplete gamma function for \(Q(a,x)\) as defined in Section 5.5.3.

Note: When comparing this section against the technical description in Section 3.2, note that \(Q(a,x) = 1-P(a,x)\).

For the example in this section,

Since the \(P\text{-value}\) obtained in step 4 of Section 2.2.4 is \(\ge \) 0.01 (i.e., \(P\text{-value}\) = 0.801252), the conclusion is that the sequence is random.

It is recommended that each sequence to be tested consist of a minimum of 100 bits (i.e., \(n \ge 100\)). Note that \(n \ge MN\). The block size \(M\) should be selected such that \(M \ge 20\), \(M > .01n\) and \(N < 100\).

(input) \(\varepsilon=\) 1100100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000

\(n = 100\)

\(M = 10\)

(processing) \(N = 10\)

(processing) \(\chi^2=7.2\)

(conclusion) Since \(P\text{-value}\ge0.01\), accept the sequence as random.

\(\varepsilon\) The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; \(\varepsilon = \varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n\).

\(V_n(\mathrm{obs})\): The total number of runs (i.e., the total number of zero runs + the total number of one-runs) across all \(n\) bits.

The reference distribution for the test statistic is a \(\chi^2\) distribution.

(1) Compute the pre-test proportion \(\pi\) of ones in the input sequence:

For example, if \(\varepsilon = 1001101011\), then \(n=10\) and \(\pi = 6/10 = 3/5\).

(2) Determine if the prerequisite Frequency test is passed: If it can be shown that \(\left|\pi - \frac{1}{2}\right| \ge \tau\), then the Runs test need not be performed (i.e., the test should not have been run because of a failure to pass test 1, the Frequency (Monobit) test). If the test is not applicable, then the \(P\text{-value}\) is set to 0.0000. Note that for this test, \(\tau = \frac{2}{\sqrt{n}}\) has been pre-defined in the test code.

For the example in this section, since \(\tau = 2/\sqrt{10} \approx 0.63246\), then \(|\pi - 1/2| = |3/5 - 1/2| = 0.1 < \tau\), and the test is not run.

Since the observed value \(\pi\) is within the selected bounds, the runs test is applicable.

(3) Compute the test statistic

where \(r(k)=0\) if \(\varepsilon_k=\varepsilon_{k+1}\), and \(r(k)=1\) otherwise.

Since \(\varepsilon = 1\ 00\ 11\ 0\ 1\ 0\ 11\), then

(4) Compute

For the example:

Since the \(P\text{-value}\) obtained in step 4 of Section 2.3.4 is \(\ge\) 0.01 (i.e., \(P\text{-value}\) = 0.147232), the conclusion is that the sequence is random.

Note that a large value for \(V_n(\mathrm{obs})\) would have indicated an oscillation in the string which is too fast; a small value would have indicated that the oscillation is too slow. (An oscillation is considered to be a change from a one to a zero or vice versa.) A fast oscillation occurs when there are a lot of changes, e.g., 010101010 oscillates with every bit. A stream with a slow oscillation has fewer runs than would be expected in a random sequence, e.g., a sequence containing 100 ones, followed by 73 zeroes, followed by 127 ones (a total of 300 bits) would have only three runs, whereas 150 runs would be expected.

It is recommended that each sequence to be tested consist of a minimum of 100 bits (i.e., \(n\ge100\)).

(input) \(\varepsilon=\) 1100100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000

\(n = 100\)

(input) \(\tau=0.02\)

(processing) \(\pi=0.42\)

(processing) \(V_n(\mathrm{obs})=52\)

(conclusion) Since \(P\text{-value}\ge0.01\), accept the sequence as random.

\(M\): The length of each block. The test code has been pre-set to accommodate three values for M: \(M=8\), \(M=128\) and \(M=10^4\) in accordance with the following values of sequence length, \(n\):

\(\chi^2(\mathrm{obs})\): A measure of how well the observed longest run length within \(M\)-bit blocks matches the expected longest length within \(M\)-bit blocks.

The reference distribution for the test statistic is a \(\chi^2\) distribution.

(2) Tabulate the frequencies \(v_i\) of the longest runs of ones in each block into categories, where each cell contains the number of runs of ones of a given length.

For the values of \(M\) supported by the test code, the \(v_i\) cells will hold the following counts:

(3) Compute

where the values for \(\pi_i\) are provided in Section 3.4. The values of \(K\) and \(N\) are determined by the value of \(M\) in accordance with the following table:

For the example of 2.4.8,

(4) Compute

For the example,

For the example in Section 2.4.8, since the P-value \(\ge \) 0.01 \(( P\text{-value}\) = \(0.180609 ) ,\) the conclusion is that the sequence is random. Note that large values of \(χ^{2} ( \mathrm{obs} )\) indicate that the tested sequence has clusters of ones.

For the case where \(K = 3\) and \(M = 8\):

(input) \(ε\) = 11001100000101010110110001001100111000000000001001 00110101010001000100111101011010000000110101111100 1100111001101101100010110010

\(n = 128\)

(processing) \(ν_{0} = 4 ; ν_{1} = 9 ; ν_{2} = 3 ; ν_{4} = 0 ; χ^{2} = 4.882457\)

(conclusion) Since the \(P\text{-value}\) is \(\ge \) 0.01, accept the sequence as random.

\(Q\) The number of columns in each matrix. For the test suite, \(Q\) has been set to 32. If other values of \(Q\) are used, new approximations need to be computed.

\(χ^{2} ( \mathrm{obs} )\): A measure of how well the observed number of ranks of various orders match the expected number of ranks under an assumption of randomness.

The reference distribution for the test statistic is a \(χ^{2}\) distribution.

(1) Sequentially divide the sequence into \(M\bullet Q\)-bit disjoint blocks; there will exist \(N=\left\lfloor\frac{n}{MQ}\right\rfloor\) such blocks. Discarded bits will be reported as not being used in the computation within each block. Collect the \(M\bullet Q\) bit segments into \(M\) by \(Q\) matrices. Each row of the matrix is filled with successive \(Q\)-bit blocks of the original sequence \(\varepsilon\).

For example, if \(n=20\), \(M=Q=3\), and \(\varepsilon=01011001001010101101\), then partition the stream into \(N=\left\lfloor\frac{n}{3\bullet 3}\right\rfloor=2\) matrices of cardinality \(M\bullet Q\) (\(3\bullet 3=9\)). Note that the last two bits (0 and 1) will be discarded. The two matrices are \(\begin{vmatrix}0&1&0\\1&1&0\\0&1&0\end{vmatrix}\) and \(\begin{vmatrix}0&1&0\\1&0&1\\0&1&1\end{vmatrix}\). Note that the first matrix consists of the first three bits in row 1, the second set of three bits in row 2, and the third set of three bits in row 3. The second matrix is similarly constructed using the next nine bits in the sequence.

(2) Determine the binary rank ( \(R_l\) ) of each matrix, where \(l=1,\ldots,N\) . The method for determining the rank is described in Appendix A.

For the example in this section, the rank of the first matrix is 2 (\(R_1=2\)), and the rank of the second matrix is 3 (\(R_2=3\)).

(3) Let \(F_M\) = the number of matrices with \(R_\ell=M\) (full rank),
\(F_{M-1}\) = the number of matrices with \(R_\ell=M-1\) (full rank - 1),
\(N-F_M-F_{M-1}\) = the number of matrices remaining.

For the example in this section, \(F_M=F_3=1\) (\(R_2\) has the full rank of 3), \(F_{M-1}=F_2=1\) (\(R_1\) has rank 2), and no matrix has any lower rank.

(4) Compute

For the example in this section,

(5) Compute \(P\text{-value}=e^{-\chi^2(\mathrm{obs})/2}\). Since there are 3 classes in the example, the \(P\text{-value}\) for the example is equal to

For the example in this section,

Since the \(P\text{-value}\) obtained in step 5 of Section 2.5.4 is \(\ge\) 0.01 (\(P\text{-value}\) = 0.741948), the conclusion is that the sequence is random.

Note that large values of \(\chi^2(\mathrm{obs})\) (and hence, small \(P\text{-values}\)) would have indicated a deviation of the rank distribution from that corresponding to a random sequence.

The probabilities for \(M = Q = 32\) have been calculated and inserted into the test code. Other choices of \(M\) and \(Q\) may be selected, but the probabilities would need to be calculated. The minimum number of bits to be tested must be such that \(n \ge 38MQ\) (i.e., at least 38 matrices are created). For \(M = Q = 32 ,\) each sequence to be tested should consist of a minimum of 38,912 bits.

(input) \(\varepsilon\) = the first 100,000 binary digits in the expansion of \(e\)

(conclusion) Since \(P\text{-value}\ge0.01\), accept the sequence as random.

\(d\): The normalized difference between the observed and the expected number of frequency components that are beyond the 95 % threshold.

(1) The zeros and ones of the input sequence (\(\varepsilon\)) are converted to values of –1 and +1 to create the sequence \(X=x_1,x_2,\ldots,x_n\), where \(x_i=2\varepsilon_i-1\).

For example, if \(n=10\) and \(\varepsilon=1001010011\), then \(X=1,-1,-1,1,-1,1,-1,-1,1,1\).

(2) Apply a Discrete Fourier transform (DFT) on \(\mathrm{X}\) to produce: \(S = \mathit{DFT}(X)\). A sequence of complex variables is produced which represents periodic components of the sequence of bits at different frequencies (see Section 3.6 for a sample diagram of a DFT result).

(3) Calculate \(M=\operatorname{modulus}(S')\equiv|S'|\), where \(S'\) is the substring consisting of the first \(n/2\) elements in \(S\), and the modulus function produces a sequence of peak heights.

(4) Compute \(T=\sqrt{\left(\log\frac{1}{0.05}\right)n}\) = the 95 % peak height threshold value. Under an assumption of randomness, 95 % of the values obtained from the test should not exceed \(T\).

(5) Compute \(N_0=.95n/2\). \(N_0\) is the expected theoretical (95 %) number of peaks (under the assumption of randomness) that are less than \(T\).

For the example in this section, \(N_0\) = 4.75.

(6) Compute \(N_1\) = the actual observed number of peaks in \(M\) that are less than \(T\).

For the example in this section, \(N_1\) = 4.

(7) Compute

For the example in this section,

(8) Compute

For the example in this section,

Since the \(P\text{-value}\) obtained in step 8 of Section 2.6.4 is \(\ge 0.01\) (P-value = 0.029523), the conclusion is that the sequence is random.

It is recommended that each sequence to be tested consist of a minimum of 1000 bits (i.e., \(n \ge 1000 ) .\)

(input) \(\varepsilon=\) 1100100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000

(conclusion) Since \(P\text{-value}\ge0.01\), accept the sequence as random.

Additional input used by the function, but supplied by the testing code:

\(\varepsilon\) The sequence of bits as generated by the RNG or PRNG being tested; this exists as a global structure at the time of the function call; \(\varepsilon = \varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n\).

\(M\) The length in bits of the substring of \(ε\)to be tested.

\(χ^{2} ( \mathrm{obs} )\): A measure of how well the observed number of template “hits” matches the expected number of template “hits” (under an assumption of randomness).

The reference distribution for the test statistic is the \(χ^{2}\) distribution.

For example, if \(ε = 10100100101110010110 ,\) then \(n =\) 20. If \(N = 2\) and \(M = 10 ,\) then the two blocks would be 1010010010 and 1110010110.

(2) Let \(W_j\) (\(j=1,\ldots,N\)) be the number of times that \(B\) (the template) occurs within the block \(j\). Note that \(j=1,\ldots,N\). The search for matches proceeds by creating an \(m\)-bit window on the sequence, comparing the bits within that window against the template. If there is no match, the window slides over one bit, e.g., if \(m=3\) and the current window contains bits 3 to 5, then the next window will contain bits 4 to 6. If there is a match, the window slides over \(m\) bits, e.g., if the current (successful) window contains bits 3 to 5, then the next window will contain bits 6 to 8.

For the above example, if \(m = 3\) and the template \(B = 001\), then the examination proceeds as follows:

Thus, \(W_1 = 2\), and \(W_2 = 1\).

(3) Under an assumption of randomness, compute the theoretical mean \(\mu\) and variance \(\sigma^2\):

For the example in this section,

(4) Compute

For the example in this section,

(5) Compute

Note that multiple \(P\text{-values}\) will be computed, i.e., one \(P\text{-value}\) will be computed for each template. For \(m = 9\), up to 148 \(P\text{-values}\) may be computed; for \(m = 10\), up to 284 \(P\text{-values}\) may be computed.

For the example in this section,

Since the \(P\text{-value}\) obtained in step 5 of Section 2.7.4 is \(\ge 0.01\) (P-value = 0.344154), the conclusion is that the sequence is random.

The test code has been written to provide templates for \(m = 2 , 3 , \ldots , 10 .\) It is recommended that \(m = 9\) or \(m = 10\) be specified to obtain meaningful results. Although \(N = 8\) has been specified in the test code, the code may be altered to other sizes. However, \(N\) should be chosen such that \(N \le 100\) to be assured that the \(P\text{-value}s\) are valid. Additionally, be sure that \(M>0.01\cdot n\) and \(N=\lfloor n/M\rfloor\).

For a template \(B = 000000001\) whose size is \(m = 9\):

(input) \(\varepsilon = 2^{20}\) bits produced by the G-SHA-1 generator¹

(input) \(n = 2^{20}\), \(B = 000000001\)

(processing) \(\mu = 255.984375\) and \(\sigma^2 = 247.499999\)

(processing) \(W_1 = 259\); \(W_2 = 229\); \(W_3 = 271\); \(W_4 = 245\); \(W_5 = 272\); \(W_6 = 262\); \(W_7 = 259\); and \(W_8 = 246\)

(processing) \(χ^{2} ( \mathrm{obs} ) = 5.999377\)

(conclusion) Since the \(P\text{-value} \ge 0.01 ,\) accept the sequence as random.

\(M\) The length in bits of a substring of \(ε\) to be tested. \(M\) has been set to 1032 in the test code.

\(χ^{2} ( \mathrm{obs} )\): A measure of how well the observed number of template “hits” matches the expected number of template “hits” (under an assumption of randomness).

The reference distribution for the test statistic is the \(χ^{2}\) distribution.

For example, if \(\varepsilon = 1011101111\mathbf{0010110100}0111001011\mathbf{1011111000}0101101001\), then \(n = 50\). If \(K = 2\), \(M = 10\) and \(N = 5\), then the five blocks are \(1011101111\), \(0010110100\), \(0111001011\), \(1011111000\), and \(0101101001\).

(2) Calculate the number of occurrences of \(B\) in each of the \(N\) blocks. The search for matches proceeds by creating an \(m\)-bit window on the sequence, comparing the bits within that window against \(B\) and incrementing a counter when there is a match. The window slides over one bit after each examination, e.g., if \(m = 4\) and the first window contains bits 42 to 45, the next window consists of bits 43 to 46. Record the number of occurrences of \(B\) in each block by incrementing an array \(v_i\) (where \(i = 0,\ldots5\)), such that \(v_0\) is incremented when there are no occurrences of \(B\) in a substring, \(v_1\) is incremented for one occurrence of \(B\),…and \(v_5\) is incremented for 5 or more occurrences of \(B\).

For the above example, if \(m = 2\) and \(B = 11\), then the examination of the first block (1011101111) proceeds as follows:

Thus, after block 1, there are five occurrences of 11, \(v_5\) is incremented, and \(v_0 = 0\), \(v_1 = 0\), \(v_2 = 0\), \(v_3 = 0\), \(v_4 = 0\), and \(v_5 = 1\).

In a like manner, blocks 2-5 are examined. In block 2, there are 2 occurrences of 11; \(v_2\) is incremented. In block 3, there are 3 occurrences of 11; \(v_3\) is incremented. In block 4, there are 4 occurrences of 11; \(v_4\) is incremented. In block 5, there is one occurrence of 11; \(v_1\) is incremented.

Therefore, \(v_0 = 0\), \(v_1 = 1\), \(v_2 = 1\), \(v_3 = 1\), \(v_4 = 1\), \(v_5 = 1\) after all blocks have been examined.

(3) Compute values for \(\lambda\) and \(\eta\) that will be used to compute the theoretical probabilities \(\pi_i\) corresponding to the classes of \(v_0\):

For the example in this section, \(\lambda = (10-2+1)/2^2 = 2.25\), and \(\eta = \lambda/2 = 1.125\).

(4) Compute

where \(\pi_0 = 0.364091\), \(\pi_1 = 0.185659\), \(\pi_2 = 0.139381\), \(\pi_3 = 0.100571\), \(\pi_4 = 0.070432\) and \(\pi_5 = 0.139865\) as specified in Section 3.8.

For the example in this section, the values of \(\pi_i\) were recomputed, since the example doesn’t fit the requirements stated in Section 2.8.7. The example is intended only for illustration. The values of \(\pi_i\) are: \(\pi_0 = 0.324652\), \(\pi_1 = 0.182617\), \(\pi_2 = 0.142670\), \(\pi_3 = 0.106645\), \(\pi_4 = 0.077147\), and \(\pi_5 = 0.166269\).

(5) Compute

For the example in this section,

Since the \(P\text{-value}\) obtained in step 4 of Section 2.8.4 is \(\ge 0.01\) (\(P\text{-value} = 0.274932\)), the conclusion is that the sequence is random.

Note that for the 2-bit template (\(B = 11\)), if the entire sequence had too many 2-bit runs of ones, then: 1) \(v_5\) would have been too large, 2) the test statistic would be too large, 3) the \(P\text{-value}\) would have been small (< 0.01) and 4) a conclusion of non-randomness would have resulted.

The values of \(K,M\) and \(N\) have been chosen such that each sequence to be tested consists of a minimum of \(10^{6}\) bits (i.e., \(n\ge10^6\)). Various values of \(m\) may be selected, but for the time being, NIST recommends \(m = 9\) or \(m = 10 .\) If other values are desired, please choose these values as follows:

• \(n\ge MN\).
• \(N\) should be chosen so that \(N\cdot(\min\pi_i)>5\).
• \(\lambda=(M-m+1)/2^m\approx2\).
• \(m\) should be chosen so that \(m\approx\log_2M\).
• Choose \(K\) so that \(K\approx2\lambda\). Note that the \(\pi_i\) values would need to be recalculated for values of \(K\) other than 5.

(input) \(\varepsilon\) = the binary expansion of \(e\) up to 1,000,000 bits

\(n = 1000000\), \(B = 111111111\)

(processing) \(ν_{0} = 329\); \(ν_{1} = 164\); \(ν_{2} = 150\); \(ν_{3} = 111\); \(ν_{4} = 78\); and \(ν_{5} = 136\)

(processing) \(χ^{2} ( \mathrm{obs} ) = 8.965859\)

(conclusion) Since the \(P\text{-value} \ge 0.01 ,\) accept the sequence as random.

\(L\) The length of each block. Note: the use of \(\mathrm{L}\) as the block size is not consistent with the block size notation (\(M\)) used for the other tests. However, the use of \(\mathrm{L}\) as the block size was specified in the original source of Maurer's test.

\(f_n\) : The sum of the \(\log_2\) distances between matching \(L\)-bit templates, i.e., the sum of the number of digits in the distance between \(L\)-bit templates.

For example, if \(ε = 01011010011101010111 ,\) then \(n = 20 .\) If \(L = 2\) and \(Q = 4 ,\) then \(K=\lfloor n/L\rfloor-Q=\lfloor20/2\rfloor-4=6\) . The initialization segment is 01011010; the test segment is 011101010111. The \(L\)-bit blocks are shown in the following table:

(2) Using the initialization segment, a table is created for each possible \(L -\)bit value (i.e., the \(L -\)bit value is used as an index into the table). The block number of the last occurrence of each \(L -\)bit block is noted in the table (i.e., For \(i\) from \(1\) to \(Q , T_{j} = i ,\) where \(j\) is the decimal representation of the contents of the \(i\)^th \(L\)-bit block).

(3) Examine each of the \(K\) blocks in the test segment and determine the number of blocks since the last occurrence of the same \(L\)-bit block (i.e., \(i - T_j\)). Replace the value in the table with the location of the current block (i.e., \(T_j = i\)). Add the calculated distance between re-occurrences of the same \(L\)-bit block to an accumulating \(\log_2\) sum of all the differences detected in the \(K\) blocks (i.e., \(\mathit{sum} = \mathit{sum} + \log_2(i - T_j)\)).

For block 5 (the 1^st test block): 5 is placed in the “01” row of the table (i.e., \(T_1\)), and

For block 6: 6 is placed in the “11” row of the table (i.e., \(T_3\)), and

For block 7: 7 is placed in the “01” row of the table (i.e., \(T_1\)), and

For block 8: 8 is placed in the “01” row of the table (i.e., \(T_1\)), and

For block 9: 9 is placed in the “01” row of the table (i.e., \(T_1\)), and

For block 10: 10 is placed in the “11” row of the table (i.e., \(T_3\)), and

(4) Compute the test statistic:

where \(T_j\) is the table entry corresponding to the decimal representation of the contents of the \(i\)^th \(L\)-bit block.

For the example in this section,

(5) Compute

where \(\operatorname{erfc}\) is defined in Section 5.5.3, and \(\operatorname{expectedValue}(L)\) and \(\sigma\) are taken from a table of precomputed values² (see the table below). Under an assumption of randomness, the sample mean, \(\operatorname{expectedValue}(L)\), is the theoretical expected value of the computed statistic for the given \(L\)-bit length. The theoretical standard deviation is given by

where

For the example in this section, \(P\text{-value} = \operatorname{erfc}\left(\left|\frac{1.1949875 - 1.5374383}{\sqrt{2}\sqrt{1.338}}\right|\right) = 0.767189\). Note that the expected value and variance for \(L = 2\) are not provided in the above table, since a block of length two is not recommended for testing. However, this value for \(L\) is easy to use in an example. The value for the expected value and variance for the case where \(L = 2\), although not shown in the above table, were taken from the indicated reference³.

Since the \(P\text{-value}\) obtained in step 5 of Section 2.9.4 is \(\ge\) 0.01 (P-value = 0.767189), the conclusion is that the sequence is random.

Theoretical expected values for \(\varphi\) have been computed as shown in the table in step (5) of Section 2.9.4. If \(f_n\) differs significantly from \(\operatorname{expectedValue}(L)\), then the sequence is significantly compressible.

This test requires a long sequence of bits (\(n \ge (Q + K)L\)) which are divided into two segments of \(L\)-bit blocks, where \(L\) should be chosen so that \(6 \le L \le 16\). The first segment consists of \(Q\) initialization blocks, where \(Q\) should be chosen so that \(Q = 10 \bullet 2^L\). The second segment consists of \(K\) test blocks, where \(K = \lceil n/L \rceil - Q \approx 1000 \bullet 2^L\). The values of \(L\), \(Q\) and \(n\) should be chosen as follows:

(input) \(ε =\) A binary string constructed using G-SHA-1⁴

\(n = 1048576\), \(L = 7\), \(Q = 1280\)

(processing) \(c=0.591311,\quad\sigma=0.002703,\quad K=148516,\quad\operatorname{sum}=919924.038020\)

(processing) \(f_n=6.194107,\quad\operatorname{expectedValue}=6.196251,\quad\sigma=3.125\)

³ From the “Handbook of Applied Cryptography.”

⁴ Defined in FIPS 186-2.

(conclusion) Since \(P\text{-value}\ge0.01\), accept the sequence as random.

\(K\) The number of degrees of freedom; \(K = 6\) has been hard coded into the test.

\(χ^{2} ( \mathrm{obs} )\): A measure of how well the observed number of occurrences of fixed length LFSRs matches the expected number of occurrences under an assumption of randomness.

The reference distribution for the test statistic is the \(χ^{2}\) distribution.

(1) Partition the \(n\)-bit sequence into \(N\) independent blocks of \(M\) bits, where \(n = MN\).

(2) Using the Berlekamp-Massey algorithm⁵, determine the linear complexity \(L_i\) of each of the \(N\) blocks (\(i = 1,\ldots,N\)). \(L_i\) is the length of the shortest linear feedback shift register sequence that generates all bits in the block \(i\). Within any \(L_i\)-bit sequence, some combination of the bits, when added together modulo 2, produces the next bit in the sequence (bit \(L_i + 1\)).

For example, if \(M = 13\) and the block to be tested is \(1101011110001\), then \(L_i = 4\), and the sequence is produced by adding the 1^st and 2^nd bits within a 4-bit subsequence to produce the next bit (the 5^th bit). The examination proceeded as follows:

(1) Under an assumption of randomness, calculate the theoretical mean \(\mu\):

For the example in this section,

(4) For each substring, calculate a value of \(T_i\), where

For the example,

(5) Record the \(T_i\) values in \(v_0,\ldots,v_6\) as follows:

If:

(6) Compute

where \(\pi_0=0.010417\), \(\pi_1=0.03125\), \(\pi_2=0.125\), \(\pi_3=0.5\), \(\pi_4=0.25\), \(\pi_5=0.0625\), \(\pi_6=0.020833\) are the probabilities computed by the equations in Section 3.10.

(7) Compute

If the \(P\text{-value}\) were \(< 0.01 ,\) this would have indicated that the observed frequency counts of \(T_{i}\) stored in the \(ν_{I}\) bins varied from the expected values; it is expected that the distribution of the frequency of the \(T_{i}\) (in the \(ν_{I}\) bins) should be proportional to the computed \(π_{i}\) as shown in step (6) of Section 2.10.5.

Choose \(n \ge 10^{6} .\) The value of \(M\) must be in the range \(500 \le M \le 5000 ,\) and \(N \ge 200\) for the \(χ^{2}\) result to be valid (see Section 3.10 for a discussion).

(conclusion) Since the \(P\text{-value} \ge 0.01 ,\) accept the sequence as random.

The focus of this test is the frequency of all possible overlapping \(m -\)bit patterns across the entire sequence. The purpose of this test is to determine whether the number of occurrences of the \(2^m\) \(m\)-bit overlapping patterns is approximately the same as would be expected for a random sequence. Random sequences have uniformity; that is, every \(m -\)bit pattern has the same chance of appearing as every other \(m -\)bit pattern. Note that for \(m\) = 1, the Serial test is equivalent to the Frequency test of Section 2.1.

\(∇ ψ_{m}^{2} ( \mathrm{obs} )\) and\(∇^{2} ψ_{m}^{2} ( \mathrm{obs} )\): A measure of how well the observed frequencies of \(m -\)bit patterns match the expected frequencies of the \(m -\)bit patterns.

The reference distribution for the test statistic is the \(χ^{2}\) distribution.

(1) Form an augmented sequence \(\varepsilon'\): Extend the sequence by appending the first \(m-1\) bits to the end of the sequence for distinct values of \(n\).

For example, given \(n = 10\) and \(\varepsilon = 0011011101\). If \(m = 3\), then \(\varepsilon' = 001101110100\). If \(m = 2\), then \(\varepsilon' = 00110111010\). If \(m = 1\), then \(\varepsilon'\) = the original sequence \(0011011101\).

(2) Determine the frequency of all possible overlapping \(m\)-bit blocks, all possible overlapping \((m-1)\)-bit blocks and all possible overlapping \((m-2)\)-bit blocks. Let \(v_{i_1\ldots i_m}\) denote the frequency of the \(m\)-bit pattern \(i_1\ldots i_m\); let \(v_{i_1\ldots i_{m-1}}\) denote the frequency of the \((m-1)\)-bit pattern \(i_1\ldots i_{m-1}\); and let \(v_{i_1\ldots i_{m-2}}\) denote the frequency of the \((m-2)\)-bit pattern \(i_1\ldots i_{m-2}\).

For the example in this section, when \(m = 3\), then \((m-1) = 2\), and \((m-2) = 1\). The frequency of all 3-bit blocks is: \(v_{000} = 0\), \(v_{001} = 1\), \(v_{010} = 1\), \(v_{011} = 2\), \(v_{100} = 1\), \(v_{101} = 2\), \(v_{110} = 2\), \(v_{111} = 0\). The frequency of all possible \((m-1)\)-bit blocks is: \(v_{00} = 1\), \(v_{01} = 3\), \(v_{10} = 3\), \(v_{11} = 3\). The frequency of all \((m-2)\)-bit blocks is: \(v_0 = 4\), \(v_1 = 6\).

(3) Compute:

For the example in this section,

(4) Compute:

and

For the example in this section, \(\nabla\psi_m^2=\psi_m^2-\psi_{m-1}^2=\Psi_3^2-\Psi_2^2=2.8-1.2=1.6\)

(5) Compute:

and

For the example in this section,

Since the \(P\text{-value}\) obtained in step 5 of Section 2.11.4 is \(\ge\) 0.01 (P-value1 = 0.808792 and P-value2 = 0.670320), the conclusion is that the sequence is random.

Note that if \(\nabla^2\psi_m^2\) or \(\nabla\psi_m^2\) had been large then non-uniformity of the \(m\)-bit blocks is implied.

Choose \(m\) and \(n\) such that \(m<\lfloor\log_2 n\rfloor-2\).

(input) \(\varepsilon\) = 1,000,000 bits from the binary expansion of \(e\)

(input) \(m = 2\); \(n = 1000000 = 10^6\)

(processing) \(\psi^2_2 = 0.343128;\ \psi^2_1 = 0.003364;\ \psi^2_0 = 0.000000\)

(processing) \(\nabla\psi^2_2 = 0.339764;\ \nabla^2\psi^2_2 = 0.336400\)

(output) \(P\text{-value}_1 = 0.843764;\ P\text{-value}_2 = 0.561915\)

(conclusion) Since both \(P\text{-value}1\) and \(P\text{-value}2\) were \(\ge 0.01\), accept the sequences as random for both tests.

As with the Serial test of Section 2.11, the focus of this test is the frequency of all possible overlapping \(\mathrm{m}\)-bit patterns across the entire sequence. The purpose of the test is to compare the frequency of overlapping blocks of two consecutive/adjacent lengths (\(m\) and \(m+1\)) against the expected result for a random sequence.

\(m\) The length of each block – in this case, the first block length used in the test. \(m+1\) is the second block length used.

\(χ^{2} ( \mathrm{obs} )\): A measure of how well the observed value of ApEn\(( m )\) (see step 6 in Section 2.12.4) matches the expected value.

The reference distribution for the test statistic is the \(χ^{2}\) distribution.

(1) Augment the \(n\)-bit sequence to create \(n\) overlapping \(m\)-bit sequences by appending \(m-1\) bits from the beginning of the sequence to the end of the sequence.

For example, if \(\varepsilon = 0100110101\) and \(m = 3\), then \(n = 10\). Append the 0 and 1 at the beginning of the sequence to the end of the sequence. The sequence to be tested becomes \(010011010101\). (Note: This is done for each value of \(m\).)

(2) A frequency count is made of the \(n\) overlapping blocks (e.g., if a block containing \(\varepsilon_j\) to \(\varepsilon_{j+m-1}\) is examined at time \(j\), then the block containing \(\varepsilon_{j+1}\) to \(\varepsilon_{j+m}\) is examined at time \(j+1\)). Let the count of the possible \(m\)-bit (\((m+1)\)-bit) values be represented as \(C_i^m\), where \(i\) is the \(m\)-bit value.

For the example in this section, the overlapping \(m\)-bit blocks (where \(m = 3\)) become \(010\), \(100\), \(001\), \(011\), \(110\), \(101\), \(010\), \(101\), \(010\), and \(101\). The calculated counts for the \(2^m = 2^3 = 8\) possible \(m\)-bit strings are:

(3) Compute \(C_i^m=\frac{\#i}{n}\) for each value of \(i\).

For example in this section, \(C^3_{000} = 0\), \(C^3_{001} = 0.1\), \(C^3_{010} = 0.3\), \(C^3_{011} = 0.1\), \(C^3_{100} = 0.1\), \(C^3_{101} = 0.3\), \(C^3_{110} = 0.1\), \(C^3_{111} = 0\).

(4) Compute

where \(\pi_i = C^3_j\), and \(j = \log_2 i\).

For the example in this section,

(5) Repeat steps 1-4, replacing \(m\) by \(m+1\).

Step 3: \(C_{0011}^{4} = C_{0100}^{4} = C_{0110}^{4} = C_{1001}^{4} = C_{1101}^{4} = 0.1 , C_{0101}^{4} = 0.2 , C_{1010}^{4} = 0.3 ,\) and all other values are zero.

Step 4:

(6) Compute the test statistic:

where \(\operatorname{ApEn}(m)=\varphi^{(m)}-\varphi^{(m+1)}\).

For the example in this section,

(7) Compute

For the example in this section,

Since the \(P\text{-value}\) obtained in step 7 of Section 2.12.4 is \(\ge\) 0.01 (P-value = 0.261961), the conclusion is that the sequence is random.

Choose \(m\) and \(n\) such that \(m<\lfloor\log_2 n\rfloor-5\).

(input) \(\varepsilon=\) 1100100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000

\(\mathit{mode}\) A switch for applying the test either forward through the input sequence (\(\mathit{mode} = 0\)) or backward through the sequence (\(\mathit{mode} = 1\)).

(1) Form a normalized sequence: The zeros and ones of the input sequence (\(\varepsilon\)) are converted to values \(X_i\) of –1 and +1 using \(X_i = 2\varepsilon_i - 1\).

For example, if \(\varepsilon = 1011010111\), then \(X = 1, (-1), 1, 1, (-1), 1, (-1), 1, 1, 1\).

(2) Compute partial sums \(S_i\) of successively larger subsequences, each starting with \(X_1\) (if \(\mathit{mode} = 0\)) or \(X_n\) (if \(\mathit{mode} = 1\)).

That is, \(S_k=S_{k-1}+X_k\) for mode 0, and \(S_k=S_{k-1}+X_{n-k+1}\) for mode 1.

For the example in this section, when \(\mathit{mode} = 0\) and \(X = 1, (-1), 1, 1, (-1), 1, (-1), 1, 1, 1\), then:

(3) Compute the test statistic \(z = \max_{1 \le k \le n} |S_k|\), where \(\max_{1 \le k \le n} |S_k|\) is the largest of the absolute values of the partial sums \(S_k\).

For the example in this section, the largest value of \(S_k\) is 4, so \(z = 4\).

(4) Compute

where \(\Phi\) is the Standard Normal Cumulative Probability Distribution Function as defined in Section 5.5.3.

Since the \(P\text{-value}\) obtained in step 4 of Section 2.13.4 is \(\ge 0.01\) (\(P\text{-value}\) = 0.411658), the conclusion is that the sequence is random.

It is recommended that each sequence to be tested consist of a minimum of 100 bits (i.e., \(n\ge100\)).

(input) \(\varepsilon=\) 1100100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000

\(n = 100\)

\(\mathit{mode} = 0\) (forward) || \(\mathit{mode} = 1\) (reverse)

(processing) \(z = 1.6\) (forward) || \(z = 1.9\) (reverse)

\(χ^{2} ( \mathrm{obs} )\): For a given state \(x ,\) a measure of how well the observed number of state visits within a cycle match the expected number of state visits within a cycle, under an assumption of randomness.

The reference distribution for the test statistic is the \(χ^{2}\) distribution.

(1) Form a normalized (-1, +1) sequence \(X\): The zeros and ones of the input sequence (\(\varepsilon\)) are changed to values of –1 and +1 via \(X_i = 2\varepsilon_i - 1\).

For example, if \(\varepsilon = 0110110101\), then \(n = 10\) and \(X = -1, 1, 1, -1, 1, 1, -1, 1, -1, 1\).

(2) Compute the partial sums \(S_i\) of successively larger subsequences, each starting with \(X_1\). Form the set \(S = \{S_i\}\).

For the example in this section,

(4) Let \(J\) = the total number of zero crossings in \(S'\), where a zero crossing is a value of zero in \(S'\) that occurs after the starting zero. \(J\) is also the number of cycles in \(S'\), where a cycle of \(S'\) is a subsequence of \(S'\) consisting of an occurrence of zero, followed by no-zero values, and ending with another zero. The ending zero in one cycle may be the beginning zero in another cycle. The number of cycles in \(S'\) is the number of zero crossings. If \(J < 500\), discontinue the test⁶.

For the example in this section, if \(S' = \{0, -1, 0\ 1, 0, 1, 2, 1, 2, 1, 2, 0\}\), then \(J = 3\) (there are zeros in positions 3, 5 and 12 of \(S'\)). The zero crossings are easily observed in the above plot. Since \(J = 3\), there are 3 cycles, consisting of \(\{0, -1, 0\}\), \(\{0, 1, 0\}\) and \(\{0, 1, 2, 1, 2, 1, 2, 0\}\).

(5) For each cycle and for each non-zero state value \(x\) having values \(– 4 \le x \le - 1\) and \(1 \le x \le 4 ,\) compute the frequency of each \(x\) within each cycle\(.\)

⁶ \(J\) times the minimum of the probabilities found in the table in Section 3.14 must be \(\ge \) 5 in order to satisfy the empirical rule for Chi-square computations.

(6) For each of the eight states of \(x\), compute \(\nu_k(x)\) = the total number of cycles in which state \(x\) occurs exactly \(k\) times among all cycles, for \(k=0,1,\ldots,5\) (for \(k=5\), all frequencies \(\ge5\) are stored in \(\nu_5(x)\)). Note that

• \(\nu_0(-1)=2\) (the –1 state occurs exactly 0 times in two cycles),
  \(\nu_1(-1)=1\) (the –1 state occurs only once in 1 cycle), and
  \(\nu_2(-1)=\nu_3(-1)=\nu_4(-1)=\nu_5(-1)=0\) (the –1 state occurs exactly \(\{2,3,4,\ge5\}\) times in 0 cycles).
• \(\nu_0(1)=1\) (the 1 state occurs exactly 0 times in 1 cycle),
  \(\nu_1(1)=1\) (the 1 state occurs only once in 1 cycle),
  \(\nu_3(1)=1\) (the 1 state occurs exactly three times in 1 cycle), and
  \(\nu_2(1)=\nu_4(1)=\nu_5(1)=0\) (the 1 state occurs exactly \(\{2,4,\ge5\}\) times in 0 cycles).
• \(\nu_0(2)=2\) (the 2 state occurs exactly 0 times in 2 cycles),
  \(\nu_3(2)=1\) (the 2 state occurs exactly three times in 1 cycle), and
  \(\nu_1(2)=\nu_2(2)=\nu_4(2)=\nu_5(2)=0\) (the 1 state occurs exactly \(\{1,2,4,\ge5\}\) times in 0 cycles).
• \(\nu_0(-4)=3\) (the -4 state occurs exactly 0 times in 3 cycles), and
  \(\nu_1(-4)=\nu_2(-4)=\nu_3(-4)=\nu_4(-4)=\nu_5(-4)=0\) (the -4 state occurs exactly \(\{1,2,3,4,\ge5\}\) times in 0 cycles).

(7) For each of the eight states of \(x\), compute the test statistic

where \(\pi_k(x)\) is the probability that the state \(x\) occurs \(k\) times in a random distribution (see Section 3.14 for a table of \(\pi_k\) values). The values for \(\pi_k(x)\) and their method of calculation are provided in Section 3.14. Note that eight \(\chi^2\) statistics will be produced (i.e., for \(x = -4, -3, -2, -1, 1, 2, 3, 4\)).

For example in this section, when \(x=1\),

(8) For each state of \(x\), compute

Eight \(P\text{-value}s\) will be produced.

For the example when \(x=1\),

Since the \(P\text{-value}\) obtained in step 8 of Section 2.14.4 is \(\ge 0.01\) (\(P\text{-value}\) = 0.502529), the conclusion is that the sequence is random.

Note that if \(\chi^2(\mathit{obs})\) were too large, then the sequence would have displayed a deviation from the theoretical distribution for a given state across all cycles.

It is recommended that each sequence to be tested consist of a minimum of 1,000,000 bits (i.e., \(n \ge 10^{6}\)).

(input) \(ε =\) "the binary expansion of \(e\) up to 1,000,000 bits"

(input) \(n = 1000000 = 10^{6}\)

(processing) \(J = 1490\)

(conclusion) For seven of the states of \(x\), the \(P\text{-value}\) is \(\ge0.01\), and the conclusion would be that the sequence was random. However, for one state of \(x\) (\(x=-1\)), the \(P\text{-value}\) is \(<0.01\), so the conclusion would be that the sequence is non-random. When contradictions arise, further sequences should be examined to determine whether or not this behavior is typical of the generator.