在資訊安全與應用統計的世界中,隨機亂數的產生與使用是非常重要的一部分,無論是在模擬實驗、密碼學、統計抽樣還是機器學習等領域,都需要高品質的亂數來確保研究結果的可靠性。
本文將講解什麼是隨機亂數、如何產生隨機亂數、以及如何使用隨機亂數來驗證研究結果的可靠性。
什麼是隨機亂數 真隨機數與偽隨機數 真隨機數(True Random Numbers): 源自自然界的物理現象,如大氣噪音、放射性衰變等。具有真正的不可預測性,但產生速度較慢且成本較高。 偽隨機數(Pseudo-Random Numbers): 通過確定性演算法產生,具有週期性,但在統計特性上近似真隨機數。現代電腦應用中最常使用的形式。 理想亂數的統計特性 均勻分布性:在給定範圍內,每個數字出現的機率應相等 獨立性:各數字間不存在相關性 不可預測性:無法從前面的序列推測後續數字 可重現性:在相同種子值下可重現相同序列(針對偽隨機數) 基本亂數產生範例 以下是一些基本的亂數產生範例,比較需要注意的是以下程式碼有設定種子值以確保可重現性,每一次執行都會產生一樣的結果。
如果你只是要寫作業,把種子拿掉就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import randomimport numpy as nprandom.seed(42 ) np.random.seed(42 ) random_float = random.random() print (f"Random float: {random_float} " )random_int = random.randint(1 , 100 ) print (f"Random integer between 1 and 100: {random_int} " )sequence = ['A' , 'B' , 'C' , 'D' , 'E' ] random_choice = random.choice(sequence) print (f"Random choice from sequence: {random_choice} " )random.shuffle(sequence) print (f"Shuffled sequence: {sequence} " )
亂數產生演算法比較 在深入介紹各種演算法之前,我們先對常見的一些亂數產生演算法進行比較。
演算法特性總覽 演算法 優點 缺點 適用場景 週期長度 安全性 效能 線性同餘法 (LCG) - 實現簡單 - 計算速度快 - 記憶體需求小 - 可重現性好 - 週期有限 - 存在明顯的統計特性 - 容易被預測 - 在高維度上分布不均勻 - 簡單的模擬程式 - 教學範例 - 非關鍵性應用 m (模數) 低 極高 梅森旋轉演算法 (MT19937) - 極長週期 - 高維度均勻分布 - 通過大多數統計檢定 - 執行效率高 - 可重現性好 - 不適用於密碼學應用 - 狀態空間較大 - 初始化較慢 - 科學計算 - 統計模擬 - 一般應用程式 2¹⁹⁹³⁷-1 中 高 CSPRNG (Fortuna) - 密碼學安全 - 不可預測性高 - 抵抗統計分析 - 持續收集熵源 - 計算速度較慢 - 資源消耗較大 - 依賴系統熵源 - 密碼學應用 - 金鑰產生 - 安全憑證 理論上無限 高 中 系統 RNG (/dev/random) - 利用硬體熵源 - 真實隨機性 - 密碼學安全 - 速度不穩定 - 可能阻塞 - 依賴硬體品質 - 密碼學應用 - 系統安全 - 加密金鑰產生 理論上無限 高 低-中
進階特性比較 演算法 記憶體使用 可移植性 初始化時間 並行性 可重現性 熵來源 LCG 極低 極高 極快 好 完美 純演算法 MT19937 中等 高 中等 一般 完美 純演算法 CSPRNG 高 中等 慢 好 無 系統熵池 系統 RNG 依系統而定 低 慢 依實現而定 無 硬體熵源
選擇指南 如果不知道怎麼選擇,這裡提供了一些常見的使用情境。
應用場景 推薦演算法 選擇理由 注意事項 一般應用開發 MT19937 (通過語言標準庫) - 提供良好的隨機性 - 性能表現優異 - 使用方便 - 內建於多數程式語言 - 統計特性優秀 - 不適用於安全關鍵場景 - 需注意正確設定種子 - 建議使用語言標準庫實現 科學計算/模擬 MT19937 - 優秀的統計特性 - 極長週期性(2¹⁹⁹³⁷-1) - 高維度均勻分布 - 結果可重現 - 執行效率高 - 初始化較慢 - 狀態空間較大 - 需要合適的種子管理 密碼學應用 CSPRNG 或 系統 RNG - 提供密碼學安全性 - 不可預測性高 - 抵抗統計分析 - 持續收集熵源 - 適合產生金鑰和憑證 - 產生速度較慢 - 資源消耗較大 - 可能受系統熵池影響 - 需考慮熵源品質 教學/範例 LCG - 概念簡單直觀 - 實現容易 - 運算過程透明 - 適合理解原理 - 資源消耗極低 - 不適用於實際應用 - 統計特性較差 - 容易被預測 - 週期長度有限 遊戲開發 MT19937 或 Xoshiro256** - 產生速度快 - 統計特性良好 - 記憶體佔用適中 - 適合過程性產生 - 需要注意種子管理 - 考慮跨平台一致性 - 避免用於安全相關功能 大規模模擬 並行 PRNG (如 PCG) - 支援並行計算 - 性能優異 - 統計特性好 - 適合分布式系統 - 實現較複雜 - 需要額外的同步機制 - 結果重現性要求高
如果是一些特殊需求,這裡也有一些選擇建議。
特殊需求 推薦選項 替代方案 高性能要求 PCG、MT19937 Xoshiro256** 記憶體受限 LCG、Xoshiro128+ 簡化版 MT19937 密碼學安全 CSPRNG、系統 RNG ChaCha20 跨平台一致 MT19937 PCG 並行計算 並行 PRNG 獨立 MT19937 範例 過程性產生 MT19937 PCG 嵌入式系統 LCG、Xoshiro128+ 簡化版 PRNG
常見的亂數產生演算法 好,接下來,我們將繼續介紹每種演算法的具體實作細節和使用方法。
線性同餘法(Linear Congruential Generator, LCG) 最基本且廣泛使用的偽隨機數產生器,其遞迴公式為:
X(n+1) = (a * X(n) + b) mod m
其中:
a 為乘數 b 為增量 m 為模數 X(0) 則為種子值 但由於線性同餘法的內部狀態可以被簡單地從輸出逆推出,因此需要避免使用在高安全性的使用情境。
線性同餘法的範例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class LCG : def __init__ (self, seed, a=1664525 , c=1013904223 , m=2 ** 32 ): self.seed = seed self.a = a self.c = c self.m = m self.current = seed def next (self ): self.current = (self.a * self.current + self.c) % self.m return self.current def random (self ): return self.next () / self.m lcg = LCG(seed=42 ) for _ in range (5 ): print (f"Random number: {lcg.random():.6 f} " )
梅森旋轉演算法(Mersenne Twister) 現代最常用的高品質偽隨機數產生器之一,具有以下特點:
極長週期(219937 - 1) 高維度均勻分布性 通過大多數統計檢定 執行效率高 以下則是 Mersenne Twister 的 Python 簡單實作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 class MersenneTwister : def __init__ (self, seed=5489 ): self.w, self.n, self.m, self.r = 32 , 624 , 397 , 31 self.a = 0x9908B0DF self.u, self.d = 11 , 0xFFFFFFFF self.s, self.b = 7 , 0x9D2C5680 self.t, self.c = 15 , 0xEFC60000 self.l = 18 self.f = 1812433253 self.MT = [0 ] * self.n self.index = self.n + 1 self.lower_mask = (1 << self.r) - 1 self.upper_mask = (~self.lower_mask) & self.d self.seed_mt(seed) def seed_mt (self, seed ): """Initialize the generator from a seed""" self.index = self.n self.MT[0 ] = seed for i in range (1 , self.n): self.MT[i] = self.d & ( self.f * (self.MT[i - 1 ] ^ (self.MT[i - 1 ] >> (self.w - 2 ))) + i ) def twist (self ): """Generate the next n values from the series""" for i in range (self.n): x = (self.MT[i] & self.upper_mask) + \ (self.MT[(i + 1 ) % self.n] & self.lower_mask) xA = x >> 1 if x % 2 != 0 : xA = xA ^ self.a self.MT[i] = self.MT[(i + self.m) % self.n] ^ xA self.index = 0 def extract_number (self ): """Extract a tempered value based on MT[index]""" if self.index >= self.n: if self.index > self.n: self.seed_mt(5489 ) self.twist() y = self.MT[self.index] y = y ^ ((y >> self.u) & self.d) y = y ^ ((y << self.s) & self.b) y = y ^ ((y << self.t) & self.c) y = y ^ (y >> self.l) self.index += 1 return self.d & y def random (self ): """Generate a random float in [0, 1)""" return self.extract_number() / ((1 << self.w) - 1 ) if __name__ == '__main__' : mt = MersenneTwister() for _ in range (5 ): print (mt.random())
值得注意的是,numpy 與 CPython 就已經採用了 Mersenne Twister 作為預設的隨機數產生器
如果你想了解更多的資訊,可以參考 CPython 的 random.py 跟 numpy 的 bit_generators 。
密碼學安全偽隨機數產生器(CSPRNG) 如果你的隨機亂數在需要高安全性的使用情境中使用,那就最好使用 CSPRNG 來產生隨機數。
/dev/random(Linux系統) CryptoAPI(Windows系統) Fortuna演算法 HMAC-DRBG 如果你使用 Python,那可以使用 secrets 模組來產生安全的隨機數或 os 模組來使用系統隨機數功能。 以下是簡單範例。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import secretsimport osrandom_bytes = secrets.token_bytes(16 ) print (f"Random bytes: {random_bytes.hex ()} " )random_int = secrets.randbelow(100 ) print (f"Random integer below 100: {random_int} " )token = secrets.token_urlsafe(32 ) print (f"Secure URL-safe token: {token} " )os_random_bytes = os.urandom(16 ) print (f"OS random bytes: {os_random_bytes.hex ()} " )
亂數品質檢定 卡方檢定 卡方檢定是最常用的亂數品質檢定方法之一,主要用於檢驗亂數序列的均勻性。原理是比較觀察值與理論期望值之間的差異,判斷亂數是否具有良好的均勻分布特性。
以下是使用卡方檢定評估亂數品質的 Python 實作範例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 import numpy as npfrom scipy import statsdef chi_square_uniformity_test (numbers, bins=10 , confidence_level=0.05 ): """ 使用卡方檢定評估亂數序列的均勻性 參數: numbers: 要檢測的亂數序列 bins: 分箱數量 confidence_level: 顯著水準 返回: is_uniform: 是否通過均勻性檢定 p_value: p值 """ observed_freq, _ = np.histogram(numbers, bins=bins, range =(0 , 1 )) expected_freq = len (numbers) / bins chi_square_stat, p_value = stats.chisquare(observed_freq) is_uniform = p_value > confidence_level print (f"卡方檢定結果:" ) print (f"p-value: {p_value:.4 f} " ) print (f"檢定結果: {'通過' if is_uniform else '未通過' } (α = {confidence_level} )" ) print (f"自由度: {bins - 1 } " ) return is_uniform, p_value np.random.seed(42 ) random_numbers = np.random.random(1000 ) print ("測試 NumPy 隨機數產生器:" )chi_square_uniformity_test(random_numbers) def lcg_sequence (n, seed=42 , a=1664525 , c=1013904223 , m=2 ** 32 ): numbers = [] current = seed for _ in range (n): current = (a * current + c) % m numbers.append(current / m) return numbers print ("\n測試線性同餘法:" )lcg_numbers = lcg_sequence(1000 ) chi_square_uniformity_test(lcg_numbers)
卡方檢定的判斷準則:
若p值 > 顯著水準(通常為0.05),則不能拒絕虛無假設,表示亂數序列具有良好的均勻性 若p值 ≤ 顯著水準,則拒絕虛無假設,表示亂數序列的均勻性不夠理想 檢定結果解讀:
p值越大,表示亂數序列越接近理想的均勻分布 實務上,p值通常大於0.05即可認為亂數品質是可接受的 但p值過高(如0.99)也可能表示亂數不夠隨機 其他檢定方法 除了卡方檢定外,還有其他檢定方法可供參考:
Kolmogorov-Smirnov檢定 游程檢定 序列相關性檢定 譜分析檢定 結論 亂數產生與應用是現代資訊安全中不可或缺的組成部分。
本文通過理論講解和實際程式範例的結合,展示了亂數在不同領域的應用方法和最佳實踐。研究人員需要根據具體應用場景,選擇合適的亂數產生方法,並通過適當的統計檢定來確保亂數品質。
也許你也會想看看