可忽略函数

在数学中，可忽略函数（英语：Negligible function）是指

对于一个函数 ${\displaystyle \mu (x):\mathbb {N} {\rightarrow }\mathbb {R} }$ ，如果对于任意一个正多项式${\displaystyle poly()}$，存在一个${\displaystyle N_{c}>0}$，使得对于所有的${\displaystyle x>N_{c}}$

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

那么这个函数便是可忽略的（negligible）。通常我们把“存在一个${\displaystyle N_{c}>0}$，使得对于所有的${\displaystyle x>N_{c}}$”简化为“对于所有足够大的${\displaystyle x}$”。

历史

可忽略函数这个概念是和数学分析的形式化模型相关的。^{[注 1]}第一个比较严格的定义是波尔查诺在1817年给出的。后来的柯西, 魏尔施特拉斯和海涅都用了基本相同的以下定义^{[注 2]}：

（连续函数） 一个实数函数${\displaystyle f(x)}$在${\displaystyle x=x_{0}}$处连续，当对于任意一个正实数${\displaystyle \epsilon >0}$，有一个正实数${\displaystyle \delta >0}$，使${\displaystyle |x-x_{0}|<\delta }$时，有${\displaystyle |f(x)-f(x_{0})|<\epsilon }$。

只要每步改变一项参数，此定义就可经数步转换成为可忽略函数的定义。首先，当${\displaystyle x_{0}=\infty ,f(x_{0})=0}$时，我们需要定义"足够大"（sufficiently large），并定义无穷小量：

（足够大） 实数${\displaystyle x}$足够大时一个数学命题为真，当且仅当存在一个实数${\displaystyle N_{c}>0}$，对所有的实数${\displaystyle x>N_{c}}$此数学命题为真。

（无穷小） 一个连续函数${\displaystyle \mu (x)}$无穷小，当对任意足够大的正实数${\displaystyle x}$，对任意正实数^{[注 3]} ${\displaystyle pnum={\frac {1}{\epsilon }}>0}$，有

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

然后我们把正实数${\displaystyle \epsilon }$换成正实数多项式函数${\displaystyle \epsilon (x)}$。^{[注 4]}

（可忽略函数） 一个连续函数${\displaystyle \mu (x)}$可忽略，当对任意足够大的正实数${\displaystyle x}$，对任意正多项式${\displaystyle poly(x)={\frac {1}{\epsilon (x)}}>0}$，有

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

在基于计算复杂性理论的现代密码学中，一个安全技术是数学上可证明安全（provably secure）的意思通常是，此安全技术的失败^{[注 5]}的概率是关于密钥长度${\displaystyle x=n}$的一个可忽略函数（参见公钥密码学）。因为密钥长度${\displaystyle n}$肯定是自然数，这就是为什么开篇的定义把定义域改为自然数域的原因。^{[注 6]}