序列檢測(cè)和近似熵檢測(cè)的快速實(shí)現(xiàn)研究

王 彤，朱敏玲

北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京 100101

1 引言

網(wǎng)絡(luò)環(huán)境的日益復(fù)雜讓信息安全逐漸成為人們關(guān)注的重點(diǎn)話題。隨機(jī)序列在信息安全領(lǐng)域中有著廣泛的應(yīng)用，例如眾多的密碼算法、安全協(xié)議、數(shù)字水印、密碼芯片中都利用隨機(jī)序列來增強(qiáng)安全性[1]。因此，隨機(jī)序列的質(zhì)量直接影響信息安全問題。

隨機(jī)序列的產(chǎn)生方式分為兩種，一種是經(jīng)過物理現(xiàn)象產(chǎn)生的真隨機(jī)序列，另一種是經(jīng)過計(jì)算機(jī)中的隨機(jī)函數(shù)產(chǎn)生的偽隨機(jī)序列[2]。著名的計(jì)算機(jī)學(xué)家馮·諾依曼曾經(jīng)說過“任何想用數(shù)學(xué)的方法產(chǎn)生真隨機(jī)數(shù)的人都是在癡心妄想”[3]。而偽隨機(jī)數(shù)發(fā)生器和密碼算法是通過一系列復(fù)雜的數(shù)學(xué)運(yùn)算處理“種子值”得到偽隨機(jī)序列，因?yàn)橛小胺N子值”，偽隨機(jī)序列在一定程度上是可控可測(cè)的，難以保證其質(zhì)量。因此，在實(shí)際應(yīng)用中需要對(duì)隨機(jī)序列進(jìn)行檢測(cè)，保證隨機(jī)序列的質(zhì)量。

隨機(jī)序列實(shí)質(zhì)上是對(duì)一組均勻分布的隨機(jī)變量進(jìn)行抽樣，產(chǎn)生的結(jié)果是不可控制、不可預(yù)測(cè)的，序列中的每個(gè)元素是相互獨(dú)立，且服從均勻分布[4]。為保證隨機(jī)序列在應(yīng)用過程中的穩(wěn)定性，隨機(jī)性檢測(cè)通過一些特定的特性，比如統(tǒng)計(jì)比特?cái)?shù)量、m位非重疊子序列頻數(shù)、兩比特間異或操作等，分析待檢測(cè)序列與真隨機(jī)序列之間的差距，判斷其是否通過檢測(cè)。經(jīng)過長(zhǎng)時(shí)間的研究和發(fā)展，目前國(guó)內(nèi)外研究學(xué)者已經(jīng)提出了大量的隨機(jī)性檢測(cè)方法。國(guó)際上通用的檢測(cè)方法是將多種隨機(jī)性檢測(cè)算法組成檢測(cè)套件，以提供更復(fù)雜和全面的隨機(jī)性分析，但是隨機(jī)套件執(zhí)行效率較低，當(dāng)檢測(cè)數(shù)據(jù)達(dá)到GB級(jí)時(shí)，在標(biāo)準(zhǔn)計(jì)算機(jī)上完成一次完整的隨機(jī)性檢測(cè)可能需要數(shù)小時(shí)[5]。

在隨機(jī)性檢測(cè)的應(yīng)用價(jià)值下，國(guó)內(nèi)外眾多研究學(xué)者對(duì)隨機(jī)性檢測(cè)項(xiàng)目進(jìn)行優(yōu)化研究，例如，楊先偉等通過將不同參數(shù)情況進(jìn)行整合，對(duì)撲克檢測(cè)進(jìn)行優(yōu)化研究，提高算法效率9.5倍左右[6]；康紅娟，楊先偉等通過將待檢測(cè)序列分為初始序列和檢測(cè)序列并按字節(jié)進(jìn)行處理，減少數(shù)據(jù)流失，減少大量對(duì)數(shù)運(yùn)算，提高M(jìn)aurer通用統(tǒng)計(jì)檢測(cè)效率[7]；Suciu等采用字節(jié)處理方式優(yōu)化隨機(jī)性統(tǒng)計(jì)檢測(cè)包，檢測(cè)包整體速度提升13.45倍[8]；Sys等對(duì)NIST統(tǒng)計(jì)測(cè)試套件進(jìn)行優(yōu)化，并對(duì)線性復(fù)雜度檢測(cè)和Berlekamp-Massey算法進(jìn)行分析和優(yōu)化[9]。

