# Fast Software Implementation of Serial Test and Approximate Entropy Test of Binary Sequence

Authors: Xian-wei Yang; Xue-qiu Zhan; Hong-juan Kang; Ying Luo
Journal: Security and Communication Networks
 (2021)

---

## Abstract

In many cryptographic applications, random numbers and pseudorandom numbers are required. Many cryptographic protocols require using random or pseudorandom numbers at various points, e.g., for auxiliary data in digital signatures or challenges in authentication protocols. In NIST SP800-22, the focus is on the need for randomness for encryption purposes and describes how to apply a set of statistical randomness tests. These tests can be used to evaluate the data generated by cryptographic algorithms. This paper will study the fast software implementation of the serial test and the approximate entropy test and propose two types of fast implementations of these tests. The first method is to follow the basic steps of these tests and replace bit operations with byte operations. Through this method, compared with the implementation of Fast NIST STS, the efficiency of the serial test and approximate entropy test is increased by 2.164 and 2.100 times, respectively. The second method is based on the first method, combining the statistical characteristics of subsequences of different lengths and further combining the two detections with different detection parameters. In this way, compared to the individual implementation of these tests, the efficiency has been significantly improved. Compared with the implementation of Fast NIST STS, the efficiency of this paper is increased by 4.078 times.


---

## Body

## 1. Introduction

In cryptography, random numbers and pseudorandom numbers are widely used in applications. For example, use a randomly generated key in a cryptographic system. There are also random or pseudorandom numbers required to be used at various points in cryptographic protocols, for example, for auxiliary data in digital signatures or challenges in authentication protocols.The random bit sequence can be explained by the result of an unbiased “fair” coin flip, with the sides of the coin marked as “0” and “1.” The probability that each flip produces a “0” or “1” is 1/2, and the results of each coin toss are independent of each other. Unbiased, fair coins are perfect random bitstream generators because 0 and 1 values will be randomly distributed, and all elements in the sequence are generated independently of each other. The value of any element in the sequence is unpredictable and has nothing to do with all previously generated elements.The SP 800-22 [1] issued by the National Institute of Standards and Technology (NIST) discusses the randomness test of random number and pseudorandom number generators. These tests can be applied to fields such as cryptography, modeling, and simulation. In NIST SP800-22, the focus is on the need for randomness for encryption purposes and describes applying a set of statistical randomness tests. Germany released the BSI AIS 30 specification [2]. In 2009, the National Cryptography Administration (NCA) of China issued a randomness test specification [3]. In addition, research on random sequences is in full swing, and a large number of new statistical tests have been proposed [4]. There are two basic types of random sequence generators: random number generator (RNG) and pseudorandom number generator (PRNG) [5]. In cryptographic applications, both generators produce zero and a stream divided into subsequences or blocks.These tests can be used to evaluate the data stream generated by the cryptographic algorithm, thereby providing useful reference data for the theoretical analysis of the algorithm [6–8]. This approach can reduce the workload of theoretical analysis and detect security risks that cannot be found by other analytical methods. For example, in the competition of AES [9, 10], randomness detection is used to evaluate candidate cryptographic algorithms [11]. ZUC [12, 13] has officially become a cryptographic algorithm of LTE and executed many randomness tests. Parameter of these detections can be recommended or be adjusted [14–16].Some researchers study the rapid implementation of all NIST STS tests and achieved interesting speedups in most of the tests [17]. Q-value is introduced, and the distribution of Q-value is closer to a uniform distribution than P value, which can reduce the false detection rate [18]. When the runs distribution test is applied on some well-known good deterministic random bit generators (DRBGs), the test results show apparent bias from randomness [19]. A new DFT test method for the long sequence is proposed, and this DFT test reconstructs the statistics to follow the chi-square distribution [20].In this paper, we study the fast implementation of the serial test and the approximate entropy test and propose two types of fast implementation of these tests. The first fast implementation method is to follow the basic steps according to these tests. In this implementation, the efficiency of the serial test and the approximate entropy test is increased by 2.164 and 2.100 times, respectively, compared with the basic implementation. The second one is to merge these tests. Relative to the individual implementation of these tests, the efficiency has been improved in this implementation. Compared with the basic implementation, the best efficiency of this method is increased by 4.078 times, and the effect is significant.This paper is organized as follows. Section2 presents an introduction to these statistical tests. Section 3 discusses the serial test, the approximate entropy test, and the basic implementation. Sections 4 and 5 present two types of fast implementation of these tests. Section 6 presents the software implementation results of these methods. Section 7 concludes the paper.


## 2. Introduction of Statistical Tests

By performing various statistical tests on the sequences, it is possible to compare and evaluate sequences with random sequences. Both characterization and description of the properties of random sequences can be done through probability. There are countless possible statistical tests to assess the presence or absence of a pattern, which indicates that the sequence is nonrandom. These test methods are designed for the different characteristics of the sequence, mainly based on the different focus of the sequence characteristics, and there are also some test methods that have no significant differences in the principles. Therefore when choosing a randomness test method, it is necessary to consider all aspects of the random characteristics of the test sequence, but also to take into account the efficiency of the test. In addition, one must be careful when interpreting the results of statistical tests to avoid erroneous conclusions about specific generators [21].The randomness of the test sequence is essential to test whether it is truly random or the gap between it and true randomness. Randomness testing usually uses hypothesis testing. Hypothesis testing is to propose certain assumptions about the population in order to infer certain properties of the population when the population distribution is unknown or only its form is known. However, its parameters are not known, and then, make judgments on the proposed hypotheses based on the sample. Random hypothesis testing means that a certain aspect of a truly random sequence conforms to a specific distribution. If the sequence to be tested is random, then the sequence to be tested should also conform to this specific distribution in this respect. Take a certain statistical valueV of a random sequence that conforms to the chi-square distribution with n degrees of freedom as an example. Null hypothesis (null hypothesis) H0: the sequence is random if the statistical value V of the sequence to be tested obeys the χ2(n) distribution. Alternative hypothesis Hα: the sequence is not random if the statistical value V of the sequence to be tested does not obey the χ2(n) distribution. The opposite of this null hypothesis is the alternative hypothesis, which is that the sequence is not random. By testing each application, a decision or conclusion is derived. Based on the generated sequence, determine whether to accept the null hypothesis H0. Under the original hypothesis, the theoretical reference distribution of the statistical data is determined by mathematical methods, and the critical value is determined. During the test, the statistical value of the tested sequence is calculated and compared with the critical value. If the test statistic value does not exceed the critical value, the null hypothesis H0 of randomness is accepted. Otherwise, accept the alternative hypothesis Ha.There are two possible outcomes of statistical hypothesis testing, namely, acceptingH0 or accepting Ha.Two types of errors may occur with this method. First, if the data is random, then we conclude that the data is nonrandom. This conclusion is called a type I error. Second, if the data is nonrandom, then we conclude that the data is random. This conclusion is called a type II error. The probability of a type I error is called the significance level of the test, and this probability is usually denoted asα. Typically, α is selected in the range of [0.001, 0.01], and the value of α in cryptography is about 0.01. In the test, α is the probability that when the test shows that the sequence is truly random, it is not a random sequence. The probability of a type II error is usually denoted as β. In the test, β is the probability that the test will indicate that the sequence is random when it is not. β is not a fixed value, which is different from α. There are many ways to select data, they can be nonrandom, and each different way can produce different β. One of the main goals of the test is to minimize the possibility of making type II errors. Table 1 below correlates the true state of the data with the test conclusion.Table 1
Conclusions of statistical hypothesis testing.
True situationAcceptH0AcceptHaData is randomNo errorType I errorData is not randomType II errorNo errorIn order to reflect the strength of the evidence against the null hypothesis, theP value can be calculated using test statistics. In all tests, the P value is the probability that the sequence generated by the perfect random number generator has less randomness than the sequence to be tested. When the sequence seems to have perfect randomness, the P value is equal to 1, and when the sequence seems to be completely nonrandom, the P value is equal to 0. When the P value ≥α, the null hypothesis H0 is accepted, which means that the sequence appears to be random. When the P value <α, the alternative hypothesis Ha is accepted, which means that the sequence appears nonrandom.In the test, theP value can be calculated with the test statistic. The P value represents the probability that the sequence generated by the perfect random number generator is less random than the sequence being tested. When the P value is 1, it means that the sequence seems to have perfect randomness, and when the P value is 0, it means that the sequence seems to be completely nonrandom. When P ≥α, it means that the null hypothesis is credible, which reflects that the sequence seems to be random. When P <α, it means that the null hypothesis is unreliable, which reflects that the sequence seems to be nonrandom. The P value is the strength of evidence for accepting the null hypothesis.The NIST SP800-22 is a statistical test suite consisting of 16 tests, and the test suite of NCA consists of 15 tests. Table2 lists all of the tests. Serial test and approximate entropy test are the tests of the two test suites.Table 2
The tests of NIST SP800-22 and NCA randomness test specification.
ItemsNISTNCAMonobit test√√Frequency test within a block√√Poker test×√Serial test√√Runs test√√Runs distribution test×√Test for the longest run of ones in a block√√Binary derivative test×√Autocorrelation test×√Binary matrix rank test√√Cumulative sums test√√Approximate entropy test√√Linear complexity test√√Maurer’s universal statistical test√√Discrete Fourier transform test√√Nonoverlapping template matching test√×Overlapping template matching test√×Lempel–Ziv compression test√×Random excursions test√×Random excursions variant test√×


