可忽略函數

在數學中，可忽略函數（英語：Negligible function）是指

對於一個函數 $\mu (x):\mathbb {N} {\rightarrow }\mathbb {R}$ ，如果對於任意一個正多項式$poly()$，存在一個$N_{c}>0$，使得對於所有的$x>N_{c}$

$\mu (x)<{\frac {1}{poly(x)}}$

那麼這個函數便是可忽略的（negligible）。通常我們把「存在一個$N_{c}>0$，使得對於所有的$x>N_{c}$」簡化為「對於所有足夠大的$x$」。

歷史

可忽略函數這個概念是和數學分析的形式化模型相關的。第一個比較嚴格的定義是波爾查諾在1817年給出的。後來的柯西, 魏爾施特拉斯和海涅都用了基本相同的以下定義：

（連續函數） 一個實數函數$f(x)$在$x=x_{0}$處連續，當對於任意一個正實數$\epsilon >0$，有一個正實數$\delta >0$，使$|x-x_{0}|<\delta$時，有$|f(x)-f(x_{0})|<\epsilon$。

只要每步改變一項參數，此定義就可經數步轉換成為可忽略函數的定義。首先，當$x_{0}=\infty ,f(x_{0})=0$時，我們需要定義"足夠大"（sufficiently large），並定義無窮小量：

（足夠大） 實數$x$足夠大時一個數學命題為真，當且僅當存在一個實數$N_{c}>0$，對所有的實數$x>N_{c}$此數學命題為真。

（無窮小） 一個連續函數$\mu (x)$無窮小，當對任意足夠大的正實數$x$，對任意正實數 $pnum={\frac {1}{\epsilon }}>0$，有

$|\mu (x)|<\epsilon ={\frac {1}{pnum}}$。

然後我們把正實數$\epsilon$換成正實數多項式函數$\epsilon (x)$。

（可忽略函數） 一個連續函數$\mu (x)$可忽略，當對任意足夠大的正實數$x$，對任意正多項式$poly(x)={\frac {1}{\epsilon (x)}}>0$，有

$|\mu (x)|<\epsilon (x)={\frac {1}{poly(x)}}$。

在基於計算複雜性理論的現代密碼學中，一個安全技術是數學上可證明安全（provably secure）的意思通常是，此安全技術的失敗的概率是關於密鑰長度$x=n$的一個可忽略函數（參見公鑰密碼學）。因為密鑰長度$n$肯定是自然數，這就是為什麼開篇的定義把定義域改為自然數域的原因。

參考

• Goldreich, Oded. Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. 2001 [2007-03-02]. ISBN 0-521-79172-3. （原始內容存檔於2020-08-11）. 
• Sipser, Michael. Section 10.6.3: One-way functions. Introduction to the Theory of Computation. PWS Publishing. 1997: 374–376. ISBN 0-534-94728-X. 
• Papadimitriou, Christos. Section 12.1: One-way functions. Computational Complexity 1st. Addison Wesley. 1993: 279–298. ISBN 0-201-53082-1. 
• Colombeau, Jean François. New Generalized Functions and Multiplication of Distributions. Mathematics Studies 84, North Holland. 1984. ISBN 0-444-86830-5. 
• Bellare, Mihir. A Note on Negligible Functions. Dept. of Computer Science & Engineering University of California at San Diego. 1997. CiteSeerX 10.1.1.43.7900 .