隨機亂數生成演算法獲突破

一般的隨機算法為了提高隨機性會在演算法中引入環境的隨機性,比如滑鼠或鍵盤的位置等。電腦會採樣若干時間點的滑鼠位置然後轉化為一串數字。但這仍然算不上真正的隨機,比如前一刻滑鼠位置如果是在螢幕左側的話,下一刻滑鼠跑到右側的可能性是很低的。因此這樣生成的隨機亂數序列仍然具有相關性的,或者是可能會偏向特定值的。也就是說,這種隨機性還是很弱。
評論
11-10-09: Dice
11-10-09: Dice
評論

本文來自於  sciencenews.org《New technique produces real randomness》,36 氪 翻譯

隨機亂數在軟體的應用非常廣泛。比如說抽獎程式就是一下能想到的應用之一。但是在一些更加重要的應用當中隨機亂數也發揮著重要的作用,比如加密敏感訊息、對地球天氣等複雜系統建模以及數據的公正採樣等都離不開隨機亂數。

不過電腦生成隨機亂數要比擲骰子困難得多,而且那些隨機亂數實際上並不是完全不可預測的,而是在隨機種子的基礎上結合演算法自動生成的「數」,這些「數」實際上是可複製的,算不上真正的隨機(偽隨機亂數)。所以隨機亂數的隨機性問題是基礎演算法面臨的一大難題。

不過最近德州大學的兩位電腦科學家 Eshan Chattopadhyay 和 David Zuckerman 開發出了一種改進的隨機抽樣器,這種算法只需要兩種隨機性不強的來源即可生成真正隨機的數字,被認為是基礎算法取得的一大突破。

一般的隨機算法為了提高隨機性會在演算法中引入環境的隨機性,比如滑鼠或鍵盤的位置等。電腦會採樣若干時間點的滑鼠位置然後轉化為一串數字。但這仍然算不上真正的隨機,比如前一刻滑鼠位置如果是在螢幕左側的話,下一刻滑鼠跑到右側的可能性是很低的。因此這樣生成的隨機亂數序列仍然具有相關性的,或者是可能會偏向特定值的。也就是說,這種隨機性還是很弱。

而隨機抽取器則是通過這些隨機性較弱的來源來發掘隨機性。用 MIT 電腦科學家 Dana Moshkovitz 的話來說,隨機性是一種資源,獲取隨機性的過程就像是挖金礦一樣—先開採礦石,然後排沙篩金。

而兩位科學家的算法是對隨機抽樣器的改進。這種隨機抽取器將兩種獨立的弱隨機亂數來源組合為一個接近隨機的集合,並且只有細微偏差。然後再利用彈性函數(一種訊息組合方法)將一串數字轉化為真正的隨機位 —1 或 0。

利用彈性函數進行訊息組合可以防止偏差的出現。比方說在大選裡面,一些蓄意的投票者有可能會把結果引向想要的方向。但彈性函數可以保護誠實的投票者。因為它不是選取簡單多數,而是先把數據分成 3 組,然後選取每組中的多數,再把選出來的數分成 3 組然後再抽取每組中的多數,以此類推直到最後。這種做法使得選舉可以容忍大量盲點的存在,而在隨機亂數生成方面,這種做法可以把偏差數過濾掉。

跟以往需要接近隨機輸入的隨機抽取器相比,這種新的辦法正是通過在隨機性非常非常弱的來源當中「淘金」來挖掘真正的隨機亂數,從而實現了隨機性的實質性改進,其結果已經接近於理想情況。對於加密、複雜系統模擬等應用來說,這是一個非常好的消息。

歡迎加入「Inside」Line 官方帳號,關注最新創業、科技、網路、工作訊息

好友人數


精選熱門好工作

高階平台開發者 / Sr. Platform Developer

奔騰網路科技有限公司
臺北市.台灣

獎勵 NT$15,000

社群行銷企劃

尹星知識管理顧問股份有限公司
臺北市.台灣

獎勵 NT$15,000

Product Designer

新加坡商拍拖有限公司台灣分公司
臺北市.台灣

獎勵 NT$15,000