## 3. Serial Test and Approximate Entropy Test

### 3.1. Definitions and Symbols

Table3 lists all of the symbols and their meanings used in this paper.Table 3
Symbols.
SymbolsMeaningεThe original input string of zero and one bits to be testedεiTheith bit in the original sequence εnThe number of bits in the stream being testedmThe number of bits in a substring (block) being testedvi1,vi2,…,vitThe frequency of thet-bit pattern i1i2…it∇Ψ2mobsA measure of how well the observed values match the expected value∇2Ψ2mobsA measure of how well the observed values match the expected valueH0The null hypothesis; i.e., the statement that the sequence is randomIgamcThe incomplete gamma functionlogxThe natural logarithm ofx: logx=logex=lnxΑThe significance level&The and operator|The or operatorThe establishment of the incomplete gamma function is based on the approximate formula [22], which can be approximated by continuous fraction expansion or series expansion according to the values of its parameters a and x.Gamma function and incomplete gamma function are defined as(1)Γx=∫0∞e−ttx−1dt,x>0,Pa,x=γa,xΓa=1Γa∫0xe−tta−1dt,Qa,x=1−Pa,x=Γa,xΓa=1Γa∫x∞e−tta−1dt.


### 3.2. Serial Test

This section describes the serial tests, such as the test description, the technical details, the testing strategy, and the purpose of this test.The frequency of all possiblem-bit subsequences in the entire sequence is the focus of the serial test. From the results of this test, it can be determined whether the frequency of occurrence of the 2mm-bit subsequences of the random sequence is roughly in line with expectations. The probability of all subsequent m-bit in the random sequence is the same, and when m is 1, the serial test has the same utility as the frequency test.For different values ofn, the sequence is expanded by appending the first m-1 bits to the end of the sequence to form an expanded sequence ε′=ε1,ε2,…,εn,ε1,…,εm−1. The serial test is based on testing the uniformity of distributions of subsequences of given lengths in the circularised string ε′. Set(2)ψm2=2mn∑i1⋯imvi1⋯im−n2m2=2mn∑i1⋯imvi1⋯im2−n.Here,ψ02=ψ−12=0. Thus, ψm2 is a χ2 type of statistic, but it is a common mistake to assume that ψm2 has the χ2 distribution. The corresponding generalized serial statistics for the testing of randomness are ∇ψm2 and ∇2ψm2:(3)∇ψm2=ψm2−ψm−12,∇2ψm2=ψm2−2ψm−12+ψm−22.Then,∇ψm2 and ∇ψm−12 have the χ2 distribution with 2m−1 and 2m−2 degrees of freedom, respectively. Thus, for small values of m, m≤⌊log2n⌋−2, one can find the corresponding 2mP values from the standard formulas:(4)P−value1=igamc2m−2,∇ψm22,P−value2=igamc2m−3,∇∇ψm222.Denote byvi1vi2,…,vim the frequency of m-bit pattern i1i2…im, vi1vi2…vim−1 the frequency of m−1-bit pattern i1i2…im−1, and vi1vi2…vim−2 the frequency of m−2-bit pattern i1i2…im−2, respectively.The steps of the serial test (Algorithm1) are as follows.Algorithm 1: Serial test.
Input: a binary sequence ε=ε1,ε1,…,εn of length n. m is the bit length of subsequence.Output: pass or not.Step 1: extend the sequence by appending the firstm−1 bits to the end of the sequence ε′=ε1,ε2,…,εn,ε1,…,εm−1Step 2: determinevi1vi2…vim, vi1vi2…vim−1, and vi1vi2…vim−2 and the frequency of all possible m-bit, m−1-bit, and m−2-bit subsequence, respectively.Step 3: computeψm2, ψm−12, and ψm−22. ψm2=2m/n∑i1⋯imvi1⋯im2−n. ψm−12=2m−1/n∑i1⋯imvi1⋯im2−nψm−22=2m−2/n∑i1⋯imvi1⋯im2−n.Step 4: compute∇ψm2 and ∇2ψm2. ∇ψm2=ψm2−ψm−12∇2ψm2=ψm2−2ψm−12+ψm−22.Step 5: computeP values. P−value1=igamc2m−2,∇ψm2/2P−value1=igamc2m−3,∇ψm2/2.Step 6: ifP−value1≥α and P−value2≥α, the sequence passes the test. Otherwise, return not pass.Note that choosem such that m≤⌊log2n⌋−2. The bit length of subsequence m and the sample length n are proposed m=2and5 and n=1000000 in specification [3], respectively.


### 3.3. Approximate Entropy Test

