Statistical-Test
計算不可區分性和非多項式算法的例子
關於計算不可區分性的維基百科頁面說，如果“任何非均勻機率多項式時間算法 A”無法將它們區分開來，則兩個集合是不可區分的。為了幫助我更好地理解定義，我搜尋了一個不符合上述限制的算法範例——特別是非多項式時間算法——它可以區分兩個計算不可區分的集合。令我驚訝的是，我沒有找到，所以我問，誰能給我一個例子？
我不是複雜性理論家，但我相信這符合要求。
最著名的因式分解算法是超多項式時間算法，因此它們不是多項式時間。超多項式時間算法可以區分的一個例子是Blum-Blum-Shub PRNG 的輸出。
以下是兩個非多項式時間的攻擊算法範例：
- 詳盡的搜尋。考慮一個迭代列舉所有可能鍵的算法，並檢查它是否正確。該算法的執行時間是非多項式的：對於一個 $ b $ -bit 密鑰，它將需要 $ 2^b $ 計算步驟，比任何多項式都大 $ b $ .
- 保理。最先進的因式分解算法的執行時間大於任何多項式 $ b $ ， 在哪裡 $ b $ 表示要分解的數字的位數。例如，一些因式分解算法的執行時間類似於 $ 2^{\sqrt{b}} $ ，它的增長速度比任何多項式函式都快 $ b $ . 據我們現在所知，沒有辦法在多項式時間內分解整數。
您正在考慮的定義僅涉及執行時間為多項式的攻擊算法，因此上述兩種攻擊被認為超出範圍（它們不被認為是密碼系統的“破壞”）。
*編輯 2/22：*在區分兩種機率分佈的情況下，如果你想要一個自然的例子，請嘗試詳盡的密鑰搜尋：為了區分 AES-CTR 輸出和真正的隨機，一種算法可能會嘗試所有可能 $ 2^{128} $ 鍵來查看它們是否與分佈中的觀察值匹配，如果匹配則輸出 1，否則輸出 0。該算法確實區分了兩個機率分佈，但它需要指數時間。（嚴格來說，我們應該把這個 $ b $ -bit 鍵，以便我們可以應用漸近執行時間，但無論如何，希望你能明白。）
PS 如果這有點多，並且您需要休息一下，請不要錯過 Eric Hughes 關於如何在聚會上進行數學講座的臭名昭著的建議（歌詞）。