陳 帥

(淮南師范學(xué)院 計算機與信息工程系，安徽 淮南232001)

在擴頻通信、信息加密和系統(tǒng)測試等實際應(yīng)用領(lǐng)域中采用了與隨機序列特性類似的偽隨機序列[1]。常用的偽隨機序列是基于線性反饋移位寄存器的m序列與同余序列(乘同余和線性同余)。

乘同余的隨機數(shù)發(fā)生器[2-3]：y(n+1)=(16807×y(n))mod(231-1)已被廣泛應(yīng)用，其周期為素數(shù)231－1＝2 147 483 647=2.147 483 647×109,直接進行該式的乘同余計算需要64位的整數(shù)除法運算。最簡單的方法是采用循環(huán)減法實現(xiàn)該同余序列運算中的整數(shù)除法，即采用將積循環(huán)減去模數(shù) 231-1，直到被減數(shù)小于模數(shù)231-1，則最后的被減數(shù)即為求得的同余數(shù)。采用循環(huán)相減的方法，若循環(huán)的次數(shù)多，必然會影響速度。為此，Montgomery[4]提出了一種求兩個大整數(shù)乘積的模的快速算法，算法不需要除法，只采用乘法、加法和右移位，即采用邊乘邊移位，其結(jié)果還需要進一步處理。如果參加乘積的數(shù)很大，則移位很多，必然降低運算速度。參考文獻[5]采用改變初始值設(shè)定，兩次調(diào)用該Montgomery算法實現(xiàn)形如 S=(x×y)mod N運算，即兩個大整數(shù)乘積的模的計算，但運算速度必然又大大降低。

現(xiàn)場可編程門陣列FPGA(Field Programmable Gate Array)編程靈活、修改方便，特別適用于流水線方式與并行方式的數(shù)據(jù)處理。在很多高速設(shè)計和高速測試的場合[6],能夠在FPGA中直接實現(xiàn)上述偽隨機序列發(fā)生器。傳統(tǒng)的實現(xiàn)乘同余產(chǎn)生偽隨機數(shù)的軟件方法時鐘頻率很低，而采用FPGA硬件實現(xiàn)則可以達到更高的速度。本文對該乘同余偽隨機序列提出了一種快速方法，該算法特別適合FPGA快速實現(xiàn)。

1 乘同余操作快速算法設(shè)計

快速算法流程圖如圖1所示。算法使用3個32位存儲單元，1個32位存儲器用于存儲常數(shù) 16 807，2個32位存儲器依次用于存儲乘法結(jié)果、移位結(jié)果、加法結(jié)果。此外采用了1個32位的乘法器、2個32位的加法器、少量移位操作和1個最高位分離器。算法步驟如下：

(1)將輸入值 y(n)與常數(shù)16807分別存入2個 32位存儲單元中。

(2)將步驟(1)中數(shù)據(jù)進行 32位乘法運算,乘積分別存入低32位存儲單元和高32位存儲單元中。

(3)將乘積的高32位存儲單元整體向高位移動1位(將乘積的最高位丟棄)，然后，將乘積的低 32位存儲單元的最高位移入乘積高32位存儲單元的最低位。

(4)將乘積的低32位存儲單元的最高位置為零值；

(5)將步驟(3)、(4)所得的 2個 32位存儲單元進行32位的加法運算得到32位的和值。

(6)將步驟(5)所得和值的高位（1或 0值）取出，存入另一32位存儲單元，將步驟(5)和值的最高位置為零值(最高位分離)。

(7)將步驟(6)所得 2個 32位存儲單元值相加，得到32位的和值，即為乘同余迭代操作計算值 y(n+1)=(16 807×y(n))mod(231-1)。

2 乘同余快速運算的驗證

采用FPGA功能仿真驗證乘同余的快速算法模型如圖2所示。在輸入時鐘信號clk的上升沿完成對輸入信號in[31..0]的一次乘同余計算，產(chǎn)生輸出信號out[31..0]， 輸出信號為：out[31..0]=(16 807×in[31..0])mod(231-1)，采用Verilog HDL硬件描述語言描述為：

