可忽略函式的多項式和不必可忽略

讓 $ {\epsilon_i}{n \in \mathbb{N}} $ 是一系列可忽略的函式和 $ q(n) $ 成為多項式 $ n $ . 然後 $ f(n) = \sum{i = 1}^{q(n)} \epsilon_i(n) $ 不必是一個可忽略的函式。

想法

一個典型的可忽略函式是 $ 2^{-n} $ . 也許我們可以把它擴展到家庭 $ 2^{-(n+i)} $ 並設置 $ q(n) $ 可以提供足夠大筆款項的東西

$$ didn’t work $$

考慮可忽略的函式 $$ \epsilon_i(n) = \begin{cases} 1 & \text{if } n \le i \ 0 & \text{if } n > i \ \end{cases} $$

和 $ q(n) = n $

應該很容易證明每個 $ \epsilon_i $ 實際上，函式可以忽略不計，但總和 $ f(n) $ 不是…

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