The frequency of all possible overlappingm-bit patterns in the sequence is the focus of the approximate entropy test. Through this test, the frequency of two adjacent lengths’ (m and m + 1) subsequences can be compared with the expected result.The repetitive pattern in the string is a feature of approximate entropy. Set(5)Cim=vi1i2⋯imn,Φm=∑i=12mCimlnCim.The approximate entropyApEnm, m≥1, is defined as(6)ApEnm=Φm−Φm−1,with ApEn0=−Φ1.ApEnm measures the logarithmic frequency with which blocks of length m that are close together. Thus, a smaller ApEnm value indicates strong regularity in the sequence, while larger values indicate irregularities in the sequence.For a fixed block lengthm, one should expect that, in long random strings, ApEnm∼ln2. The limited distribution is consistent with the distribution of a random variable with 2m degrees of freedom. This fact provides the basis for statistical testing. Thus, with χ2obs=nln2−ApEnm), the reported P value is(7)P−value=igamc2m−1,χ2obs2.The steps of the approximate entropy (Algorithm2) test are as follows.Algorithm 2: Approximate entropy test.
Input: a binary sequence ε=ε1,ε1,…,εn of length n. m is the bit length of subsequenceOutput: pass or notStep 1: extend the sequence by appending the firstm-1 bits to the end of the sequence ε′=ε1,ε2,⋯,εn,ε1,⋯,εm−1.Step 2: determinevi1vi2…vim the frequency of all possible m-bit subsequences.Step 3: computeCim, for each value of i. Cim=vi1i2…im/n.Step 4: computeΦmΦm=∑i=12mCimlnCim.Step 5: repeat Steps 1–4, replacingm by m+1.Step 6: computeχ2=nln2−ApEnm with ApEnm=Φm−Φm−1.Step 7: computeP values. P−value=igamc2m−1,χ2/2.Step 8: ifP−value≥α, the sequence passes the test. Otherwise, return not pass.Note that choosem such that m≤⌊log2n⌋−2. The bit length of subsequence m and the sample length n are proposed m=2and5 and n=1000000 in specification [3], respectively.The second step of the serial test and the approximate entropy test is to determine the frequency of all possiblem-bit subsequences of ε′=ε1,ε2,…,εn,ε1,…,εm−1. Algorithm 3 is a basic implementation of Step 2 based on bits’ operations.Algorithm 3: Determine the frequency of all possible m-bit subsequence (bit string).
Input: A extended binary sequence ε′=ε1,ε2,…,εn,ε1,…,εm−1 of length n+m−1. m is the bit length of subsequence.Output:vw, for each value of w=i1i2⋯im.Step 1:vi1i2⋯im=0, for each value of i.Step 2: fori=1,2,…,n, do: 2.1 x=0. 2.2 for j=0,1,…,m−1, do: x=2x+εi+j. 2.3 vx=vx+1.Step 3: returnvw, for each value of w=i1i2…im.We note by LOAD the data loading operation. Left and right shifts will be denoted SHIFT. By CMP means the compare operation.The computational complexity of Algorithm3 is mn LOAD, 2mn ADD, mn SHIFT, and mn OR. The computational complexity of Algorithm 4 is n/8 LOAD, nm+7/8 ADD, n SUB, nm+7/8 SHIFT, n AND, nm+7/8 OR, and E′=E1,E2,…,En/8,E1 CMP.Algorithm 4: Determine the frequency of all possible m-bit subsequence (octet string).
Input: a extended octet string E′=E1,E2,…,En/8,E1 of octet length n/8+1. m is the bit length of subsequence.Output:vw, for each value of w=i1i2…im.Step 1:vi1i2…im=0, for each value of i. M=2m−1.Step 2: fori=1,2,…,n/8, do: 2.1 x=0. 2.2 for j=0,1,…,m−1, do. k=8−j−m if k≥0, then: x=Ei≫k&M if k<0, then: x=Ei≪−k|Ei+1≪8+k&Mvx=vx+1Step 3: returnvw, for each value of w=i1i2…im.


## 3.1. Definitions and Symbols

Table3 lists all of the symbols and their meanings used in this paper.Table 3
Symbols.
SymbolsMeaningεThe original input string of zero and one bits to be testedεiTheith bit in the original sequence εnThe number of bits in the stream being testedmThe number of bits in a substring (block) being testedvi1,vi2,…,vitThe frequency of thet-bit pattern i1i2…it∇Ψ2mobsA measure of how well the observed values match the expected value∇2Ψ2mobsA measure of how well the observed values match the expected valueH0The null hypothesis; i.e., the statement that the sequence is randomIgamcThe incomplete gamma functionlogxThe natural logarithm ofx: logx=logex=lnxΑThe significance level&The and operator|The or operatorThe establishment of the incomplete gamma function is based on the approximate formula [22], which can be approximated by continuous fraction expansion or series expansion according to the values of its parameters a and x.Gamma function and incomplete gamma function are defined as(1)Γx=∫0∞e−ttx−1dt,x>0,Pa,x=γa,xΓa=1Γa∫0xe−tta−1dt,Qa,x=1−Pa,x=Γa,xΓa=1Γa∫x∞e−tta−1dt.


## 3.2. Serial Test

This section describes the serial tests, such as the test description, the technical details, the testing strategy, and the purpose of this test.The frequency of all possiblem-bit subsequences in the entire sequence is the focus of the serial test. From the results of this test, it can be determined whether the frequency of occurrence of the 2mm-bit subsequences of the random sequence is roughly in line with expectations. The probability of all subsequent m-bit in the random sequence is the same, and when m is 1, the serial test has the same utility as the frequency test.For different values ofn, the sequence is expanded by appending the first m-1 bits to the end of the sequence to form an expanded sequence ε′=ε1,ε2,…,εn,ε1,…,εm−1. The serial test is based on testing the uniformity of distributions of subsequences of given lengths in the circularised string ε′. Set(2)ψm2=2mn∑i1⋯imvi1⋯im−n2m2=2mn∑i1⋯imvi1⋯im2−n.Here,ψ02=ψ−12=0. Thus, ψm2 is a χ2 type of statistic, but it is a common mistake to assume that ψm2 has the χ2 distribution. The corresponding generalized serial statistics for the testing of randomness are ∇ψm2 and ∇2ψm2:(3)∇ψm2=ψm2−ψm−12,∇2ψm2=ψm2−2ψm−12+ψm−22.Then,∇ψm2 and ∇ψm−12 have the χ2 distribution with 2m−1 and 2m−2 degrees of freedom, respectively. Thus, for small values of m, m≤⌊log2n⌋−2, one can find the corresponding 2mP values from the standard formulas:(4)P−value1=igamc2m−2,∇ψm22,P−value2=igamc2m−3,∇∇ψm222.Denote byvi1vi2,…,vim the frequency of m-bit pattern i1i2…im, vi1vi2…vim−1 the frequency of m−1-bit pattern i1i2…im−1, and vi1vi2…vim−2 the frequency of m−2-bit pattern i1i2…im−2, respectively.The steps of the serial test (Algorithm1) are as follows.Algorithm 1: Serial test.
Input: a binary sequence ε=ε1,ε1,…,εn of length n. m is the bit length of subsequence.Output: pass or not.Step 1: extend the sequence by appending the firstm−1 bits to the end of the sequence ε′=ε1,ε2,…,εn,ε1,…,εm−1Step 2: determinevi1vi2…vim, vi1vi2…vim−1, and vi1vi2…vim−2 and the frequency of all possible m-bit, m−1-bit, and m−2-bit subsequence, respectively.Step 3: computeψm2, ψm−12, and ψm−22. ψm2=2m/n∑i1⋯imvi1⋯im2−n. ψm−12=2m−1/n∑i1⋯imvi1⋯im2−nψm−22=2m−2/n∑i1⋯imvi1⋯im2−n.Step 4: compute∇ψm2 and ∇2ψm2. ∇ψm2=ψm2−ψm−12∇2ψm2=ψm2−2ψm−12+ψm−22.Step 5: computeP values. P−value1=igamc2m−2,∇ψm2/2P−value1=igamc2m−3,∇ψm2/2.Step 6: ifP−value1≥α and P−value2≥α, the sequence passes the test. Otherwise, return not pass.Note that choosem such that m≤⌊log2n⌋−2. The bit length of subsequence m and the sample length n are proposed m=2and5 and n=1000000 in specification [3], respectively.