2001年美國(guó)NIST發(fā)布了16種隨機(jī)性檢測(cè)標(biāo)準(zhǔn)，其中將傳統(tǒng)的序偶檢測(cè)和撲克檢測(cè)替換為序列檢測(cè)，于亦舟等人將三種檢測(cè)方法進(jìn)行對(duì)比分析，證明序列檢測(cè)效果要優(yōu)于同時(shí)使用撲克檢測(cè)和序偶檢測(cè)的效果[10]。近似熵檢測(cè)作為一項(xiàng)基礎(chǔ)檢測(cè)方法，不僅出現(xiàn)在我國(guó)的隨機(jī)性檢測(cè)標(biāo)準(zhǔn)中，也出現(xiàn)在眾多國(guó)家的檢測(cè)標(biāo)準(zhǔn)中。但是序列檢測(cè)和近似熵檢測(cè)的檢測(cè)速度較慢，在NIST統(tǒng)計(jì)測(cè)試套件中檢測(cè)速度位于各檢測(cè)項(xiàng)的末端[11]。因此，本文對(duì)序列檢測(cè)和近似熵檢測(cè)進(jìn)行優(yōu)化分析，提高檢測(cè)方法的運(yùn)行效率。

2 兩種檢測(cè)算法簡(jiǎn)介

2.1 序列檢測(cè)

序列檢測(cè)的目的是判定待檢測(cè)序列中2m個(gè)m位重疊子塊的數(shù)目是否和隨機(jī)情況下預(yù)期值一致。隨機(jī)序列具有均勻性，故序列中每種m位重疊子序列出現(xiàn)的頻數(shù)應(yīng)該是一致的[12]。

計(jì)算兩個(gè)相鄰長(zhǎng)度可重疊子塊的頻數(shù)時(shí)，設(shè)Yi(m)=(εi+1,εi+2,…,εi+m-1)，令：

式（1）中表示模式Y(jié)i(m)在待檢測(cè)序列中出現(xiàn)的相對(duì)頻數(shù)，πi表示模式l=(i1,i2,…,im)在待檢測(cè)序列中出現(xiàn)的相對(duì)頻率。待檢測(cè)序列長(zhǎng)度為n，m

序列檢測(cè)的執(zhí)行流程如下：

（1）將待檢測(cè)序列ε構(gòu)造成一個(gè)新的序列ε′，構(gòu)造方法是將序列ε最開始的m-1位數(shù)據(jù)添加到序列ε的結(jié)尾得到新序列ε′，新序列ε′的長(zhǎng)度為n′=n+m-1。

（2）計(jì)算ε′中所有的2m個(gè)m位子序列模式的出現(xiàn)頻數(shù)，記m位模式i1i2…im出現(xiàn)的頻數(shù)為vi1i2…im。對(duì)于所有的j(0≤j≤2m-1)，計(jì)算待檢測(cè)序列中出現(xiàn)的相對(duì)頻數(shù)。重復(fù)上述構(gòu)造過程，分別計(jì)算不同參數(shù)下ε′中所有的m位、m-1位、m-2位子序列模式的出現(xiàn)頻數(shù)。

（3）計(jì)算觀察到的m比特模式的頻數(shù)與預(yù)期模式頻數(shù)的匹配程度，即統(tǒng)計(jì)值。

（4）計(jì)算p-value值，設(shè)顯著性水平為α，如果p-value1≥α且p-value2≥α，則此序列通過序列檢測(cè)；否則，不通過檢測(cè)。

