在下一個位測試

我想知道什麼 $ O(v(n)) $ 真正的意思是詳細而簡單的詞。我在我正在審查的文獻中到處都能找到它，但我找不到它的直覺（特別是如果它意味著大 O 表示法，那麼它與這裡的機率有什麼關係；還有什麼是 $ v $ ，除非在另一篇論文中將其定義為常數-但可能與此公式中的 v 沒有直接關係-)。

非常感謝。

參考文獻 1 , 2

但是這個符號是在第一篇論文中（非正式地）定義的。

符號 $ O(\nu(n)) $ 用於任何功能， $ f(n) $ ，它的消失速度比任何多項式的逆都快，即對於每個多項式， $ \mathrm{poly} (n) $ ， 和 $ n $ 足夠大， $ f(n) \leq 1/\mathrm{poly}(n) $

因此，它的意思是沒有機率多項式時間（PPT）算法 $ A $ 可以以逆多項式遞減錯誤率的方式猜測下一位。

給定任何 PPT 算法 $ A $ 該錯誤機率以超多項式方式衰減，例如以一定速率衰減 $ \exp(-\log^2 n) $ 它比任何多項式都更快地歸零。

宣稱： $ \exp(-\log^2 n) $ 小於 $ n^{-c} $ 對於任何常數 $ c $ 為了 $ n $ 足夠大。

*證明：*看倒數。$$ \exp(\log^2 n) > n^c $$當且僅當 $$ \log^2 n > c \log n $$這顯然會盡快發生$$ \frac{\log^2 n}{\log n}>c $$即，盡快 $ \log n>c $ .

注意 $ \exp(\log^{1+\epsilon} n) $ 是所有的超多項式 $ \epsilon>0. $

**編輯：**超多項式收斂本質上就是所謂的可忽略性。

引用自：https://crypto.stackexchange.com/questions/83657