## 3.3. Approximate Entropy Test

The frequency of all possible overlappingm-bit patterns in the sequence is the focus of the approximate entropy test. Through this test, the frequency of two adjacent lengths’ (m and m + 1) subsequences can be compared with the expected result.The repetitive pattern in the string is a feature of approximate entropy. Set(5)Cim=vi1i2⋯imn,Φm=∑i=12mCimlnCim.The approximate entropyApEnm, m≥1, is defined as(6)ApEnm=Φm−Φm−1,with ApEn0=−Φ1.ApEnm measures the logarithmic frequency with which blocks of length m that are close together. Thus, a smaller ApEnm value indicates strong regularity in the sequence, while larger values indicate irregularities in the sequence.For a fixed block lengthm, one should expect that, in long random strings, ApEnm∼ln2. The limited distribution is consistent with the distribution of a random variable with 2m degrees of freedom. This fact provides the basis for statistical testing. Thus, with χ2obs=nln2−ApEnm), the reported P value is(7)P−value=igamc2m−1,χ2obs2.The steps of the approximate entropy (Algorithm2) test are as follows.Algorithm 2: Approximate entropy test.
Input: a binary sequence ε=ε1,ε1,…,εn of length n. m is the bit length of subsequenceOutput: pass or notStep 1: extend the sequence by appending the firstm-1 bits to the end of the sequence ε′=ε1,ε2,⋯,εn,ε1,⋯,εm−1.Step 2: determinevi1vi2…vim the frequency of all possible m-bit subsequences.Step 3: computeCim, for each value of i. Cim=vi1i2…im/n.Step 4: computeΦmΦm=∑i=12mCimlnCim.Step 5: repeat Steps 1–4, replacingm by m+1.Step 6: computeχ2=nln2−ApEnm with ApEnm=Φm−Φm−1.Step 7: computeP values. P−value=igamc2m−1,χ2/2.Step 8: ifP−value≥α, the sequence passes the test. Otherwise, return not pass.Note that choosem such that m≤⌊log2n⌋−2. The bit length of subsequence m and the sample length n are proposed m=2and5 and n=1000000 in specification [3], respectively.The second step of the serial test and the approximate entropy test is to determine the frequency of all possiblem-bit subsequences of ε′=ε1,ε2,…,εn,ε1,…,εm−1. Algorithm 3 is a basic implementation of Step 2 based on bits’ operations.Algorithm 3: Determine the frequency of all possible m-bit subsequence (bit string).
Input: A extended binary sequence ε′=ε1,ε2,…,εn,ε1,…,εm−1 of length n+m−1. m is the bit length of subsequence.Output:vw, for each value of w=i1i2⋯im.Step 1:vi1i2⋯im=0, for each value of i.Step 2: fori=1,2,…,n, do: 2.1 x=0. 2.2 for j=0,1,…,m−1, do: x=2x+εi+j. 2.3 vx=vx+1.Step 3: returnvw, for each value of w=i1i2…im.We note by LOAD the data loading operation. Left and right shifts will be denoted SHIFT. By CMP means the compare operation.The computational complexity of Algorithm3 is mn LOAD, 2mn ADD, mn SHIFT, and mn OR. The computational complexity of Algorithm 4 is n/8 LOAD, nm+7/8 ADD, n SUB, nm+7/8 SHIFT, n AND, nm+7/8 OR, and E′=E1,E2,…,En/8,E1 CMP.Algorithm 4: Determine the frequency of all possible m-bit subsequence (octet string).
Input: a extended octet string E′=E1,E2,…,En/8,E1 of octet length n/8+1. m is the bit length of subsequence.Output:vw, for each value of w=i1i2…im.Step 1:vi1i2…im=0, for each value of i. M=2m−1.Step 2: fori=1,2,…,n/8, do: 2.1 x=0. 2.2 for j=0,1,…,m−1, do. k=8−j−m if k≥0, then: x=Ei≫k&M if k<0, then: x=Ei≪−k|Ei+1≪8+k&Mvx=vx+1Step 3: returnvw, for each value of w=i1i2…im.


## 4. Fast Implementation

### 4.1. Hotspots

After determining the key parts of the program, we can start to optimize the code. During the running of the program, there are two situations for time allocation. In some programs, more than 99% of the time is used for inner loop calculations. In other programs, 99% of the time is used to read and write data, and less than 1% of the time is used to calculate the data. It is important to optimize these parts of the code instead of the parts of the code that spend a small amount of time. Optimizing the less critical parts of the code not only wastes time but also makes the code more difficult to maintain.We can use the profiler in the compiler to profile how much time each function costs. It can also be done with third-party analyzers, such as AQtime, Intel VTune, and AMD Code Analyst.Due to the short time interval, time measurement requires very high resolution. Users can use the QueryPerformanceCounter or GetTickCount functions for millisecond resolution in Windows. Use the time stamp counter in the CPU to get a higher resolution RDTSC. This instruction counts at the CPU clock frequency.We need to identify the most time-consuming hotspots of the basic implementation of the serial test and the approximate entropy test. The Hotspots analysis helps understand these tests and identify steps that take a long time to execute (hotspots). Intel VTune amplifier identifies that Step 2 of the serial test is the most time-consuming hotspot of this test. In the serial test, this step determinesvi1vi2…vim, vi1vi2…vim−1, and vi1vi2…vim−2 and the frequency of all possible m-bit, m−1-bit, and m−2-bit subsequence, respectively. Then, the Intel VTune amplifier identifies that Step 2 of the approximate entropy test is the most time-consuming hotspots of this test. This step determines vi1vi2…vim the frequency of all possible m-bit subsequences.All the operations of Algorithm3 are based on bit operations, which seriously reduce the performance of these tests.In practice, a binary sequence is in the form of an octet string. This octet string needs to be converted into a bit string, and then, the bit string is sent into Algorithm3 to determine the frequency of all possible m-bit subsequences.Algorithm3 is replaced by bit operations with byte operations, and the performance will be significantly improved.


### 4.2. Fast Implementation Based on Octet Operation

In practice, a binary sequence is almost in the form of the octet string, so we assume thatn is divided by 8|n The random byte is a byte sequence formed by combining random bits by bit-by-bit splicing.DenoteE=E1,E2,…,En/8 the octet string of the binary sequence ε=ε1,ε1,…,εn of length n, with Ei=ε8i−7,ε8i−6…,ε8i, i=1,2,…,n/8. Because the value of the parameter m is less than 8, the extended octets are not more than one octet (8 bits). Extend the sequence by appending the first octet to the end of the octet string and E′=E1,E2,…,En/8,E1 to form the augmented octet string E′. Algorithm 4 determines the frequency based on multiple bits’ operations.