2.2 近似熵檢測(cè)

近似熵檢測(cè)與序列檢測(cè)方法相似，目的是比較序列中相鄰長(zhǎng)度的重疊子序列出現(xiàn)的概率是否和正態(tài)分布的序列中出現(xiàn)的概率情況接近，以此來判斷序列是否通過檢測(cè)[13]。近似熵檢測(cè)的執(zhí)行流程如下：

（1）將長(zhǎng)度為n的二元序列ε構(gòu)造成一個(gè)新的序列ε′，構(gòu)造方法與序列檢測(cè)相同，得到新序列ε′，新序列ε′的長(zhǎng)度為n′=n+m-1。

（2）計(jì)算ε′中所有的2m個(gè)m位子序列模式出現(xiàn)頻數(shù)vi1i2…im，對(duì)所有的j(0≤j≤2m-1)，計(jì)算待檢測(cè)序列出現(xiàn)的相對(duì)頻數(shù)，計(jì)算相對(duì)頻數(shù)方法與序列檢測(cè)中一致。

（4）用m+1代替m，重復(fù)操作（1）至（3），計(jì)算得到。

（5）計(jì)算熵ApEn(m)和統(tǒng)計(jì)值V。

（6）計(jì)算p-value值，設(shè)顯著性水平為α，如果p-value≥α，則認(rèn)為待檢序列通過近似熵檢測(cè)；否則，不通過檢測(cè)。

序列檢測(cè)和近似熵檢測(cè)方法相似，兩種檢測(cè)采用相同方法將待檢測(cè)序列構(gòu)造成新序列，并統(tǒng)計(jì)新序列中所有2m個(gè)m位子序列出現(xiàn)的頻數(shù)，兩種檢測(cè)計(jì)算得到的統(tǒng)計(jì)值均服從χ2分布。

3 兩種算法的效率分析與改進(jìn)

傳統(tǒng)隨機(jī)性檢測(cè)過程中將待檢測(cè)序列存儲(chǔ)和處理為數(shù)組，根據(jù)不同檢測(cè)算法的描述對(duì)單個(gè)比特進(jìn)行操作。例如在美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院發(fā)布的隨機(jī)性檢測(cè)包sts2.1.2中采用一種通用的方法來計(jì)算擴(kuò)張序列中所有可能出現(xiàn)的重疊mbit，首先定義具有2m+1-1個(gè)元素的數(shù)組變量p[]；將待檢測(cè)序列劃分成n m個(gè)非重疊子序列；定義局部變量k、i，再對(duì)每一個(gè)子序列，依次判斷每個(gè)單比特的值，若值為1，則令X=X+1，若值為0，則令X=2X+1；每個(gè)子序列計(jì)算結(jié)束后統(tǒng)計(jì)，令p[X-1]=p[X-1]+1，同時(shí)令k=1。這種對(duì)待檢測(cè)數(shù)據(jù)進(jìn)行單比特處理的操作方式，不僅浪費(fèi)CPU的字長(zhǎng)，而且當(dāng)檢測(cè)數(shù)據(jù)達(dá)到GB級(jí)時(shí)，這將是一個(gè)非常耗時(shí)的轉(zhuǎn)換過程。

