偽隨機函式：函式是如何儲存的？
我想知道用於測試函式族是否是偽隨機的設置。我們走進一個房間，用 $ x $ ，產生 $ f(x) $ 等…我們不知道是否 $ f $ 是一個隨機函式，或者如果它來自某個預設函式族 $ F $ . 在後一種情況下，對 $ F $ ? 每個人都夠嗎 $ f $ 在 $ F $ 被列為黑匣子中的表格，因此 $ f: {0,1}^n \to {0,1}^n $ 被列為一個表 $ 2^n $ 條目？如果 $ f $ 由多項式的某個函式描述，其係數在 $ n $ ? 函式族中的函式有哪些限制 $ F $ ，如果有的話？
對於偽隨機性的定義，家庭 $ F $ of functions 可以是任何一組函式。但通常我們將其視為一個集合，其中每個函式都可以用一個相當短的鍵/種子來描述，並且可以在給定輸入（和鍵）的情況下有效地計算函式輸出。這是因為我們想要家庭 $ F $ 表示我們可以隨機選擇並在現實生活中使用的函式。
例如， $ F $ 可能是一組函式 AES $ _k $ , 接管所有 128 位字元串 $ k $ （其中 AES $ _k $ 表示帶有密鑰的 AES 分組密碼 $ k $ ）。請注意，有“僅” $ 2^{128} $ 這個家族的函式，遠少於128位到128位的函式個數（即 $ (2^{128})^{2^{128}} $ ).
偽隨機函式只需要產生“隨機”值，對函式沒有特殊限制。
有一些測試可以測量隨機函式的質量。這些測試將嘗試檢測函式的輸出是否以某種方式相關或有偏差。
一個著名的測試電池是 George Marsaglia 的Diehard Tests。或者你有更多最近的測試在這裡。
PS：通常隨機函式只會根據初始種子值生成隨機序列；您不必傳遞參數 $ x $ 每次呼叫該函式時。雖然確實存在這樣的隨機函式，但您描述中的框以某種方式讓我想起了雜湊函式（或隨機預言）。