The available approaches to testing pseudorandom sequences show low flexibility and versatility in the means of finding hidden patterns in the data. To solve this problem, it is suggested to use algorithms based on multidimensional statistics. The paper proposed a new approach for testing pseudorandom sequences, obtained an explicit form of the joint distribution of numbers of 2-chains and numbers of 3-chains of various options random bit sequence of a given small length. Examples, tables, diagrams that can be used to test for randomness of the location of zeros and ones in the bit section are presented. In future as a result an information system will be created that will allow analyzing the pseudorandom sequence of a small length and choosing a quality pseudorandom sequence for use in a particular subject area.
Random sequences have found the widest application from the gaming computer industry to mathematical modeling and cryptology.
We list some areas of their usage: modeling, cryptography and information security, decision making in automated expert systems, optimization of functional dependencies, fun and games.
There are various approaches to the formal definition of the term “randomness” based on the concepts of computability and algorithmic complexity [1-2].
By implementing some algorithm, software generators produce numbers (although not obvious) depending on the set of previous values, so the received numerical sequences are not truly random and are called pseudo-random sequences (PRS). At the moment, more than a thousand software PRS generators are known, which differ in algorithms and values of parameters. Statistical properties are significantly different from the number sequences that are generated by them.
Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) 2019 DCSMart Workshop.
The presented and not presented results allow us to characterize the state of modern technologies of designing the PRS (focusing on the most progressive of them by the following basic provisions [3-6]. 2
Before responsible using in mathematical modeling and cryptology, PRS should be tested. Unfortunately, for many PRS tests, there are some limitations: • checked out only one of the probable ones properties that are characterize
PRS; • not fix family alternatives; • do not have theoretical ones ratings power. • do not give a correct an estimate of chance sequences provided a little sample.
Problems small and large samples refer to the main problems that arise in practical application methods analysis data. Let's be use the next classification samples by number [2], based on requirements presented in the program criteria: • very small sample - from 5 to 12, • small sample - from 13 to 40, • medium sample - from 41 to 100, • large sample - from 101 and more.
The minimum size of the sample limits not so much the algorithm of calculating the criterion, but the distribution of its statistics. For a row algorithms with too much small ones numbers sample normal approximation distribution of statistics criterion will be under question.
During the research, the localization of the local sections of the bit sequence was conducted to detect the dependencies in the location of its elements by using the exact distributions of the corresponding statistics. In the work an explicit form of the joint distribution of the numbers of 2-chains and numbers of 3-chains of various variants in a random sequence was obtained. This joint distribution allows more accurate comparison of the use of one-dimensional statistics, to analyze the bit sequence small length by chance. 3
Joint Distribution of number of 2-chains and number of 3chains of a provided type in binary sequence Consider a sequence of random variables where = {0, 1}, i= 1, 2, . . . , , > 0.
Subsequences , +1, . . . , + −1, 1, 2, . . . , − + 1, = 1, 2, . . . , .
1, 2, . . . , ,
(
Denote ( 1 2 . .. ) the number of s-chains in the sequence (
Theorem. Let sequence (
1, if = = 0; −−11,
if ≥ ≥ 1; Ρ{ ( ) = 1, ( ∗ ∗ ∗) = 2} = ∑
1=0 1 0 × { 1 − 1−1Ζ( ∗ − + 1 + 1; − 1 − 1 − 1)+ 2 − 1+1Ζ( ∗ − + 1 − 1; − 1 − 2 + 1)+
2 3− 1Ζ( ∗ − + 1; − 1 − 3)+ ( − 1 − 1, 2, ∗)}Ζ( ; − 1), Ρ{ ( ) = 1, ( ∗ ∗) = 2 } = ∑ 1=0 1 0 × { 2 − 1−2 1+1
− 1− 2−1Ζ( ∗; − 1 − 1) 1( − 1 − 2)+ − 1 t∗−− 11Ζ( 1; − 1 − 2)+ 2 − 1−1 ∗−1 2 2
− 1− 2−1 − 1− 2−1 +
1 2( − 1 − 1, 2, ∗)}, where 1( 1) = {0, elsewhere 1, if 1 ≥ 1,
, 2( 1, 2, 3) = {0, e1l,siefw h1e=re 2 = 3 = 0, Ρ{ ( ) = 1, ( ∗ ∗ ∗)+ ( ∗ ∗) = 2 } = ∑ 1=0 1 0 × {(∑ + ∗= 1 1 × − 1−2 ∗− 1−1 1+1
− 1−δ−1Ζ( ∗ − + 1 + 1; − 1 − ∗ − 1)+ (∑ + ∗= 2 δ
∗ − 1 − 1+1Ζ( 1; − 1 − δ)Ζ( ∗ − + 1 − 1; − 1 − ∗ + 1))+(∑ + ∗= 3 − 1−1 ∗− 1 1
− 1−δ−1Ζ( ∗ − + 1; − 1 − ∗))
+ ( − 1 − 1, 2, ∗)},
(
denotes addition over all non-negative integers and ∗ such that
As a result of applying this technique for testing pseudo-random sequences for
twodimensional statistics, you can build tables (relations (
As practice shows, the use of ready-made tables for analyzing the sequence of randomness allows you to get the answer as quickly as possible, in contrast to the classical testing method.
Consider an example of tables and bubble diagrams for a bit-sequence of small
length. For example, let the length of the bit sequence n, n = 32 for relations (
Illustration of the Use of Equality (
In Table 1 the first column contains all possible values 1 and 2, for which probability is Ρ{ ( ) = 1, ( ∗ ∗ ∗) = 2} ≥ 0,01. The second column of Table 1 gives the probabilities (in non-decreasing order) { ( ) = 1, ( ∗ ∗ ∗) = 2} for pairs of numbers ( 1, 2) listed in the first column.
Each row of the fourth column contains the sum of the accumulated probabilities before the event is implemented { ( ) = 1, ( ∗ ∗ ∗) = 2} inclusive where 1 and 2 indicated in the same line in the first column. 4.2
Illustration of the Use of Equality (
In Table 4 in the first, second and third columns are all possible values 1, 2 and 3, for which probability Ρ{ ( ) = 1, ( ∗ ∗ ∗) = 2, ( ∗ ∗) = 3 } ≥ 0,009 , and the contents of the fourth and fifth columns are similar to the contents of the third and fourth columns of the Table 1. 5
Results and Discussion
As a result of applying this technique for testing pseudo-random sequences for
twodimensional statistics (relations (
Consider examples of bubble diagrams for a bit sequence of small length n, n = 32. 5.1
Graphic Illustration of the Use of Equality (
After analyzing Fig. 1 it can be concluded that for the analysis of the sequence of chains of small and medium length (from 13 to 100 elements), one-dimensional statistics do not always give the correct result. For example, if we consider the sequence where the parameter 1 = 8, then we can draw a conclusion with a degree of probability about 10% of randomness of the sequence with these characteristics, however, if we pay attention when 1 = 8 and 2 = 5 it can be argued that this sequence is non6 5 2,71% 2,99%
2,64% 2,38% 3,31% 3,68% 3,36%
2,59% 2,25% 3,09% 3,50% 3,32%
2,71% 2,09% 2,42% 2,40% 2,07% random, therefore as shown in Fig. 1 we have Ρ{ ( ) = 1, ( ∗ ∗ ∗) = 2} = 1,45%. What also shows the lack of use of one-dimensional statistics for the analysis of small and medium bit sequences.
An approach to testing using n-dimensional statistics allows us to rely on a deeper justification of the randomness of generated sequences. 5.2
Graphic Illustration of the Use of Equality (
4 5 6 7
Valu8e k1
9
10
11
12
In Fig. 3 shows the use of relation (
Fig. 3 gives a bubble chart in which the first parameter (horizontal axis) is the value 1, the second parameter (vertical axis) is the value 2, and the third parameter (bubble size) is the probability of the event occurring { ( ) = 1, ( ∗ ∗ ∗) + ( ∗ ∗) = 2 }, which is represented as a percentage. 6 • • • • • 2 k eu 7 l a V 6 5 4 2,16% 2,42% 2,61% 2,70%
2,11% 2,03% 2,78% 2,74%
2,08% 2,02% 2,62% 2,51% 2,16%
2,06% 9 10 11 4 5 6 7
8
Value k1
In this paper, the exact compatible distributions of some statistics (
The Results of the Comparison the NIST Statistical Test Suite and Test of PRS of Small Length using Multidimensional Statistics Consider the well-known examples that are given in [7, 8]. Let us analyze the submitted sequences for the corresponding tests, where:
P is the probability of sequence randomness according to the selected criterion
from the first column,
P1 is the probability obtained using relation (
As can be seen from the table, the use of two-dimensional statics gives a more accurate result for short sequences. And also, according to [8], the recommended minimum sequence length n is greater than 100 bits.
The available approaches to testing pseudorandom sequences show low flexibility and versatility in the means of finding hidden patterns in the data. To solve this problem, it is suggested to use algorithms based on multidimensional statistics.
The approach to testing using multidimensional statistics allows you to rely on a deeper justification of the randomness of the generated sequences. This area is promising for scientific research.
The paper proposed a methodology for testing a sequence and obtained a correct view of the joint distribution of the numbers of 2-chains and the numbers of 3-chains of various variants in a random bit sequence of a given small length.
These algorithms and scheme of work for verification statistical tests of randomness sequences (proposed in chapter II) combine all the advantages of statistical methods and are the only alternative for the analysis of sequences of small and medium length.
To implement the proposed approach, a PRS software test package is being developed, which will include tests using multidimensional statistics, which are well recommended for testing a small length PRS. As a result of the implementation of this technique, an information system will be created that will allow analyzing the PRS of a small length and choosing a quality PRS for use in a particular subject area.