辨識可忽略的函式

我很難理解和應用用於辨識函式的公式是否可以忽略不計？

• 一個文本將其定義為；一個函式 $ f $ 如果對於每個正多項式，從自然數到非負實數可以忽略不計 $ p $ 有一個 $ N $ 這樣對於所有整數 $ n > N $ 它認為 $ f(n) < 1/p(n) $ .
• 另一本教科書將其定義為；一個函式 $ f $ 如果，對於每個多項式，則可以忽略不計 $ p $ ， 我們有 $ \lim_{\lambda \rightarrow \infty} p(\lambda)f(\lambda)=0 $

例子： $ 1/2^{\lambda/2} $ 這會被認為是微不足道的功能嗎？

首先讓我回顧一下指數函式的定義和一些性質。基中的指數函式 $ a $ 定義如下： $ \exp_a(x) = a^x $ . 如果 $ a>1 $ , 這樣的函式增長速度比任何多項式都快 $ p(x) $ . 更正式地，該屬性以以下兩種方式解釋。

• 1. 對於任何多項式 $ p $ 和任何依據 $ a>1 $ ， 那裡存在 $ N $ 這樣對於所有人 $ n\geq N, \exp_a(n) > p(n) $ .
• 2. 對於任何多項式 $ p $ 和任何依據 $ a>1 $ , $ \lim_\limits{x \rightarrow \infty} \frac{\exp_a(x)}{p(x)} = \infty $ （所以 $ \lim_\limits{x \rightarrow \infty} \frac{p(x)}{\exp_a(x)} = 0 $ )

現在，我們注意到函式 $ h(\lambda) = 2^{\lambda/2} $ 是指數函式，因為 $ h(\lambda) = 2^{\lambda/2}=\left(2^{1/2}\right)^\lambda= \sqrt{2}^\lambda =\exp_{\sqrt{2}}(\lambda) $ . 最後，你的功能是 $ f(\lambda) = \frac{1}{\exp_{\sqrt{2}}(\lambda)} $ . 下面，我們將證明 $ f $ 使用這兩個定義可以忽略不計。

• 1. $ \sqrt{2} >1 $ , 所以對於任何多項式 $ p $ ， 那裡存在 $ N $ 這樣對於所有人 $ n\geq N, \exp_\sqrt{2}(n) > p(n) $ ，這意味著對於所有 $ n\geq N, \frac{1}{\exp_\sqrt{2}(n)} < \frac{1}{p(n)} $ . 自從 $ f(\lambda) = \frac{1}{\exp_{\sqrt{2}}(\lambda)} $ , 我們為所有人推斷出 $ n\geq N, f(n) < \frac{1}{p(n)} $ .
• 2. $ \sqrt{2} >1 $ , 所以對於任何多項式 $ p $ , $ \lim_\limits{\lambda \rightarrow \infty} \frac{p(\lambda)}{\exp_\sqrt{2}(\lambda)} = 0 $ . 自從 $ \frac{p(\lambda)}{\exp_\sqrt{2}(\lambda)} = p(x) \frac{1}{\exp_\sqrt{2}(\lambda)} = p(\lambda) f(\lambda) $ , 我們推斷 $ \lim_\limits{\lambda \rightarrow \infty} p(\lambda) f(\lambda) = 0 $

總而言之，直覺是多項式除以增長速度比任何多項式都快的東西是一個可忽略的函式，因為它很快就會變得非常小。

從第一個定義；

要看到一個函式可以忽略不計，你必須找到一個 $ n >N $ 對於每個正多項式 $ p(n) $ 這樣之後 $ f(n) < 1/p(n) $ 是持有。這裡有兩個例子；

• 考慮 $ p(n)= 10^6 $ 然後 $ n \geq 800 $ 然後 $ 1/2^{800/2} = 1/1048576 < 1/10^{-6} $
• 考慮 $ p(n)= 10^{3} $ 然後 $ n \geq 200 $ 然後 $ 1/2^{200/2} = 1/1024 < 1/10^{-3} $

從第二個定義； $ \lim_{\lambda \rightarrow \infty} p(\lambda) f(\lambda) =0? $

為您 $ f(\lambda) = 1/2^{\lambda/2} $ 我們必須看到，無論多項式，極限都是 0 $ p(\lambda) = a_n \lambda^n +\ldots + a_0 $

$$ \lim_{\lambda \rightarrow \infty} p(\lambda)f(\lambda) = \frac{p(\lambda)}{2^{\lambda /2 }} = \lim_{\lambda \rightarrow \infty} \frac{a_n \lambda^n +\ldots + a_0}{2^{\lambda /2 }} = 0, $$

因為如果你接受L’Hôpital 的規則 $ n $ - 乘以分子為 1 並最終為零。然而，分子趨於無窮大。

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