非常大（10^1.2mil）數的僞隨機算法？

-1

我正在尋找一個僞隨機數發生器（一種算法，你輸入一個種子數，它輸出一個不同的'隨機看'的數字，並且相同的種子總是會產生相同的輸出） 95 ^1,312,000。非常大（10^1.2mil）數的僞隨機算法？

我會使用Linear Feedback Shift Register (LFSR) PRNG，但如果我這樣做了，我將不得不將種子編號（可能長達120萬位數的基數爲10）轉換成二進制數，這將會非常大我認爲計算需要很長時間。

作爲對similar question的迴應，推薦使用Feistel密碼，但我不明白該方法的wiki頁面的詞彙表（我將進入10年級，因此我沒有加密學位），所以如果你可以使用外行的條款，我會非常感激。

有沒有一種有效的方式來做到這一點，直到時間結束纔會採取，或者這個問題是不可能的？

編輯：我忘了提到，prng序列需要有一個完整的時期。我的錯。

2017-08-01 Ike Bishop

歡迎來到SO :)我沒有投票，但我想你是因爲其中一個原因：（1）在這個問題中太多的無關信息，即使你已經「隱藏」它，（2）它就像你問了一堆問題，所以目前還不清楚你真正想要什麼，這讓我覺得（3）你正在遭遇一個[XY問題]的困擾（https://meta.stackexchange.com/questions/66377/what -is-的-XY-問題）。嘗試編輯您的問題以符合[好問題]的社區標準（https://stackoverflow.com/help/how-to-ask），並且獲得幫助將會更容易。 – HFBrowning

澄清 - 我不相信你需要一個隨機數字發生器，你對你實際要做的事情的解釋很混亂 – HFBrowning

是的，請將這個問題簡化爲你需要解決的問題。嘗試寫一個簡單的庫問題描述，然後簡要描述當前的研究和實現問題。總之*爲什麼*，其次是*如何*。 – Prune

一個簡單的方法是使用linear congruential generator，模數m = 95^1312000。發電機的公式爲x_(n+1) = a*x_n + c (mod m)。根據赫爾 - 多貝爾定理，當且僅當gcd(m,c) = 1和95除以a-1時，它將具有全部週期。此外，如果你想要很好的第二個值（即在種子之後），即使是非常小的種子，a和c也應該相當大。此外，您的代碼不能存儲這些值作爲文字（他們會太大）。相反，您需要能夠在飛行中可靠地製作它們。有點試驗和錯誤，以確保gcd(m,c) = 1後，我突發奇想：

import random 

def get_book(n): 
    random.seed(1941) #Borges' Library of Babel was published in 1941 
    m = 95**1312000 
    a = 1 + 95 * random.randint(1, m//100) 
    c = random.randint(1, m - 1) #math.gcd(c,m) = 1 
    return (a*n + c) % m

例如：

>>> book = get_book(42) 
>>> book % 10**100 
47797469195027531423235726984781379963232069671941973329985178287714271555822878919350677

顯示最近100個位數的考慮「書」號42 Python的內置支持大整數，代碼運行速度驚人地快（在我的機器上拿一本書只需不到1秒鐘的時間）

來源

2017-08-02 18:40:07

我們如何保證'c'和'm'不會共享1以外的其他因素？似乎如果'c'可能是'1'和'm-1'之間的任何數字，'c'可能至少與'm'共享一個公因式。此外，非常感謝您的迴應 –

@IkeBishop'c'是一個特定的數字，由種子決定（1941年，選自百靈）。我用'm'測試了它是相對的，最初使用'math.gcd（）'，雖然只需檢查'c％5'和'c％19'都不爲零。 –

對，我誤以爲每次你運行代碼時'c'和'a'都會有所不同，但你是對的。我認爲這個故事發表的那一年恰好是一個能夠產生LCG整個時期的種子。非常聰明，謝謝！ –

如果你有一個方法可以產生一個僞隨機數字，那麼你可以將多個連接在一起，只要你想。它將和基本的prng一樣可重複。

但是，您可能會用盡內存縮放，高達數百萬位數並嘗試進行算術運算。通常這種規模的東西不是在「數字」上完成的。它是在字節向量或類似的東西上完成的。

來源

2017-08-02 00:06:38 recursive

當連接成一個大數字時，一般選擇的RNG將不會充分隨機。第一個** M **數字將唯一地指示剩下的** MN **，其中N >> M. – Prune

我認爲這樣可以，因爲問題表明一個LFSR將是合適的，它將具有相同的屬性。 – recursive

這是一個很好的觀點。然而，在這個問題中，我忘記提到prng序列需要一個完整的階段（我的不好）。連接方法是否工作並且仍然會產生一個完整的週期？ –

非常大（10^1.2mil）數的僞隨機算法？

回答

相關問題