可忽略函数

对于一个函数 $\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年给出的。后来的柯西, 魏尔施特拉斯和海涅都用了基本相同的以下定义（其中所有数都在实数域$\mathbb{R}$中）：

（连续函数） 一个实数函数$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），并定义"无穷小"（infinitesimal）：

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

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

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

然后我们把"正实数$\epsilon$"换成"正实数多项式函数$\epsilon(x)$"。因为数可以看作是度数为0的多项式函数，“可忽略函数”其实就是“函数值无穷小”在概念上的一个广义定义。

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

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

在基于計算複雜性理論的现代密码学中，一个安全技术是数学上可证明安全（provably secure）的意思通常是，此安全技术的失败（比如在多项式时间内将单向函数逆反，或在多项式时间内将密码随机数发生器产生的数和真正随机数区别开来）的概率是关于密钥长度$x=n$的一个可忽略函数（参见公钥密码学）。因为密钥长度$n$肯定是自然数，这就是为什么开篇的定义把定义域改为自然数域的原因。

不过，此关于可忽略函数的数学定义从未规定函数输入$x$必须是密钥长度$n$。实际上在具体分析中，$x$可以是任何事先规定好的系统的某个参数，然后可以通过数学上的分析揭示一些并不显而易见的复杂系统的行为。

参考书目

• Goldreich, Oded (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the author's web site.
• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X.  Section 10.6.3: One-way functions, pp.374–376.
• Christos Papadimitriou. Computational Complexity. 1st edition. Addison Wesley. 1993. ISBN 0-201-53082-1.  Section 12.1: One-way functions, pp.279–298.