無視可能函数のソースを表示

[[数学]]における'''無視可能函数'''（むしかのうかんすう、{{lang-en-short|''negligible function''}}）は、極限においていかなる多項式よりも非常に緩やかな増加をするような[[函数]]である。

== 定義 ==
実数列 &mu;: '''N''' &rarr; '''R''' は、任意の正整数 ''c'' に対して適当な整数 ''N''<sub>''c''</sub> を選べば、''x'' &gt; ''N''<sub>''c''</sub> なる全ての ''x'' について
:<math>|\mu(x)|<\frac{1}{x^c}</math>
が成り立つようにできるとき、「無視できる」という。あるいは同じことだが、次のように定義してもよい。すなわち、実数列 &mu;: '''N''' &rarr; '''R''' が「無視できる」とは、任意の正値多項式 poly(&bull;) に対して適当な自然数 ''N''<sub>poly</sub> を選べば、''x'' &gt; ''N''<sub>poly</sub> なる全ての ''x'' に対して
: <math>|\mu(x)|<\frac{1}{\text{poly}(x)}</math>
が成り立つようにできることをいう。

== 歴史 ==
「無視可能」という概念は sound models of analysis にまで遡ることができる。 [[アイザック・ニュートン|ニュートン]]や[[ゴットフリート・ライプニッツ|ライプニッツ]]の時代（1680年代）には[[連続写像|連続性]]や[[無限小]]の概念が重要な意味を持つようになっていたが、これらの概念は後の1810年代になるまでは[[well-defined|きちんと定義された]]ものではなかった。[[解析学]]において「連続性」の意味のある厳密な定義が初めて成されるのは、[[ベルナルト・ボルツァーノ]]が1817年に著した『連続性の現代的定義』においてである。その後、[[オーギュスタン・ルイ・コーシー|コーシー]]、[[カール・ワイエルシュトラス|ワイエルシュトラス]]および[[エドゥアルト・ハイネ|ハイネ]]らも以下のような定義を与えている。ここでは数は全て実数全体の成す集合 '''R''' に属するものとする。

; [[連続函数]]: 函数 ''f'': '''R''' &rarr; '''R''' が点 ''x'' = ''x''<sub>0</sub> において'''連続'''であるとは、いかなる正の数 &epsilon; &gt; 0 に対しても正の数 &delta; &gt; 0 を適当に選べば、&#x7c;''x'' &minus; ''x''<sub>0</sub>&#x7c; &lt; &delta; ならば &#x7c;''f''(''x'') &minus; ''f''(''x''<sub>0</sub>)&#x7c; &lt; &epsilon; とできることをいう。

この古典的な連続性の定義を適当に書き換えれば、無視可能性の定義に書き直すことができる。まず、''x''<sub>0</sub> = &infin; において ''f''(''x''<sub>0</sub>) = 0 となる場合を考える。ここで「'''無限小'''」の概念を定義する必要が生じる。
; [[無限小]]函数: 連続函数 &mu;: '''R''' &rarr; '''R''' が（''x'' を無限大に飛ばす極限で）'''無限小'''であるとは、あらゆる &epsilon; &gt; 0 に対して適当な ''N''<sub>&epsilon;</sub> を選べば、''x'' &gt; ''N''<sub>&epsilon;</sub> なるとき常に &#x7c;&mu;(''x'')&#x7c; &lt; &epsilon; とできることをいう。

引き続き、定義における &epsilon; &gt; 0 を函数 1/''x''<sup>''c''</sup> (''c'' &gt; 0) あるいは 1/poly(''x'')（poly(''x'') は正値多項式）に取り替えれば、先の無視可能函数の定義を得る。定数 &epsilon; &gt; 0 も適当な定数多項式に対する 1/poly(''x'') として書けるから、無視可能函数のクラスは（無限遠における）無限小函数のクラスの部分集合になっていることがわかる。

== 暗号理論 ==
計算量に基づく現代暗号理論では、セキュリティ方式が'''[[証明可能安全性|証明可能な安全性を持つ]]'''とは、入力項 ''x'' を長さ ''n'' の暗号鍵とするとき、セキュリティ失敗（例えば[[一方向函数]]が覆されたり、[[暗号論的擬似乱数生成器|暗号論的強擬似乱数ビット]]が真のビットと峻別されたり）の可能性が「無視できる」ことをいう。これを適用するためには、鍵長 ''n'' は自然数でないといけないので、冒頭の定義における ''x'' は自然数としている。

もちろん、無視可能函数の一般概念では系の入力変数 ''x'' は何も鍵長 ''n'' である必要はないのであって、実際 ''x'' は事前に与えられた系の任意の計量としてよく、無視可能函数についての解析学は、こういった系のある種の隠れた解析学的振る舞いを記述するものになる。

多項式の逆数による定式化は、[[計算論的有界性]]が多項式時間に従って定義されるのと同じ理由で利用される。これは閉包性質を持つから[[漸近的安全性|漸近的な設定]]において御しやすい。例えば仮に、無視できる可能性しかないセキュリティ条件に反して攻撃が成功したとして、攻撃回数が多項式オーダーで繰り返されたならば、攻撃が全般にわたって成功する可能性はそれでもまだ無視できる。実用上はもっと[[具体的なセキュリティ|具体的な]]函数が求められ、それによって相手の成功可能性を低く抑えたり、その可能性が適当な閾値（2<sup>&minus;128</sup> など）を超えない程度に十分に長いセキュリティー変数を選んだりする。

== 参考文献 ==
* Goldreich, Oded (2001). ''Foundations of Cryptography: Volume 1, Basic Tools''.  Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the  [http://www.wisdom.weizmann.ac.il/~oded/frag.html author's web site].
* {{cite book|author = [[マイケル・シプサー|Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X}} Section 10.6.3: One-way functions, pp.374&ndash;376.
* {{cite book|author = [[クリストス・パパディミトリオ|Christos Papadimitriou]] | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st edition | isbn = 0-201-53082-1}} Section 12.1: One-way functions, pp.279&ndash;298.
* {{cite book|author = [[ジャン・フランソワ・コロンボ|Jean François Colombeau]] | year = 1984 | title = New Generalized Functions and Multiplication of Distributions | publisher = Mathematics Studies 84, North Holland | isbn = 0-444-86830-5}}

== 関連項目 ==
* [[無視可能集合]]
* [[コロンボ代数]]
* [[超準解析]]
* [[多項式の増加に関するグロモフの定理]]
* [[超準微分積分学]]

{{DEFAULTSORT:むしかのうかんすう}}
[[Category:関数]]
[[Category:解析学]]
[[Category:暗号技術]]
[[Category:数学に関する記事]]