可忽略函数

在数学中，可忽略函数（英語：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]}

注释

1. 尽管“连续函数”和“无穷小”的概念在牛顿和莱布尼茨时代（十七世纪八十年代）就有了，但直到十九世纪一十年代才为后来的数学家们给出严格的数学定义。
2. 其中所有数都在实数域${\displaystyle \mathbb {R} }$ 中
3. 注意此处的倒数${\displaystyle pnum}$ 在定义域为实数域时并不需要加入，这样写是为了推导时看得清楚。
4. 因为数可以看作是度数为0的多项式函数，“可忽略函数”其实就是“函数值无穷小”在概念上的一个广义定义。
5. 比如在多项式时间内将单向函数逆反，或在多项式时间内将密码随机数发生器产生的数和真正随机数区别开来
6. 不过，此关于可忽略函数的数学定义从未规定函数输入${\displaystyle x}$ 必须是密钥长度${\displaystyle n}$ 。实际上在具体分析中，${\displaystyle x}$ 可以是任何事先规定好的系统的某个参数，然后可以通过数学上的分析揭示一些并不显而易见的复杂系统的行为。

参考

• 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  .