跳至內容

可忽略函數

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

數學中,可忽略函數(英語:Negligible function)是指

對於一個函數 ,如果對於任意一個正多項式,存在一個,使得對於所有的

那麼這個函數便是可忽略的(negligible)。通常我們把「存在一個,使得對於所有的」簡化為「對於所有足夠大的」。

歷史

可忽略函數這個概念是和數學分析的形式化模型相關的。[註 1]第一個比較嚴格的定義是波爾查諾在1817年給出的。後來的柯西, 魏爾施特拉斯海涅都用了基本相同的以下定義[註 2]

連續函數 一個實數函數連續,當對於任意一個正實數,有一個正實數,使時,有

只要每步改變一項參數,此定義就可經數步轉換成為可忽略函數的定義。首先,當時,我們需要定義"足夠大"(sufficiently large),並定義無窮小量

(足夠大) 實數足夠大時一個數學命題為真,當且僅當存在一個實數,對所有的實數此數學命題為真。
無窮小 一個連續函數無窮小,當對任意足夠大的正實數,對任意正實數[註 3] ,有

然後我們把正實數換成正實數多項式函數[註 4]

(可忽略函數) 一個連續函數可忽略,當對任意足夠大的正實數,對任意正多項式,有

在基於計算複雜性理論的現代密碼學中,一個安全技術是數學上可證明安全(provably secure)的意思通常是,此安全技術的失敗[註 5]概率是關於密鑰長度的一個可忽略函數(參見公鑰密碼學)。因為密鑰長度肯定是自然數,這就是為什麼開篇的定義把定義域改為自然數域的原因。[註 6]

注釋

  1. ^ 儘管「連續函數」和「無窮小」的概念在牛頓萊布尼茨時代(十七世紀八十年代)就有了,但直到十九世紀一十年代才為後來的數學家們給出嚴格的數學定義。
  2. ^ 其中所有數都在實數域
  3. ^ 注意此處的倒數在定義域為實數域時並不需要加入,這樣寫是為了推導時看得清楚。
  4. ^ 因為數可以看作是度數為0的多項式函數,「可忽略函數」其實就是「函數值無窮小」在概念上的一個廣義定義。
  5. ^ 比如在多項式時間內將單向函數逆反,或在多項式時間內將密碼隨機數發生器產生的數和真正隨機數區別開來
  6. ^ 不過,此關於可忽略函數的數學定義從未規定函數輸入必須是密鑰長度。實際上在具體分析中,可以是任何事先規定好的系統的某個參數,然後可以通過數學上的分析揭示一些並不顯而易見的複雜系統的行為。

參考