可忽略函数这个概念是和数学分析的形式化模型相关的。[注 1]第一个比较严格的定义是波尔查诺在1817年给出的。后来的柯西, 魏尔施特拉斯和海涅都用了基本相同的以下定义[注 2]:
- (连续函数) 一个实数函数
在
处连续,当对于任意一个正实数
,有一个正实数
,使
时,有
。
只要每步改变一项参数,此定义就可经数步转换成为可忽略函数的定义。首先,当
时,我们需要定义"足够大"(sufficiently large),并定义无穷小量:
- (足够大) 实数
足够大时一个数学命题为真,当且仅当存在一个实数
,对所有的实数
此数学命题为真。
- (无穷小) 一个连续函数
无穷小,当对任意足够大的正实数
,对任意正实数[注 3]
,有
。
然后我们把正实数
换成正实数多项式函数
。[注 4]
- (可忽略函数) 一个连续函数
可忽略,当对任意足够大的正实数
,对任意正多项式
,有
。
在基于计算复杂性理论的现代密码学中,一个安全技术是数学上可证明安全(provably secure)的意思通常是,此安全技术的失败[注 5]的概率是关于密钥长度
的一个可忽略函数(参见公钥密码学)。因为密钥长度
肯定是自然数,这就是为什么开篇的定义把定义域改为自然数域的原因。[注 6]