跳转到内容

可忽略函数

本页使用了标题或全文手工转换
维基百科,自由的百科全书

数学中,可忽略函数(英語:Negligible function)是指

对于一个函数 ,如果对于任意一个正多项式,存在一个,使得对于所有的

那么这个函数便是可忽略的(negligible)。通常我们把“存在一个,使得对于所有的”简化为“对于所有足够大的”。

历史

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

连续函数 一个实数函数连续,当对于任意一个正实数,有一个正实数,使时,有

只要每步改变一项参数,此定义就可经数步转换成为可忽略函数的定义。首先,当时,我们需要定义"足够大"(sufficiently large),并定义無窮小量

(足够大) 实数足够大时一个数学命题为真,当且仅当存在一个实数,对所有的实数此数学命题为真。
无穷小 一个连续函数无穷小,当对任意足够大的正实数,对任意正实数[註 3] ,有

然后我们把正实数换成正实数多项式函数[註 4]

(可忽略函数) 一个连续函数可忽略,当对任意足够大的正实数,对任意正多项式,有

在基于計算複雜性理論的现代密码学中,一个安全技术是数学上可证明安全(provably secure)的意思通常是,此安全技术的失败[註 5]概率是关于密钥长度的一个可忽略函数(参见公钥密码学)。因为密钥长度肯定是自然数,这就是为什么开篇的定义把定义域改为自然数域的原因。[註 6]

注释

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

参考