Abstract
亂數的產生對於許多應用來說是必需且相當重要的，例如蒙地卡羅模擬和通訊系統。近年來，因著資訊安全相關應用的大量需求，非線性偽亂數產生器已引起廣泛的重視。然而，要設計一系列具有高輸出率、長週期及小面積之非線性偽亂數產生器是相當有挑戰性的。在本論文中，我們提出兩種轉換的方法，將一系列有效率的線性多重遞迴產生器 (我們稱之為DX產生器)，轉換成非線性的偽亂數產生器。為了硬體能有效率的被實現-特別是記憶體的使用，我們找到新的低次?之DX產生器。其次?低於24，並且其模數是32位元中最大的質數231-1。專特的來講，我們提出一個全新重植-混合的方法來延長混沌邏輯斯諦映射(Logistic map) 偽亂數產生器的週期及改善其統計特性。重植的方法消除在數位化的邏輯斯諦映射中之短週期現象，而混合的方法則是藉由異或邏輯匣與DX產生器作混合後，可將週期大大提昇至2253。相較於其他的非線性偽亂數產生器，新的重植-混合偽亂數產生器可以達到6.4Gbit/s的高輸出率。在這樣高的輸出率之下，所產生的亂數序列仍然成功的通過美國國家標準技術研究院 (National Institute of Standards and Technology, NIST) 所發展之SP800-22的擬亂數統計檢測。另外，我們藉由數學理論的推導，將此一系列所提出之重植-混合偽亂數產生器的最低週期算出。為了進一步降低硬體的成本，我們題出另一洗牌-隱藏的方法將DX產生器轉換成非線性偽亂數產生器。當我們用台積電0.18μm的製程來實現，所提出的洗牌-隱藏非線性偽亂數產生器可達到6.4Gbit/s的高輸出率及9.254 × 10223之長週期。不僅通過美國NIST SP800-22的檢測，所提出的非線性偽亂數產生器在單位邏輯匣中所產生的輸出率及單位邏輯匣中所產生的週期長度之表現上皆優於文獻中的非線性偽亂數產生器。另外，我們藉由下一個數的預測子 (Next Number Predictor) 嘗試提出一套關於多重遞迴產生器 (MRG) 及所提出之非線性偽亂數產生器的安全度分析方法。藉由這些良好的特性，我們相信我們所提出的這些偽亂數產生器及其變型可以符合需要考量安全度之應用的需求。