通過分析兩種算法的執(zhí)行流程可知，序列檢測(cè)和近似熵檢測(cè)在計(jì)算過程中均統(tǒng)計(jì)了2m個(gè)m位子序列出現(xiàn)的頻數(shù)，因此對(duì)該過程的時(shí)間復(fù)雜度進(jìn)行分析。當(dāng)兩種檢測(cè)的空間復(fù)雜度相同時(shí)，采用一種特殊的數(shù)據(jù)結(jié)構(gòu)——二叉樹，分析該步驟的時(shí)間復(fù)雜度。首先，查找m位重疊子序列出現(xiàn)的頻數(shù)，就要構(gòu)造深度為m+1的滿二叉樹，滿二叉樹共有2m+1-1個(gè)節(jié)點(diǎn)，其節(jié)點(diǎn)中存放的信息是該節(jié)點(diǎn)代表的m位子序列出現(xiàn)的頻數(shù)。在統(tǒng)計(jì)序列中m位子序列出現(xiàn)的個(gè)數(shù)過程中，需要在有匹配信息時(shí)對(duì)應(yīng)節(jié)點(diǎn)內(nèi)容增加1，最后統(tǒng)計(jì)底層節(jié)點(diǎn)中存放的頻數(shù)。在統(tǒng)計(jì)頻數(shù)過程中每次向后移動(dòng)1 bit，它的時(shí)間復(fù)雜度為O(mn)。因此，在空間復(fù)雜度相同的情況下，兩種檢測(cè)計(jì)算待檢測(cè)序列中相鄰長(zhǎng)度重疊子序列頻數(shù)的時(shí)間復(fù)雜度為O(n)。

序列檢測(cè)和近似熵檢測(cè)在統(tǒng)計(jì)2m個(gè)m位子序列出現(xiàn)的頻數(shù)時(shí)，當(dāng)參數(shù)m=2時(shí)，序列檢測(cè)計(jì)算2位、1位重疊子序列出現(xiàn)的頻數(shù)，近似熵檢測(cè)計(jì)算2位、3位重疊子序列出現(xiàn)的頻數(shù)；當(dāng)參數(shù)m=5時(shí)，序列檢測(cè)計(jì)算5位、4位、3位重疊子序列出現(xiàn)的頻數(shù)，近似熵檢測(cè)計(jì)算5位、6位重疊子序列出現(xiàn)的頻數(shù)。在兩種檢測(cè)算法中存在大量重復(fù)的數(shù)據(jù)加載和計(jì)算過程，例如當(dāng)m=2時(shí)，兩種檢測(cè)算法各執(zhí)行一次（1）、（2）操作，如果將兩種檢測(cè)的部分?jǐn)?shù)據(jù)進(jìn)行復(fù)用，可以大大縮減檢測(cè)時(shí)間，提高檢測(cè)效率。

綜上所述，采用序列檢測(cè)和近似熵檢測(cè)對(duì)大量數(shù)據(jù)進(jìn)行檢測(cè)時(shí)，需要通過若干輪的比特轉(zhuǎn)換和逐比特的數(shù)值判斷和數(shù)學(xué)運(yùn)算才能得到統(tǒng)計(jì)值，因此對(duì)大量數(shù)據(jù)進(jìn)行兩種檢測(cè)的運(yùn)算量較大，執(zhí)行效率較低，檢測(cè)過程非常耗時(shí)。在實(shí)際應(yīng)用中，多數(shù)國(guó)家的隨機(jī)性檢測(cè)標(biāo)準(zhǔn)中均包含序列檢測(cè)和近似熵檢測(cè)，因此需要加快兩種檢測(cè)的運(yùn)行速度，以便快速篩查出不符合隨機(jī)性特征的序列。針對(duì)以上問題，本文采取下列方法快速實(shí)現(xiàn)兩種檢測(cè)算法：

（1）優(yōu)化字節(jié)處理方式，使用位級(jí)操作一次處理多個(gè)比特，提高CPU的利用率。

（2）根據(jù)檢測(cè)算法自身特點(diǎn)，按字節(jié)對(duì)m位可重疊子序列模式出現(xiàn)的頻數(shù)進(jìn)行預(yù)處理，將字節(jié)處理與相對(duì)頻數(shù)計(jì)算相結(jié)合。

（3）根據(jù)兩種算法自身特點(diǎn)合并兩種檢測(cè)方法，減少數(shù)據(jù)重復(fù)加載過程，避免冗余的計(jì)算過程。

4 優(yōu)化算法

4.1 兩種檢測(cè)算法優(yōu)化