FPGA設(shè)計實現(xiàn)的乘同余快速計算的仿真功能如圖3所示,T1時刻,輸入為0x00000002,在clk的上升沿進行計算：(16 807×2)mode(231-1)=0x834e;T2時刻,輸入為0x6fffffff,在 clk的上升沿進行計算：(16 807×0x6fffffff)mode(231-1)=0x0ffff7cb;T3時刻,輸入為 0x003fffff,在 clk的上升沿進行計算：(16 807×0x003fffff)mode(231-1)=0x69bfbe79;T4時刻,輸入為 0,在 clk的上升沿進行計算：(16 807×0)mode(231-1)=0;T5時刻,輸入為 0x00000006,在clk的上升沿進行計算:(16 807×6)mode(231-1)=0x000189ea?？梢?，F(xiàn)PGA仿真結(jié)果與人工計算一致，從而證明了乘同余快速算法的正確性。

2.2 乘同余序列的產(chǎn)生

為了連續(xù)產(chǎn)生乘同余序列，需要將上次產(chǎn)生的結(jié)果反饋輸入作為下次進行乘同余計算的輸入值。為此需要對乘同余算法添加選擇控制電路，F(xiàn)PGA才能實現(xiàn)序列發(fā)生器。設(shè)計的電路如圖4所示,其中選擇控制為快速乘同余計算選擇輸入的數(shù)據(jù)，在set=1時完成初始值預(yù)置輸入，在set=0時進行反饋輸入。

圖5為設(shè)計的FPGA電路功能仿真圖，F(xiàn)PGA采用EPF10K30ATC144-1。在T1時刻以前的set=1預(yù)置了初始值0x00000001，從而在T1時刻的時鐘clk的上升沿進行乘同余運算得到0x000041A7；在T2時刻的時鐘clk的上升沿，由于set=0,將0x000041A7代入進行乘同余運算得到0x10D63AF1；在T3時刻的時鐘clk的上升沿，由于set=0,將0x10D63AF1代入進行乘同余運算得到0x60B7ACD9;在T4時刻的時鐘clk的上升沿，由于set=0，將0x60B7ACD9代入進行乘同余運算得到0x3AB50C2A；在T5時刻的時鐘clk的上升沿,由于set=0,將0x3AB50C2A代入進行乘同余運算得到0x4431B782；在T6時刻開始set=1,故又重新預(yù)置初始值0x00000001，然后在T7時刻的時鐘clk的上升沿,將0x00000001代入進行乘同余運算得到0x000041A7；在T8時刻的時鐘 clk的上升沿，由于 set=0，將0x000041A7代入進行乘同余運算得到0x10D63AF1。

對計算乘同余序列：y(n+1)=(16 807×y(n))mod(231-1)的運算，提出了一種新的快速算法，算法包括1個32位乘法、2個32位加法、少量移位操作和1次最高位分離，不需要除法，只需乘法、加法、移位和最高位分離操作即可。在FPGA上設(shè)計了快速同余算法，功能仿真驗證了該算法的正確性。

[1]李飛飛,劉偉寧,王艷華.改進的中值濾波算法及其 FPGA快速實現(xiàn)[J].計算機工程,2009,35(14):175-177.

[2]楊波.網(wǎng)絡(luò)安全理論與應(yīng)用[M].北京:電子工業(yè)出版社,2002.

[3]張傳林,林立東.偽-隨機數(shù)發(fā)生器及其應(yīng)用[J].數(shù)值計算與計算機應(yīng)用,2002,23(3):188-208.

[4]PETER L.Modular multiplication without trial division.Mathematics of Computation,1985,44(170):519-521.

[5]陳政彣.于8051單芯片上實作RSA密碼系統(tǒng)之能量擊及防御措施[D].臺灣：資訊工程研究所,1993.

[6]束禮寶,宋克柱,王硯方.偽隨機數(shù)發(fā)生器的FPGA實現(xiàn)與研究[J].電路與系統(tǒng)學(xué)報,2003,8(3):121-124.