GM/T 0005:2021 Randomness test specification English
1 Scope
This document specifies the randomness test index and test method applicable to binary sequences.
2 Normative references
There are no normative references in this document.
3 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
3.1
binary sequence
bit string consisting only of "0" and "1”
Note: Unless otherwise specified, the sequences referred to in this document are binary sequences.
3.2
randomness hypothesis
hypothesis that a binary sequence is random when it is subjected to randomness test, which is called original or null hypothesis and denoted as H0. The hypothesis opposite to the original hypothesis, that is, the sequence is not random, is called alternative hypothesis, which is denoted as Hα
3.3
randomness test
function or process used in binary sequence test, which may be used to judge whether the randomness hypothesis is acceptable
3.4
significance level
probability of judging a random sequence as a non-random sequence by mistake in randomness test
3.5
sample
binary sequence used for randomness test
3.6
sample group
collection of multiple samples
3.7
sample length
number of bits of a sample
3.8
sample size
number of samples in a sample group
3.9
test parameter
parameter to be set for randomness test
4 Symbols
For the purposes of this document, the following symbols apply.
d: Logical left shift bit of sequences in autocorrelation test
H0: Original hypothesis (null hypothesis)
Hα: Alternative hypothesis
K: Number of L-bit subsequences of the sequence to be tested in universal statistical test
L: Subsequence length in universal statistics
Li: Linear complexity of subsequences in linear complexity test
M: Number of rows of matrix in binary matrix rank test
m: Bit length of a subsequence
N: Number of m-bit subsequences in an n-bit sequence to be tested
n: Bit length of the binary sequence to be tested
Q: Number of columns of matrix in binary matrix rank test, or number of L-bit subsequences of initial sequence in universal statistical test
V: Statistical value
Xi: 2εi-1
α: Significance level for sample pass rate test
αT: Significance level for sample distribution uniformity test
ε: Binary sequence to be tested
ε′: New sequence generated according to certain rules on the basis of ε
π: Proportion of ones in the binary sequence to be tested
∑: Summation sign
*: Multiplication, sometimes omitted
ln(x): Natural logarithm of x
log2(x): Base-2 logarithm of x
: Largest integer not greater than x
max: Take the maximum value from several elements
min: Take the minimum value from several elements
Φ(x): Cumulative distribution function of standard normal distribution
P_value: Measurement index to measure the randomness of samples, used for the judgment of sample pass rate
Q_value: Measurement index to measure the randomness of samples, used for the judgment of sample distribution uniformity
erfc: Complementary Error Function
igamc: Incomplete Gamma Function
Vn(obs): Total number of runs in the binary sequence to be tested
ApEn(m): Approximate entropy of the binary sequence to be tested
modulus(x): Operation used to calculate the module value of complex coefficient x
: The first statistical value in serial test
: The second statistical value in serial test
5 Randomness test methods
5.1 Monobit frequency test
5.1.1 General
The monobit frequency test is the most basic test, which is used to test whether the number of zeros and that of ones in a binary sequence are similar. The random sequences shall have balanced zeros and ones.
5.1.2 Test steps
The monobit frequency test steps are as follows:
Step 1: Convert “0” and “1” in the sequence to be tested ε into “-1” and “1”, Xi=2εi-1 (1≤i≤n).
Step 2: Obtain by cumulative summation.
Step 3: Calculate the statistical value .
Step 4: Calculate .
Step 5: Calculate .
The test settings are in accordance with the requirements of Annex A and See B.1 for the test principle.
5.1.3 Result judgment
The P_value calculated in 5.1.2 is compared with α. If P_value≥α, it is considered that the sequence to be tested passes the monobit frequency test, otherwise it fails the test.
5.2 Frequency test within a block
5.2.1 General
The frequency test within a block is used to test whether the number of ones in m-bit subsequence of the sequence to be tested is close to . For random sequences, the number of ones in m-bit subsequences of any length shall be close to .
5.2.2 Test steps
The steps for frequency test within a block are as follows:
Step 1: Divide the sequence to be tested ε into non-overlapping subsequences with length of m, and discard redundant bits.
Step 2: Calculate the proportion of “1” in each subsequence, , 1≤i≤N.
Step 3: Calculate the statistical value .
Step 4: Calculate .
Step 5: Calculate Q_value=P_value.
The test settings are in accordance with the requirements of Annex A and see B.2 for the test principle.
5.2.3 Result judgment
The P_value calculated in 5.2.2 is compared with α. If P_value≥α, it is considered that the sequence to be tested passes the frequency test within a block, otherwise, it fails the test.
5.3 Poker test
5.3.1 General
The poker test is used to test whether the number of 2m classes of subsequences with length of m is close. For random sequences, the number of 2m classes of subsequences shall be close.
Foreword i
1 Scope
2 Normative references
3 Terms and definitions
4 Symbols
5 Randomness test methods
5.1 Monobit frequency test
5.2 Frequency test within a block
5.3 Poker test
5.4 Serial test
5.5 Runs test
5.6 Runs distribution test
5.7 Test for the longest run in a block
5.8 Binary derivative test
5.9 Autocorrelation test
5.10 Binary matrix rank test
5.11 Cumulative sums test
5.12 Approximate entropy test
5.13 Linear complexity test
5.14 Maurer’s “universal statistical” test
5.15 Discrete fourier transform test
6 Randomness test judgment
6.1 General
6.2 Judgment of the sample pass rate
6.3 Judgment of the sample distribution uniformity
6.4 Judgment of the randomness test result
Annex A (Nominative) Sample length and test settings
Annex B (Informative) Randomness test principle
Annex C (Informative) Examples of randomness test results
GM/T 0005:2021 Randomness test specification English
1 Scope
This document specifies the randomness test index and test method applicable to binary sequences.
2 Normative references
There are no normative references in this document.
3 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
3.1
binary sequence
bit string consisting only of "0" and "1”
Note: Unless otherwise specified, the sequences referred to in this document are binary sequences.
3.2
randomness hypothesis
hypothesis that a binary sequence is random when it is subjected to randomness test, which is called original or null hypothesis and denoted as H0. The hypothesis opposite to the original hypothesis, that is, the sequence is not random, is called alternative hypothesis, which is denoted as Hα
3.3
randomness test
function or process used in binary sequence test, which may be used to judge whether the randomness hypothesis is acceptable
3.4
significance level
probability of judging a random sequence as a non-random sequence by mistake in randomness test
3.5
sample
binary sequence used for randomness test
3.6
sample group
collection of multiple samples
3.7
sample length
number of bits of a sample
3.8
sample size
number of samples in a sample group
3.9
test parameter
parameter to be set for randomness test
4 Symbols
For the purposes of this document, the following symbols apply.
d: Logical left shift bit of sequences in autocorrelation test
H0: Original hypothesis (null hypothesis)
Hα: Alternative hypothesis
K: Number of L-bit subsequences of the sequence to be tested in universal statistical test
L: Subsequence length in universal statistics
Li: Linear complexity of subsequences in linear complexity test
M: Number of rows of matrix in binary matrix rank test
m: Bit length of a subsequence
N: Number of m-bit subsequences in an n-bit sequence to be tested
n: Bit length of the binary sequence to be tested
Q: Number of columns of matrix in binary matrix rank test, or number of L-bit subsequences of initial sequence in universal statistical test
V: Statistical value
Xi: 2εi-1
α: Significance level for sample pass rate test
αT: Significance level for sample distribution uniformity test
ε: Binary sequence to be tested
ε′: New sequence generated according to certain rules on the basis of ε
π: Proportion of ones in the binary sequence to be tested
∑: Summation sign
*: Multiplication, sometimes omitted
ln(x): Natural logarithm of x
log2(x): Base-2 logarithm of x
: Largest integer not greater than x
max: Take the maximum value from several elements
min: Take the minimum value from several elements
Φ(x): Cumulative distribution function of standard normal distribution
P_value: Measurement index to measure the randomness of samples, used for the judgment of sample pass rate
Q_value: Measurement index to measure the randomness of samples, used for the judgment of sample distribution uniformity
erfc: Complementary Error Function
igamc: Incomplete Gamma Function
Vn(obs): Total number of runs in the binary sequence to be tested
ApEn(m): Approximate entropy of the binary sequence to be tested
modulus(x): Operation used to calculate the module value of complex coefficient x
: The first statistical value in serial test
: The second statistical value in serial test
5 Randomness test methods
5.1 Monobit frequency test
5.1.1 General
The monobit frequency test is the most basic test, which is used to test whether the number of zeros and that of ones in a binary sequence are similar. The random sequences shall have balanced zeros and ones.
5.1.2 Test steps
The monobit frequency test steps are as follows:
Step 1: Convert “0” and “1” in the sequence to be tested ε into “-1” and “1”, Xi=2εi-1 (1≤i≤n).
Step 2: Obtain by cumulative summation.
Step 3: Calculate the statistical value .
Step 4: Calculate .
Step 5: Calculate .
The test settings are in accordance with the requirements of Annex A and See B.1 for the test principle.
5.1.3 Result judgment
The P_value calculated in 5.1.2 is compared with α. If P_value≥α, it is considered that the sequence to be tested passes the monobit frequency test, otherwise it fails the test.
5.2 Frequency test within a block
5.2.1 General
The frequency test within a block is used to test whether the number of ones in m-bit subsequence of the sequence to be tested is close to . For random sequences, the number of ones in m-bit subsequences of any length shall be close to .
5.2.2 Test steps
The steps for frequency test within a block are as follows:
Step 1: Divide the sequence to be tested ε into non-overlapping subsequences with length of m, and discard redundant bits.
Step 2: Calculate the proportion of “1” in each subsequence, , 1≤i≤N.
Step 3: Calculate the statistical value .
Step 4: Calculate .
Step 5: Calculate Q_value=P_value.
The test settings are in accordance with the requirements of Annex A and see B.2 for the test principle.
5.2.3 Result judgment
The P_value calculated in 5.2.2 is compared with α. If P_value≥α, it is considered that the sequence to be tested passes the frequency test within a block, otherwise, it fails the test.
5.3 Poker test
5.3.1 General
The poker test is used to test whether the number of 2m classes of subsequences with length of m is close. For random sequences, the number of 2m classes of subsequences shall be close.
Contents of GM/T 0005-2021
Foreword i
1 Scope
2 Normative references
3 Terms and definitions
4 Symbols
5 Randomness test methods
5.1 Monobit frequency test
5.2 Frequency test within a block
5.3 Poker test
5.4 Serial test
5.5 Runs test
5.6 Runs distribution test
5.7 Test for the longest run in a block
5.8 Binary derivative test
5.9 Autocorrelation test
5.10 Binary matrix rank test
5.11 Cumulative sums test
5.12 Approximate entropy test
5.13 Linear complexity test
5.14 Maurer’s “universal statistical” test
5.15 Discrete fourier transform test
6 Randomness test judgment
6.1 General
6.2 Judgment of the sample pass rate
6.3 Judgment of the sample distribution uniformity
6.4 Judgment of the randomness test result
Annex A (Nominative) Sample length and test settings
Annex B (Informative) Randomness test principle
Annex C (Informative) Examples of randomness test results
