可忽略函式這個概念是和數學分析的形式化模型相關的。儘管“連續函式”和“無窮小”的概念在牛頓和萊布尼茨時代（十七世紀八十年代）就有了，但直到十九世紀一十年代才為後來的數學家們給出嚴格的數學定義。
基本介紹
- 中文名：可忽略函式
- 外文名：Negligible Function
- 領域：數學分析
對於一個函式μ(x):N→R，如果對於任意一個正多項式poly(x)，存在一個Nc > 0，使得對於所有的 x > Nc 有：
在基於計算複雜性理論的現代密碼學中，一個安全技術是數學上可證明安全（provably secure）的意思通常是，此安全技術的失敗（比如在多項式時間內將單向函式逆反，或在多項式時間內將密碼隨機數發生器產生的數和真正隨機數區別開來）的機率是關於密鑰長度x = n的一個可忽略函式（參見公鑰密碼學）。因為密鑰長度n肯定是自然數，這就是為什麼開篇的定義把定義域改為自然數域的原因。
不過，此關於可忽略函式的數學定義從未規定函式輸入x必須是密鑰長度n。實際上在具體分析中，x可以是任何事先規定好的系統的某個參數，然後可以通過數學上的分析揭示一些並不顯而易見的複雜系統的行為。