### 4.3. Analysis of Computational Complexity

This section analyses and compares the number of arithmetic operations of the above algorithms. Because Step 2 is the most time-consuming, so the main task is to analyze the computational complexity of Algorithm3 based on bit string and bit operations and Algorithm 4 based on octet string and multibit operations.Unroll Step 2.2 of Algorithm4, which can reduce many operations. The CMP operation is clear, and the left and right shift number does not need to be calculated. The computational complexity is reduced to n/8 LOAD, n ADD, nm+7/8 SHIFT, n AND, and nm+7/8 OR.The efficiency of the loop depends on the microprocessor’s ability to predict the control branch of the loop. A loop with a small and fixed repeat count and no branches inside can be predicted perfectly. It is best to avoid loop unrolling on processors with microoperation cache because it is important to save the use of microoperation cache. The unrolled loop takes up more space in the code cache or microoperation cache. If there are specific advantages to be gained, such as eliminating the if branch, the programmer should manually unroll a loop.Loop unrolling of Algorithm4 has many advantages. Then, if the branch is eliminated, the CMP operation is removed, and the left and right shift numbers are cleared.The computational complexity of Algorithm3 (based on bit string) and Algorithm 4 (based on octet string) is provided in Table 4.Table 4
The computational complexity of Algorithms3 and 4.
Execution numberOperationsAlgorithm3Algorithm3LOADmnn/8ADD2mnnSHIFTmnnm+7/8AND0nORmnnm−1/8For example, when the value ofm is 3, the execution numbers of Algorithms 3 and 4 are 15n and 3.625n, respectively.The serial test determines the frequency of all possiblej-bit patterns, with j=1,2,3,4,and5. In Algorithm 3 (based on bit string), the sum of operations of the serial test (with j=1,2,3,4,and5) is(8)∑m=155mn=75n.In Algorithm4 (based on octet string), the sum of operations of the serial test (with j=1,2,3,4,and5) is(9)∑m=15n2m+238=18.125n.In contrast to the number of arithmetic operations of the above two algorithms, it is shown that Algorithm4 based on the octet string is superior to Algorithm 3 based on bit string, in the serial test. Table 5 shows the number of arithmetic operations of the above two algorithms.Table 5
The number of operations of Algorithms3 and 4 in the serial test.
OperationsExecution number of serial testCalling algorithm3Calling algorithm4LOAD15n0.625nADD30n5nSHIFT15n6.25nAND0.5nOR15n1.25nThe approximate entropy test determines the frequency of all possiblej-bit patterns, with j=2,3,5,and6. In Algorithm 3 (based on bit string), the sum of operations of the approximate entropy test is(10)∑m=2,3,5,65mn=80n.In Algorithm4 (based on octet string), the sum of operations of the approximate entropy test is(11)∑m=2,3,5,6n2m+238=15.5n.In contrast to the number of arithmetic operations of the above two algorithms, it is shown that Algorithm4 based on octet string is superior to Algorithm 3 based on bit string, in the approximate entropy test. Table 6 shows the number of arithmetic operations of the above two algorithms.Table 6
The number of operations of Algorithms3 and 4 in the approximate entropy test.
OperationsExecution number of approximate entropy testCalling algorithm3Calling algorithm4LOAD16n0.5nADD32n4nSHIFT16n5.5nAND04nOR16n1.5nHowever, different instructions cost different cycles. Integer operations are usually very fast. On most microprocessors, most simple integer operations (such as addition, subtraction, comparison, bit operations, and shift operations) only take one clock cycle. Multiplication and division require longer clock cycles. Usually, integer multiplication requires 3-4 clock cycles, and integer division requires 40–80 clock cycles. In addition, it may take longer to access data from RAM compared to the time required to perform calculations on the data. If it is cached, it only takes 2-3 clock cycles to read or write the variables in the memory, while if it is not cached, it takes hundreds of clock cycles [23]. So, the exact time consuming of these algorithms needs to do many different experiments.


## 4.1. Hotspots

After determining the key parts of the program, we can start to optimize the code. During the running of the program, there are two situations for time allocation. In some programs, more than 99% of the time is used for inner loop calculations. In other programs, 99% of the time is used to read and write data, and less than 1% of the time is used to calculate the data. It is important to optimize these parts of the code instead of the parts of the code that spend a small amount of time. Optimizing the less critical parts of the code not only wastes time but also makes the code more difficult to maintain.We can use the profiler in the compiler to profile how much time each function costs. It can also be done with third-party analyzers, such as AQtime, Intel VTune, and AMD Code Analyst.Due to the short time interval, time measurement requires very high resolution. Users can use the QueryPerformanceCounter or GetTickCount functions for millisecond resolution in Windows. Use the time stamp counter in the CPU to get a higher resolution RDTSC. This instruction counts at the CPU clock frequency.We need to identify the most time-consuming hotspots of the basic implementation of the serial test and the approximate entropy test. The Hotspots analysis helps understand these tests and identify steps that take a long time to execute (hotspots). Intel VTune amplifier identifies that Step 2 of the serial test is the most time-consuming hotspot of this test. In the serial test, this step determinesvi1vi2…vim, vi1vi2…vim−1, and vi1vi2…vim−2 and the frequency of all possible m-bit, m−1-bit, and m−2-bit subsequence, respectively. Then, the Intel VTune amplifier identifies that Step 2 of the approximate entropy test is the most time-consuming hotspots of this test. This step determines vi1vi2…vim the frequency of all possible m-bit subsequences.All the operations of Algorithm3 are based on bit operations, which seriously reduce the performance of these tests.In practice, a binary sequence is in the form of an octet string. This octet string needs to be converted into a bit string, and then, the bit string is sent into Algorithm3 to determine the frequency of all possible m-bit subsequences.Algorithm3 is replaced by bit operations with byte operations, and the performance will be significantly improved.


## 4.2. Fast Implementation Based on Octet Operation

In practice, a binary sequence is almost in the form of the octet string, so we assume thatn is divided by 8|n The random byte is a byte sequence formed by combining random bits by bit-by-bit splicing.DenoteE=E1,E2,…,En/8 the octet string of the binary sequence ε=ε1,ε1,…,εn of length n, with Ei=ε8i−7,ε8i−6…,ε8i, i=1,2,…,n/8. Because the value of the parameter m is less than 8, the extended octets are not more than one octet (8 bits). Extend the sequence by appending the first octet to the end of the octet string and E′=E1,E2,…,En/8,E1 to form the augmented octet string E′. Algorithm 4 determines the frequency based on multiple bits’ operations.


## 4.3. Analysis of Computational Complexity