序列檢測(cè)和近似熵檢測(cè)在計(jì)算m位子序列模式出現(xiàn)的頻數(shù)時(shí)，由于參數(shù)m無(wú)法確定，導(dǎo)致無(wú)法對(duì)字節(jié)中的重疊子序列進(jìn)行預(yù)處理，因此本文根據(jù)隨機(jī)性檢測(cè)經(jīng)驗(yàn)定義m=2,5。

本文中記ε=ε1||ε2||…||εL，1≤L≤n/8 為多個(gè)字節(jié)組成的待檢測(cè)數(shù)據(jù)，其中εi，1≤i≤L。為區(qū)分兩種參數(shù)下統(tǒng)計(jì)m位子塊的相對(duì)頻數(shù)情況，記為序列中m位子塊出現(xiàn)的相對(duì)頻數(shù)，其中1≤i≤2m。當(dāng)參數(shù)為m時(shí)，計(jì)算相對(duì)頻數(shù)的方式為：

優(yōu)化方法中#i的值采用創(chuàng)建字節(jié)表的方式獲取，當(dāng)參數(shù)m=2 時(shí)，記B=(#i,t)表示計(jì)算ε=ε1||ε2||…||εL這新序列L個(gè)字節(jié)中m位子序列出現(xiàn)的頻數(shù)，當(dāng)t為1時(shí)，B=(#i,1)表示字節(jié)ε1中00、01、10、11子序列出現(xiàn)的次數(shù)。B=(#i,t)可以通過查表統(tǒng)計(jì)，得到所有重疊子序列出現(xiàn)的頻數(shù)。在查詢字節(jié)表的過程中，如果上一次是使用序列中第i～i+7位進(jìn)行查表的，那本次將使用序列中第i+7～i+14位進(jìn)行查表。以參數(shù)m=2為例，序列檢測(cè)算法優(yōu)化過程如下：

算法1優(yōu)化實(shí)現(xiàn)序列檢測(cè)算法

輸入：待檢測(cè)序列ε=ε1||ε2||…||εL，1≤L≤n/8，參數(shù)m=2

輸出：序列是否通過序列檢測(cè)

1.初始化數(shù)據(jù)：#i=vi1i2…im=0

2.將序列最開始的m-1位添加到序列末端，構(gòu)成新序列ε′ ，即ε=ε1||ε2||…||εL→ε1||ε2||…||εL+m-1

