使用散列函式作為隨機數生成器
例如，使用 MD5 或 SHA1，並按順序將整數（可以說是種子）應用於雜湊函式，並且只保留結果雜湊的前 64 位，我們是否總是有接近 $ 1/{2^{64}} $ 具有$$ \text{hash}{64}(n) = \text{hash}{64}(n+1) $$對於每個 $ n\in\big[1,2^{64}] $ ?
警告：這個答案是我在Vulcan模式下寫的。也就是說，我按字面意思回答這個問題（在第一部分）；或僅在一個小變體中（第二部分）；並忽略問題的標題，我認為這無關緊要，尤其是考慮到 $ n $ .
考慮的機率是 $ 0 $ 對於許多不同的常用定義方法中的每一種 $ \text{hash}_{64}(n) $ 作為整數的 MD5 或 SHA-1 的前 64 位 $ n $ . 無論 $ 0 $ 是*“接近 $ 1/2^{64} $ “*是見仁見智的問題。
對於其他一些定義 $ \text{hash}_{64}(n) $ , 這個機率是 $ 1 $ ，這不是*“接近 $ 1/2^{64} $ “*許多人認為。
理由：被認為是機率 $ p $ 那對於每個 $ n $ 在 $ \big[1,2^{64}\big] $ 它擁有 $ \text{hash}{64}(n)=\text{hash}{64}(n+1) $ .
對於固定功能 $ \text{hash}{64} $ 這是某個確定的事實是否成立的機率，因此 $ p $ 或者是 $ 0 $ 或者 $ 1 $ 取決於功能 $ \text{hash}{64} $ . 這也成立（也許有不同的 $ p $ ) 如果我們將every更改為some。
對於定義函式的許多不同的常用方法 $ \text{hash}{64} $ 對於作為該整數的 MD5 或 SHA-1 的前 64 位的整數參數，該機率為 $ 0 $ . 例如，如果我們定義 $ \text{hash}{64} $ 為最短大端十進製表示的 SHA-1 的前 64 位 $ n $ 用 ASCII 編碼，然後 $ \text{hash}{64}(1) $ 是單字節 0x31 的 SHA-1，即 b6589…8410ch ，而 $ \text{hash}{64}(2) $ 是單字節 0x32 的 SHA-1，即 da4b…0b0ch ，因此它們不匹配。
我們可以嘗試使用 MD5 和 SHA-1，各種常見的基數（包括 2、8、10、16、64、256、2 32）、常見的合適字母（ASCII、EBCDIC、二進制、字節）和常見的變體（大寫或小寫） hex，各種base64習語），字節序（大，小，各種混合）和寬度 $ n $ （固定為 64，但有一些例外 $ n=2^{64} $ , 65, 72 or 96 bits, 自適應根據 $ n $ 具有各種步驟，例如十六進制常見的步驟）。但我不相信我們會找到這樣的 $ \text{hash}{64} $ 和 $ \text{hash}{64}(1)=\text{hash}{64}(2) $ . 我已經準備好賭房子了 $ \text{hash}{64}(2)=\text{hash}_{64}(3) $ 不會另外持有。
當我們對所有可能定義的機率求平均時 $ \text{hash}_{64} $ ，我們得到 $ 2^{\left(64-2^{70}\right)} $ . 這是一個可笑的小數字，但不是零。
現在也許我們應該考慮機率 $ p $ 那對於一個隨機的 $ n $ 在 $ \big[1,2^{64}\big] $ 它擁有 $ \text{hash}{64}(n)=\text{hash}{64}(n+1) $ .
那個機率 $ p $ 是 $ k/{2^{64}} $ 對於某個整數 $ k $ ，這可以通過顯著但可行的努力從精確定義中計算出來 $ \text{hash}_{64} $ .
當我們平均 $ p $ 在所有可能的定義中 $ \text{hash}_{64} $ ，我們得到 $ 1/2^{64} $ ; 因此*“接近 $ 1/2^{64} $ “*當然。
我們也可以定義機率 $ p_k $ 那 $ p $ 是 $ k/{2^{64}} $ 對於隨機函式 $ \text{hash}{64} $ ，這是一個合理的模型，適用於各種 $ \text{hash}{64} $ 問題認為。最大的 $ p_k $ 是 $ p_1 $ （意義 $ p=1/{2^{64}} $ 是最有可能的），與 $ p_0 $ 非常接近第二，兩者都非常接近 $ 1/e\approx36.8% $ . $ p_2 $ 大約是一半，並且 $ p_k $ 快速下降 $ k $ 增長，下降到 $ p_{2^{64}}=2^{\left(-2^{70}\right)} $ ， 然後 $ p_k=0 $ 為了 $ k>2^{64} $ . 它擁有 $ 1=\sum p_k $ .
我們看到 $ p $ 是在三元素集中 $ {0,1/2^{64},1/2^{63}} $ 機率約為 $ 5/2e\approx92.0% $ . 我們可以說 $ p $ 很多時候*“接近 $ 1/2^{64} $ ”*。