This section analyses and compares the number of arithmetic operations of the above algorithms. Because Step 2 is the most time-consuming, so the main task is to analyze the computational complexity of Algorithm3 based on bit string and bit operations and Algorithm 4 based on octet string and multibit operations.Unroll Step 2.2 of Algorithm4, which can reduce many operations. The CMP operation is clear, and the left and right shift number does not need to be calculated. The computational complexity is reduced to n/8 LOAD, n ADD, nm+7/8 SHIFT, n AND, and nm+7/8 OR.The efficiency of the loop depends on the microprocessor’s ability to predict the control branch of the loop. A loop with a small and fixed repeat count and no branches inside can be predicted perfectly. It is best to avoid loop unrolling on processors with microoperation cache because it is important to save the use of microoperation cache. The unrolled loop takes up more space in the code cache or microoperation cache. If there are specific advantages to be gained, such as eliminating the if branch, the programmer should manually unroll a loop.Loop unrolling of Algorithm4 has many advantages. Then, if the branch is eliminated, the CMP operation is removed, and the left and right shift numbers are cleared.The computational complexity of Algorithm3 (based on bit string) and Algorithm 4 (based on octet string) is provided in Table 4.Table 4
The computational complexity of Algorithms3 and 4.
Execution numberOperationsAlgorithm3Algorithm3LOADmnn/8ADD2mnnSHIFTmnnm+7/8AND0nORmnnm−1/8For example, when the value ofm is 3, the execution numbers of Algorithms 3 and 4 are 15n and 3.625n, respectively.The serial test determines the frequency of all possiblej-bit patterns, with j=1,2,3,4,and5. In Algorithm 3 (based on bit string), the sum of operations of the serial test (with j=1,2,3,4,and5) is(8)∑m=155mn=75n.In Algorithm4 (based on octet string), the sum of operations of the serial test (with j=1,2,3,4,and5) is(9)∑m=15n2m+238=18.125n.In contrast to the number of arithmetic operations of the above two algorithms, it is shown that Algorithm4 based on the octet string is superior to Algorithm 3 based on bit string, in the serial test. Table 5 shows the number of arithmetic operations of the above two algorithms.Table 5
The number of operations of Algorithms3 and 4 in the serial test.
OperationsExecution number of serial testCalling algorithm3Calling algorithm4LOAD15n0.625nADD30n5nSHIFT15n6.25nAND0.5nOR15n1.25nThe approximate entropy test determines the frequency of all possiblej-bit patterns, with j=2,3,5,and6. In Algorithm 3 (based on bit string), the sum of operations of the approximate entropy test is(10)∑m=2,3,5,65mn=80n.In Algorithm4 (based on octet string), the sum of operations of the approximate entropy test is(11)∑m=2,3,5,6n2m+238=15.5n.In contrast to the number of arithmetic operations of the above two algorithms, it is shown that Algorithm4 based on octet string is superior to Algorithm 3 based on bit string, in the approximate entropy test. Table 6 shows the number of arithmetic operations of the above two algorithms.Table 6
The number of operations of Algorithms3 and 4 in the approximate entropy test.
OperationsExecution number of approximate entropy testCalling algorithm3Calling algorithm4LOAD16n0.5nADD32n4nSHIFT16n5.5nAND04nOR16n1.5nHowever, different instructions cost different cycles. Integer operations are usually very fast. On most microprocessors, most simple integer operations (such as addition, subtraction, comparison, bit operations, and shift operations) only take one clock cycle. Multiplication and division require longer clock cycles. Usually, integer multiplication requires 3-4 clock cycles, and integer division requires 40–80 clock cycles. In addition, it may take longer to access data from RAM compared to the time required to perform calculations on the data. If it is cached, it only takes 2-3 clock cycles to read or write the variables in the memory, while if it is not cached, it takes hundreds of clock cycles [23]. So, the exact time consuming of these algorithms needs to do many different experiments.


## 5. Further Optimizing

### 5.1. Merging These Two Tests

As mentioned earlier, accessing data from RAM may take longer than the time it takes to perform calculations on the data. This is why all modern computers have a memory cache. Generally, there are a level 1 data cache, a level 2 cache, and a level 3 cache. If the total size of all data in the program is greater than the level 2 cache and the data is scattered in the memory or accessed in a nonsequential manner, memory access may be the largest time-consuming operation in the program. If it is cached, it only takes 2-3 clock cycles to read or write a variable in the memory, while if it is not cached, it takes hundreds of clock cycles.The sequence size is 125000 bytes, which is bigger than most of the level-1 cache, so these data cannot be cached. Loading sequence data in memory costs many clock cycles, and memory access is the time-consuming operation (hotspots) in these tests. The size of the sequence cannot be reduced, and the cache of the CPU is fixed. The best thing we can do is reduce the loading times of data to improve the performance of these tests. Many specifications propose to perform both the serial test and the entropy test.Step 2 of the serial test and Step 2 of the approximate entropy test have similar functions and call the same algorithm so that these tests may be merged. The values ofm are proposed in specification [3]. In the serial test, the values are m=2and5, which need to determine the frequency of 1-bit, 2-bit, 3-bit, 4-bit, and 5-bit pattern. In the approximate entropy test, the values are m=2and5, which need to determine the frequency of 2-bit, 3-bit, 5-bit, and 6-bit pattern so one can determine the frequency of i-bit patterns, with i=1,2,…,6.There are many benefits to the merger of the six cases. Firstly, lots of the same operations of Algorithm4 can be combined. For example, the large number of loading operations only need to execute one time with m=1,2,…,6, and the loading data operations reduce 5n/8, which enhances the efficiency of data. Secondly, the number of calling algorithms can be greatly reduced, which further speeds up the test performance.Algorithm5 shows the emerged test based on multibit, which is the merger of the serial test and the approximate entropy test.Algorithm 5: Merged test based on multibit.
Input: an octet string E=E1,E2,…,En/8 of octet length n/8.Output: pass or not passStep 1: extend the sequence by appending the first octet to the end of the sequenceE′=E1,E2,⋯,En/8,E1.Step 2: call Algorithm6 to determine vi1vi2…vim the frequency of all possible j-bit pattern, with j=1,2,…,6.Step 3: computeψj2, j=1,2,…,5. ψj2=2j/n∑i1⋯ijvi1⋯ij2−n.Step 4: compute∇ψj2 and ∇2ψj2, j=1,2,…,5. ∇ψj2=ψj2−ψj−12∇2ψj2=ψj2−2ψj−12+ψj−22.Step 5: computeP values of the serial test, j=2,5P1STj=igamc2j−2,∇ψj2/2P2STj=igamc2j−3,∇ψj2/2.Step 6: pass the serial test, ifP1STj≥α, P2STj≥α, j=2and5. Otherwise, not pass.Step 7: computeCij=vi1i2⋯ij/n, for each value of i.Step 8: computeΦj, j=2,3,5,6Φj=∑i=12mCijlnCij, j=2,3,5,and6.Step 9: computeχ2=nln2−ApEnj with ApEnj=Φj−Φj−1, j=2,3,5,and6.Step 10: computeP values of the approximate entropy test. PAETj=igamc2j−1,χ2/2, j=2and5.Step 11: pass the approximate entropy test, ifPAET2≥α, j=2and5. Otherwise, not pass.Algorithm6 shows the merger of the six cases, which determine the frequency of the i-bit pattern, with i=1,2,…,6.Algorithm 6: Determine the frequency of all possible m-bit subsequence with m=1,2,…,6.
Input: a extended octet string E′=E1,E2,…,En/8,E1 of octet length n/8+1.Output:v1w,v2w,v3w,v4w,v5w,andv6w, for each value of w=i1i2…ij, i=1,2,…,6.Step 1:v1w=v2w=v3w=v4w=v5w=v6w=0, for each value of w=i1i2…ij, i=1,2,…,6. Mj=2j−1, i=1,2,…,6.Step 2: Fori=1,2,…,n/8, do: 2.1Z=Ei≪8|Ei+1 2.2 for k=15,14,…,3, do x=Z≫k for j=MAX9−k,1,…,MIN16−k,6 do. y=x&Mjvjy=vjy+1.Step 3: Returnv1w,v2w,v3w,v4w,v5w,andv6w.In Step 2.2, the conditions ofj are 1≤j≤6 and 8<k+j≤16, which ensure the validity of the results. For example, k = 13, v2y(j = 2) is valid, and v5y(j = 3) is invalid. It is recommended to unroll the loop of j and k in programming, reducing lots of operations.The codes of Algorithm6 are shown in Appendix, with loop unrolling.


