Cryptanalysis
可忽略函式1！_1n!frac{1}{n!}
是 $ \frac{1}{n!} $ 一個可以忽略的函式 $ n $ 是安全參數嗎？
應用：我有一個 n>100 個元素的向量。我將其置換並交給對手。如果對手能找到向量的原始順序，它就可以破壞它。它成功的機率是： $ \frac{1}{n!} $ . 因此，我需要知道這個機率是否可以忽略不計。
提示：你可以注意到 $ n! > 2^n $ （除了非常小的 $ n $ ).
是的，一個函式 $ f $ 如果對於每個多項式函式，則稱其可忽略不計 $ p(n) $ 存在一些常數 $ N $ 這樣 $ f(n) < \frac{1}{p(n)} $ 對所有人 $ n > N $ .
如果 $ \frac{1}{n!} < \frac{1}{p(n)} $ 然後 $ n! > p(n) $ , 對於所有多項式 $ p(n) $ 並且適合 $ N $ 這樣 $ n>N $ . 因此，您只需要證明陳述的第二部分。
最 簡單的解決方案是注意 $ n! $ 可以通過斯特林近似近似為
$$ \sqrt{2\pi n}\bigg(\frac{n}{e}\bigg)^n $$所以$$ \frac{1}{n!} = \frac{1}{\sqrt{2\pi n}\bigg(\frac{n}{e}\bigg)^n} $$這顯然是一個指數衰減函式，因此總是小於任何多項式函式 $ p(n) $ 對於這樣的 $ n>N $ 適合 $ N $ .