3.L≤n/8時(shí)，查表計(jì)算B=(#i,t)，得到m位重疊子序列出現(xiàn)的頻數(shù)

4.重復(fù)步驟1～3，分別計(jì)算m-1、m-2位重疊子序列出現(xiàn)的頻數(shù)

6.計(jì)算p-value值，如果p-value≥0.01，序列通過檢測(cè)

近似熵檢測(cè)優(yōu)化過程中，參數(shù)m=2時(shí)，計(jì)算m位重疊子序列的方法與序列檢測(cè)相同，當(dāng)參數(shù)轉(zhuǎn)換為m+1=3時(shí)，查詢字節(jié)表的過程中，如果上一次是使用序列中i～i+7位進(jìn)行查表的，那本次將使用序列中第i+6～i+13位進(jìn)行查表。以參數(shù)m=2為例，近似熵檢測(cè)算法優(yōu)化如下：

算法2優(yōu)化實(shí)現(xiàn)近似熵檢測(cè)算法

輸入：待檢測(cè)序列ε=ε1||ε2||…||εL，1≤L≤n/8，參數(shù)m=2

輸出：序列是否通過近似熵檢測(cè)

1.初始化數(shù)據(jù)：#i=vi1i2…im=0

2.將序列最開始的m-1位添加到序列末端，構(gòu)成新序列ε′ ，即ε=ε1||ε2||…||εL→ε1||ε2||…||εL+m-1

3.L≤n/8時(shí)，查表計(jì)算B=(#i,t)，得到m位重疊子序列出現(xiàn)的頻數(shù)

4.重復(fù)步驟1～3，計(jì)算m+1位重疊子序列出現(xiàn)的頻數(shù)

5.計(jì)算近似熵ApEn(m)和統(tǒng)計(jì)值

6.計(jì)算p-value值，如果p-value≥0.01，序列通過檢測(cè)

4.2 兩種檢測(cè)算法合并優(yōu)化

將兩種檢測(cè)算法合并的過程中，字節(jié)統(tǒng)計(jì)結(jié)果可以在兩種算法之間復(fù)用。當(dāng)參數(shù)m=2時(shí)，兩種檢測(cè)同時(shí)需要統(tǒng)計(jì)2位子序列出現(xiàn)的次數(shù)；當(dāng)參數(shù)m=5時(shí)，兩種檢測(cè)同時(shí)需要5位子序列出現(xiàn)的次數(shù)；當(dāng)同時(shí)進(jìn)行參數(shù)m=2，5時(shí)，近似熵檢測(cè)可復(fù)用序列檢測(cè)中2位、3位、5位子序列查表結(jié)果。極大地減少了兩種算法的運(yùn)算量，提高兩種算法同時(shí)運(yùn)行的效率。下面以參數(shù)m=2為例，提出兩種檢測(cè)合并后算法。

算法3優(yōu)化實(shí)現(xiàn)兩種合并算法

輸入：待檢測(cè)序列ε=ε1||ε2||…||εL，1≤L≤n/8，m=1

輸出：檢測(cè)結(jié)果

1.初始化數(shù)據(jù)：#i=vi1i2…im=0

2.將序列最開始的m-1位添加到序列末端，構(gòu)成新序列ε′ ，即ε=ε1||ε2||…||εL→ε1||ε2||…||εL+m-1

3.L≤n/8時(shí)，查表計(jì)算B=(#i,t)，得到m位重疊子序列出現(xiàn)的頻數(shù)

4.令m+=1，m<4 ，重復(fù)步驟1～3，分別計(jì)算出1位、2位、3位重疊子序列出現(xiàn)的頻數(shù)

5.計(jì)算序列檢測(cè)統(tǒng)計(jì)量?Ψ2m、?2Ψ2m

6.計(jì)算近似熵檢測(cè)ApEn(m)和統(tǒng)計(jì)值

7.計(jì)算p-value1、p-value2、p-value3值，如果p-value≥0.01，序列通過檢測(cè)

5 實(shí)驗(yàn)結(jié)果

在實(shí)際應(yīng)用中產(chǎn)生隨機(jī)序列的方式主要分為兩類，一類是由偽隨機(jī)數(shù)發(fā)生器和密碼算法產(chǎn)生的偽隨機(jī)序列，偽隨機(jī)序列并不是真正意義上的隨機(jī)序列，它是由確定事件的概率組合產(chǎn)生的，因此偽隨機(jī)序列能夠被預(yù)測(cè)和重復(fù)。另一類是通過物理方法產(chǎn)生的真隨機(jī)序列，物理方法通過利用隨機(jī)“噪音”信號(hào)產(chǎn)生序列，例如熱力學(xué)噪聲、電噪音中提取隨機(jī)序列[14]。然而理論上經(jīng)典的物理過程在考慮所有環(huán)境變量的基礎(chǔ)上是可以模擬的，唯獨(dú)量子物理過程產(chǎn)生的隨機(jī)序列是完全真隨機(jī)序列。在量子隨機(jī)數(shù)發(fā)生器中，量子是無(wú)法繼續(xù)分割的，量子組成了光子、原子、電子，它是構(gòu)成物質(zhì)的最小微粒。量子隨機(jī)數(shù)具有隨機(jī)性主要原因是量子事件中測(cè)量坍縮造成的不確定性和真空起伏導(dǎo)致的隨機(jī)噪音，量子事件具有不確定性，量子隨機(jī)數(shù)發(fā)生器利用這一特性產(chǎn)生隨機(jī)序列[15]。因此，為保證實(shí)驗(yàn)數(shù)據(jù)可以通過兩種檢測(cè)，實(shí)驗(yàn)采用量子隨機(jī)數(shù)發(fā)生器產(chǎn)生的真隨機(jī)數(shù)。

本實(shí)驗(yàn)的測(cè)試平臺(tái)情況如表1所示。

表1 測(cè)試平臺(tái)信息

為更準(zhǔn)確地說明本文提出的算法的效率，設(shè)計(jì)實(shí)驗(yàn)測(cè)試優(yōu)化前后算法的執(zhí)行效率。測(cè)試數(shù)據(jù)是利用量子隨機(jī)數(shù)發(fā)生器生成的109bit的隨機(jī)數(shù)據(jù)，將隨機(jī)數(shù)據(jù)按106bit規(guī)格劃分為1 000條樣本數(shù)據(jù)。對(duì)比實(shí)驗(yàn)采用美國(guó)NIST官網(wǎng)發(fā)布的sts-2.1.2檢測(cè)包，該檢測(cè)包僅適用于Linux系統(tǒng)，為保證實(shí)驗(yàn)條件的一致性，本文按照該檢測(cè)包代碼思想，在Windows系統(tǒng)中實(shí)現(xiàn)兩種檢測(cè)算法。優(yōu)化后實(shí)驗(yàn)是對(duì)待檢測(cè)序列按照上述優(yōu)化算法，分別實(shí)現(xiàn)參數(shù)m=2及m=5時(shí)的兩種檢測(cè)及合并后的檢測(cè)，所有的算法均采用標(biāo)準(zhǔn)C實(shí)現(xiàn)，計(jì)時(shí)單位為ms。

參數(shù)m=2,5時(shí)選取實(shí)驗(yàn)中500條樣本，原序列檢測(cè)和近似熵檢測(cè)以及優(yōu)化后的算法1、算法2、算法3運(yùn)行時(shí)間如圖1～4所示。

圖1 m=2時(shí)原算法耗時(shí)間

圖2 m=2時(shí)優(yōu)化算法耗時(shí)間

圖3 m=5時(shí)原算法耗時(shí)間

圖4 m=5時(shí)優(yōu)化算法耗時(shí)間

實(shí)驗(yàn)結(jié)果如表2所示，參數(shù)m=2時(shí)，序列檢測(cè)優(yōu)化后速度提升了29.72倍，近似熵檢測(cè)優(yōu)化后速度提升了27.58倍；參數(shù)m=5時(shí)，序列檢測(cè)優(yōu)化后速度提升了30.02倍，近似熵檢測(cè)優(yōu)化后速度提升了24.14倍；參數(shù)m=2及m=5時(shí)兩種檢測(cè)合并后速度分別提升了40.12倍、45.23倍。

表2 算法性能對(duì)比

6 結(jié)束語(yǔ)

本文對(duì)NIST隨機(jī)性檢測(cè)標(biāo)準(zhǔn)中的序列檢測(cè)和近似熵檢測(cè)進(jìn)行快速實(shí)現(xiàn)。通過對(duì)字節(jié)的預(yù)處理、字節(jié)統(tǒng)計(jì)與相對(duì)頻數(shù)統(tǒng)計(jì)相結(jié)合、頻數(shù)統(tǒng)計(jì)優(yōu)化復(fù)用等方法，使得序列檢測(cè)和近似熵檢測(cè)速度最高分別提升30.02倍、27.58倍，兩種檢測(cè)合并后整體速度最高提升45.23倍。

本文提出的序列檢測(cè)和近似熵檢測(cè)優(yōu)化方案，有利于兩種檢測(cè)方法的推廣和應(yīng)用。隨機(jī)性檢測(cè)標(biāo)準(zhǔn)中還有很多其他檢測(cè)項(xiàng)可以做性能優(yōu)化及算法合并，這將是以后研究工作的一個(gè)方向。