確定性和非確定性隨機位發生器的數學定義
誰能給出確定性和非確定性隨機位生成器的數學定義？
提供參考也將非常有幫助。
確定性隨機比特生成器是一個函式，它將一個秘密種子和可能的其他輸入作為輸入，並產生具有以下屬性的（長）輸出比特串：對於所有具有（多項式）有界計算能力的對手，輸出比特的分佈是不可區分的來自一個統一的、獨立的比特分佈。
我不認為真正的隨機位源有嚴格的“數學”定義（我想這就是你所說的“非確定性”），因為它需要定義現在被數學很好地捕捉到的東西（外部，熵的物理源）。
NIST 在其標準SP800-90Ar1 中將非確定性隨機位生成器定義為：
始終可以訪問熵源並且（在正常工作時）生成具有完整熵的輸出位串的 RBG。通常稱為真隨機數（或位）生成器。（與確定性隨機位生成器對比）。
涵蓋隨機性和隨機位生成器主題的一本很好的參考書是“隨機數生成器 - 原理和實踐”。
根據標準術語，確定性隨機位生成器是**偽隨機生成器。這被定義為確定性多項式時間算法 $ G $ 與關聯多項式 $ l $ （它的長度擴展因子），實現一個功能 $ G:{0,1}^\to{0,1}^ $ 這樣
- 對於所有輸入 $ s $ 它擁有 $ \mathbin|G(s)\mathbin|=l(\mathbin|s\mathbin|)>\mathbin|s\mathbin| $
換句話說，如果輸入位串²是 $ n $ -bit，輸出為 $ l(n) $ -bit 並且比輸入長。
- 對於任何多項式時間算法 $ D $ ，存在一個可忽略的²函式 $ \operatorname{negl} $ 使得對於任何整數 $ n $ $$ \Bigl|\Pr\bigl[D\bigl(G(s)\bigr)=1\bigr]-\Pr\bigl[D(r)=1\bigr]\Bigr|\le \operatorname{negl}(n) $$ 在哪裡 $ s $ 是均勻隨機的⁴ $ n $ -位串和 $ r $ 是均勻隨機的⁴ $ l(n) $ -bit 位串。
換句話說，沒有機率多項式時間算法可以區分輸出 $ G $ 從隨機的不可忽略的機率。
非確定性隨機位生成器可以在數學上定義⁴ 為具有指定隨機輸入的偽隨機生成器，就像機率算法的隨機輸入一樣。當計算機率的所有值 $ s $ 被考慮。
為簡單起見，輸入可以用它的位長代替 $ n $ （輸入 $ s $ 變得隱含地均勻隨機長度 $ n $ ).
或者，輸入可以是所需的輸出長度 $ m $ ( $ s $ 變得隱含一致隨機長度最低 $ n $ 這樣 $ l(n)\ge m $ ).
筆記：
¹：此定義等同於並改編自 Jonathan Katz 和 Yehuda Lindell 的《現代密碼學導論》中的定義。
²：記下任意有限長度的位串集 $ {0,1}^* $
³：一個可忽略的函式是 $ f:\Bbb N\mapsto\Bbb R^+ $ 這樣對於所有人 $ k\in\Bbb N $ 它擁有 $ \displaystyle\lim_{n\to\infty}f(n),n^k=0 $
⁴：如果算法 $ D $ 是機率的，機率是在所有隨機輸入上計算的 $ D $ 除了所有 $ s $ 或者 $ r $ .
⁵：這個定義是非標準的，我想不通。