Provable-Security
1/(2^n)！是微不足道的功能嗎？
根據定義 $ \frac {1} {n} $ , $ \frac{1}{2^n} $ 和 $ \frac{1}{n!} $ 是可以忽略的函式。
我有這個功能 $$ f(n) = \frac{1}{(2^n)!} $$在哪裡 $ n $ 是安全參數。
我不明白，我如何正式證明這一點$$ \frac{1}{(2^n)!} $$是一個可以忽略的函式嗎？誰能幫幫我？
證明函式的最簡單方法 $ f $ 如果明顯可忽略，則可忽略是為了表明它比某些其他函式“更可忽略” $ g $ 您已經證明可以忽略不計，例如 $ g(n)=2^{-n} $ .
因為 $ g $ 可以忽略不計，存在 $ n_{g_0} $ 這樣對於所有人 $ n>n_{g_0} $ 它認為 $ g(n)<1/{n^c} $ 對於任何固定的選擇 $ c $ .
現在你可以通過證明存在一些來利用它 $ n_{f_0} $ 這樣對於所有人 $ n>n_{f_0} $ 它認為 $ f(n)\leq g(n) $ . 顯然，它對所有人都適用 $ n>\max(n_{f_0},n_{g_0}) $ 那 $ f(n)\leq g(n)<1/n^c $ 意思是 $ f $ 可以忽略不計。
我會留下選擇 $ g $ 為您的具體應用。