The Design Of A Novel Random Number Test Algorithm Based On Burrows-Wheeler Transform

Random numbers play a fundamental and critical role in cryptography,simulation and other fields.The quality of random numbers is a key element of applications in these fields.The randomness test can be used to detect the quality of random numbers to ensure that it meets the requirements of applications.At present,most randomness test algorithms are mainly based on the principle of repetitive pattern detection,but there is room for further improvement in algorithm implementation and detection capability.This thesis designs a new random number detection algorithm based on Burrows-Wheeler Transform(BWT).Firstly,the algorithm detects the frequency of the sequence to be measured.On the premise of 0-1 equalization,the modified BWT algorithm is used to process the sequence.Then,Run Test,Discrete Fourier Transform Test,Linear Complexity Test and Random Excursions Test in the traditional randomness test algorithm are applied to the sequence processed by BWT algorithm.In this way,the pattern detection problem of the sequence is transformed into the character distribution problem of the sequence after BWT processing,and finally the detection of the randomness of the sequence is realized.By means of suffix sorting,the detection algorithm improves the pattern detection method of the sequence,and processes all the possible repetitive patterns in the sequence to be tested in the way of character aggregation.Compared with the traditional randomness test algorithm,detection performance of the algorithm are improved to a certain extent.Based on the above innovations,this thesis also designs a random number command line detection software,which includes 15 items of the proposed new randomness test algorithm and the randomness test of NIST standard.It can detect the random number of sequences comprehensively.