#### 5.1.1. Computational Complexity

This section analyses the number of arithmetic operations of the above algorithms.Algorithm5 shows the emerged test based on multibit, which is the merger of the serial test and the approximate entropy test. The most time-consuming step of this test still is Step 2, which calls Algorithm 6, to determine the frequency of all possible j-bit patterns, with j=1,2,…,6. In Algorithm 6, Step 1 and Step 3 do basic operations, and Step 2 is the crucial step and the most time-consuming step.The computational complexity of Algorithm6 is n/8 LOAD, 6n ADD, 7n/4 SHIFT, 6n AND, and n/8 OR. The details are provided in Table 7.Table 7
The number of operations of Algorithm6.
OperationsAlgorithm6LOAD0.125nADD6nSHIFT1.75nAND6nOR0.125nIn the implementation of these two tests, different algorithms have different performances. Table8 lists the number of operations of Algorithms 3, 4, and 6 in the serial test and the approximate entropy test.Table 8
The number of operations of Algorithms3, 4, and 6.
OperationsSerial test and approximate entropy testAlgorithm3Algorithm4Algorithm6LOAD31n1.125n0.125nADD62n9n6nSHIFT31n11.75n1.75nAND09n6nOR31n2.75n0.125n


## 5.1. Merging These Two Tests

As mentioned earlier, accessing data from RAM may take longer than the time it takes to perform calculations on the data. This is why all modern computers have a memory cache. Generally, there are a level 1 data cache, a level 2 cache, and a level 3 cache. If the total size of all data in the program is greater than the level 2 cache and the data is scattered in the memory or accessed in a nonsequential manner, memory access may be the largest time-consuming operation in the program. If it is cached, it only takes 2-3 clock cycles to read or write a variable in the memory, while if it is not cached, it takes hundreds of clock cycles.The sequence size is 125000 bytes, which is bigger than most of the level-1 cache, so these data cannot be cached. Loading sequence data in memory costs many clock cycles, and memory access is the time-consuming operation (hotspots) in these tests. The size of the sequence cannot be reduced, and the cache of the CPU is fixed. The best thing we can do is reduce the loading times of data to improve the performance of these tests. Many specifications propose to perform both the serial test and the entropy test.Step 2 of the serial test and Step 2 of the approximate entropy test have similar functions and call the same algorithm so that these tests may be merged. The values ofm are proposed in specification [3]. In the serial test, the values are m=2and5, which need to determine the frequency of 1-bit, 2-bit, 3-bit, 4-bit, and 5-bit pattern. In the approximate entropy test, the values are m=2and5, which need to determine the frequency of 2-bit, 3-bit, 5-bit, and 6-bit pattern so one can determine the frequency of i-bit patterns, with i=1,2,…,6.There are many benefits to the merger of the six cases. Firstly, lots of the same operations of Algorithm4 can be combined. For example, the large number of loading operations only need to execute one time with m=1,2,…,6, and the loading data operations reduce 5n/8, which enhances the efficiency of data. Secondly, the number of calling algorithms can be greatly reduced, which further speeds up the test performance.Algorithm5 shows the emerged test based on multibit, which is the merger of the serial test and the approximate entropy test.Algorithm 5: Merged test based on multibit.
Input: an octet string E=E1,E2,…,En/8 of octet length n/8.Output: pass or not passStep 1: extend the sequence by appending the first octet to the end of the sequenceE′=E1,E2,⋯,En/8,E1.Step 2: call Algorithm6 to determine vi1vi2…vim the frequency of all possible j-bit pattern, with j=1,2,…,6.Step 3: computeψj2, j=1,2,…,5. ψj2=2j/n∑i1⋯ijvi1⋯ij2−n.Step 4: compute∇ψj2 and ∇2ψj2, j=1,2,…,5. ∇ψj2=ψj2−ψj−12∇2ψj2=ψj2−2ψj−12+ψj−22.Step 5: computeP values of the serial test, j=2,5P1STj=igamc2j−2,∇ψj2/2P2STj=igamc2j−3,∇ψj2/2.Step 6: pass the serial test, ifP1STj≥α, P2STj≥α, j=2and5. Otherwise, not pass.Step 7: computeCij=vi1i2⋯ij/n, for each value of i.Step 8: computeΦj, j=2,3,5,6Φj=∑i=12mCijlnCij, j=2,3,5,and6.Step 9: computeχ2=nln2−ApEnj with ApEnj=Φj−Φj−1, j=2,3,5,and6.Step 10: computeP values of the approximate entropy test. PAETj=igamc2j−1,χ2/2, j=2and5.Step 11: pass the approximate entropy test, ifPAET2≥α, j=2and5. Otherwise, not pass.Algorithm6 shows the merger of the six cases, which determine the frequency of the i-bit pattern, with i=1,2,…,6.Algorithm 6: Determine the frequency of all possible m-bit subsequence with m=1,2,…,6.
Input: a extended octet string E′=E1,E2,…,En/8,E1 of octet length n/8+1.Output:v1w,v2w,v3w,v4w,v5w,andv6w, for each value of w=i1i2…ij, i=1,2,…,6.Step 1:v1w=v2w=v3w=v4w=v5w=v6w=0, for each value of w=i1i2…ij, i=1,2,…,6. Mj=2j−1, i=1,2,…,6.Step 2: Fori=1,2,…,n/8, do: 2.1Z=Ei≪8|Ei+1 2.2 for k=15,14,…,3, do x=Z≫k for j=MAX9−k,1,…,MIN16−k,6 do. y=x&Mjvjy=vjy+1.Step 3: Returnv1w,v2w,v3w,v4w,v5w,andv6w.In Step 2.2, the conditions ofj are 1≤j≤6 and 8<k+j≤16, which ensure the validity of the results. For example, k = 13, v2y(j = 2) is valid, and v5y(j = 3) is invalid. It is recommended to unroll the loop of j and k in programming, reducing lots of operations.The codes of Algorithm6 are shown in Appendix, with loop unrolling.


### 5.1.1. Computational Complexity

