可忽略函数

基本介绍

对于一个函数μ(x):N→R，如果对于任意一个正多项式poly(x)，存在一个Nc u003e 0，使得对于所有的 x u003e Nc 有：

μ(x) u003c 1/poly(x)

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

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