This section analyses the number of arithmetic operations of the above algorithms.Algorithm5 shows the emerged test based on multibit, which is the merger of the serial test and the approximate entropy test. The most time-consuming step of this test still is Step 2, which calls Algorithm 6, to determine the frequency of all possible j-bit patterns, with j=1,2,…,6. In Algorithm 6, Step 1 and Step 3 do basic operations, and Step 2 is the crucial step and the most time-consuming step.The computational complexity of Algorithm6 is n/8 LOAD, 6n ADD, 7n/4 SHIFT, 6n AND, and n/8 OR. The details are provided in Table 7.Table 7
The number of operations of Algorithm6.
OperationsAlgorithm6LOAD0.125nADD6nSHIFT1.75nAND6nOR0.125nIn the implementation of these two tests, different algorithms have different performances. Table8 lists the number of operations of Algorithms 3, 4, and 6 in the serial test and the approximate entropy test.Table 8
The number of operations of Algorithms3, 4, and 6.
OperationsSerial test and approximate entropy testAlgorithm3Algorithm4Algorithm6LOAD31n1.125n0.125nADD62n9n6nSHIFT31n11.75n1.75nAND09n6nOR31n2.75n0.125n


## 5.1.1. Computational Complexity

This section analyses the number of arithmetic operations of the above algorithms.Algorithm5 shows the emerged test based on multibit, which is the merger of the serial test and the approximate entropy test. The most time-consuming step of this test still is Step 2, which calls Algorithm 6, to determine the frequency of all possible j-bit patterns, with j=1,2,…,6. In Algorithm 6, Step 1 and Step 3 do basic operations, and Step 2 is the crucial step and the most time-consuming step.The computational complexity of Algorithm6 is n/8 LOAD, 6n ADD, 7n/4 SHIFT, 6n AND, and n/8 OR. The details are provided in Table 7.Table 7
The number of operations of Algorithm6.
OperationsAlgorithm6LOAD0.125nADD6nSHIFT1.75nAND6nOR0.125nIn the implementation of these two tests, different algorithms have different performances. Table8 lists the number of operations of Algorithms 3, 4, and 6 in the serial test and the approximate entropy test.Table 8
The number of operations of Algorithms3, 4, and 6.
OperationsSerial test and approximate entropy testAlgorithm3Algorithm4Algorithm6LOAD31n1.125n0.125nADD62n9n6nSHIFT31n11.75n1.75nAND09n6nOR31n2.75n0.125n


## 6. Experimental Results

This section shows the experimental results of the above algorithm. In contrast to the performance of these algorithms, it is shown that Algorithm4 (based on octet string) and Algorithm 6 (based on the merger of these tests) are superior to Algorithm 1 (based on bit string).At first, it shows the way to perform analysis of the above algorithms. The first step is to set a time counterTs before the algorithm to be analyzed, and set another time counter Te after the algorithm. Then, run the application and get the elapsed time Ti=Te−Ts. Repeat Step 1 and Step 2 k times (k is odd), and get multiple values of the elapsed time Tii=1,2,…,k. By the descending order of these values, T1′T2′≥…≥Tk′, and the intermediate value Tk+1/2 is the elapsed time of the algorithm.We can use the command RDTSC to get the current time. RDTSC instruction loads the current value of the processor’s time stamp counter (64-bit counter). The processor monotonically increments the timestamp counter every clock cycle and resets it to 0 every time the processor is reset. The RDTSC instruction is not serialized. It does not have to wait until all previous instructions have been executed to read the counter.We measure our algorithms and these tests on a personal computer. This computer has one Intel Core i3-3240@ 3400 MHz CPU with four cores. Measurements use one core. The compiler used to compile our C code is Intel C++ Compiler XE 12.0.The input data of Algorithm3 is a bit string of length 1000000, and the input data of Algorithms 4 and 8 is the octet string of byte length 125000, which is converted from that binary string.Algorithm3 (based on bit string) and Algorithm 4 (based on octet string) can be used to determine the frequency of the m-bit pattern. Algorithm 6 (based on octet string) can be used to determine the frequency of the i-bit pattern with m=1,2,…,6.In the serial test, one should determine the frequency of 1-bit, 2-bit, 3-bit, 4-bit, and 5-bit patterns. In the approximate entropy test, one should determine the frequency of 2-bit, 3-bit, 5-bit, and 6-bit patterns. Algorithm6 can complete this task.On the same test platform, we use the NIST STS source code provided by NIST, the source code of Fast NIST STS from [17], and the implementation of this paper to test serial test and approximate entropy test. Table 9 shows the performance of the original implementation NIST STS, the implementation Fast NIST STS from [17], and our new implementation.Table 9
The performance of the original implementation NIST STS, the implementation Fast NIST STS from [17], and our new implementation. Merged test is a combined test of the serial test (m = 2 and 5) and approximate entropy test (m = 2 and 5).
TestsNIST STS [1] (ms)Fast NIST STS [17] (ms)Our (ms)Speedup our vs. Fast NIST STSSerial test (m = 2)32.8440.6270.5461.148Serial test (m = 5)64.6100.6300.5751.096Serial test (m = 2 and 5)96.1631.2830.5932.164Approximate entropy test (m = 2)36.0460.6360.5531.150Approximate entropy test (m = 5)50.8310.6470.581.116Approximate entropy test (m = 2 and 5)124.5061.2620.6012.100Merged test220.3132.5610.6284.078The original implementation of NIST STS is based on bits when performing serial tests and approximate entropy tests. This makes the detection time increase significantly whenm increases. For example, when m = 2, it takes 32.844 milliseconds to perform the serial test, and when m = 9, the time increases to 169.163 milliseconds. In addition, the original implementations of NIST STS and Fast NIST STS both perform detection for a single parameter m when performing serial tests and approximate entropy tests. This makes m = 2 and m = 5 need to perform corresponding tests, respectively.It can be seen from Table9 that the efficiency of the serial test and the approximate entropy test are increased by 2.164 and 2.100 times separately, compared with the implementation of Fast NIST STS, and the execution efficiency of the merge test has been significantly improved. Its execution time is very close to that of the serial test or approximate entropy test alone. At the same time, the efficiency of the merge test reached 4.078 times that of Fast NIST STS.In most applications, all the detection items of the test suit need to be executed. Therefore, the algorithm proposed in this paper has very important value in practical applications and can significantly reduce the execution time of these two detection algorithms.


## 7. Conclusions

In this paper, we study the fast implementation of the serial test and the approximate entropy test and propose two types of fast implementation of these tests.The first fast implementation method is to follow the basic steps according to these tests and then call Algorithm4 to determine the frequency of the m-bit pattern. In this implementation, the efficiency of the serial test and the approximate entropy test are increased by 2.164 and 2.100 times separately, compared with the implementation of Fast NIST STS. The second one is to merge these tests, combine the steps, and call Algorithm 6 to determine the frequency of all the possible values of m. In this implementation, the efficiency has been greatly improved relative to the individual implementation of these tests, and the improvement is much more significant compared with the basic implementation based on bits’ operations. The best efficiency of this method is increased by 4.078 times, comparing to the implementation of Fast NIST STS.In conclusion, we propose the fast implementation method based on merging tests and combining the frequency of the subsequences. This method not only can be used in the merging test but also can be used to only do the serial test or only do the approximate entropy test.



---

*Source: 1375954-2021-09-16.xml*