無視できる機能

数学において、無視できる関数とは 、任意の正の整数cに対して、任意のx  >  _{N c}に対して、 ${\displaystyle \mu :\mathbb {N} \to \mathbb {R} }$

${\displaystyle |\mu (x)|<{\frac {1}{x^{c}}}.}$

同様に、次の定義も使用できます。関数が無視可能であるとは、すべての正の多項式poly(·)に対して、整数N _{poly > 0が存在し、すべての}x  >  N _poly に対して${\displaystyle \mu :\mathbb {N} \to \mathbb {R} }$

${\displaystyle |\mu (x)|<{\frac {1}{\operatorname {poly} (x)}}.}$

無視可能性の概念は、健全な解析モデルに遡ることができます。「連続性」と「無限小」の概念は、ニュートンとライプニッツの時代（1680年代）に数学で重要になりましたが、1810年代後半まで明確に定義されていませんでした。数学的解析における連続性の最初の合理的に厳密な定義は、1817年に連続性の現代的な定義を書いたベルナルド・ボルツァーノによるものです。後に、コーシー、ワイエルシュトラス、ハイネも次のように定義しました（すべての数は実数領域内です）。 ${\displaystyle \mathbb {R} }$

（連続関数）関数がで連続であるとは、任意の に対して、 となる正の数が存在する場合である。${\displaystyle f:\mathbb {R} {\rightarrow }\mathbb {R} }$${\displaystyle x=x_{0}}$${\displaystyle \epsilon >0}$${\displaystyle \delta >0}$${\displaystyle |x-x_{0}|<\delta }$${\displaystyle |f(x)-f(x_{0})|<\varepsilon .}$

この連続性の古典的な定義は、定義で使用されるパラメータを変更することで、数ステップで無視可能性の定義に変換できます。まず、の場合、 「無限小関数」の概念を定義する必要があります。 ${\displaystyle x_{0}=\infty }$${\displaystyle f(x_{0})=0}$

（無限小）連続関数が無限小（無限大に向かって）であるとは、任意の関数に対して、任意の関数に対して、${\displaystyle \mu :\mathbb {R} \to \mathbb {R} }$${\displaystyle x}$${\displaystyle \epsilon >0}$${\displaystyle N_{\varepsilon }}$${\displaystyle x>N_{\epsilon}}$

${\displaystyle |\mu (x)|<\varepsilon \,.}$^[要出典]

次に、を関数 で置き換えるか、 を で置き換えます。ここで、 は正の多項式です。これにより、この記事の冒頭で示した無視できる関数の定義が導かれます。定数は定数多項式でと表すことができるため、無限小関数は無視できる関数のスーパーセットであることがわかります。 ${\displaystyle \epsilon >0}$${\displaystyle 1/x^{c}}$${\displaystyle c>0}$${\displaystyle 1/\operatorname {poly} (x)}$${\displaystyle \operatorname {poly} (x)}$${\displaystyle \epsilon >0}$${\displaystyle 1/\operatorname {poly} (x)}$

複雑性に基づく現代の暗号では、セキュリティ 障害の確率（例えば、一方向関数の反転、暗号的に強い疑似ランダムビットと真にランダムなビットの区別）が入力= 暗号鍵の長さに関して無視できるほど小さい場合、セキュリティスキームは安全であると証明できます。したがって、鍵の長さは自然数でなければならない ため、ページ上部の定義が当てはまります。${\displaystyle x}$${\displaystyle n}$${\displaystyle n}$

ただし、無視可能性の一般的な概念では、入力パラメータがキーの長さである必要はありません。実際、は任意の所定のシステム メトリックであり、対応する数学的分析によって、システムの隠れた分析動作が明らかになります。 ${\displaystyle x}$${\displaystyle n}$${\displaystyle x}$

多項式の逆数定式化は、計算上の有界性が多項式実行時間として定義されるのと同じ理由で使用されます。つまり、漸近設定で扱いやすくする数学的な閉包特性を持つためです (「閉包特性」を参照)。たとえば、攻撃がセキュリティ条件の違反に成功する可能性がごくわずかで、攻撃が多項式回数繰り返された場合、攻撃全体の成功確率は依然としてごくわずかのままです。

実際には、敵対者の成功確率を制限するより具体的な関数を用意し、この確率が2 ⁻¹²⁸などのしきい値よりも小さくなるようにセキュリティパラメータを十分に大きく選択することが望まれるかもしれません。

無視できる関数が複雑性理論暗号の基礎で使われる理由の一つは、それが閉包性に従うからである。^[1]具体的には、

1. が無視できる場合、関数は無視できます。${\displaystyle f,g:\mathbb {N} \to \mathbb {R} }$${\displaystyle x\mapsto f(x)+g(x)}$
2. が無視でき、 が任意の実多項式である場合、関数は無視できます。${\displaystyle f:\mathbb {N} \to \mathbb {R} }$${\displaystyle p}$${\displaystyle x\mapsto p(x)\cdot f(x)}$

逆に、が無視できない場合は、任意の実多項式 に対して もが無視できません。 ${\displaystyle f:\mathbb {N} \to \mathbb {R} }$${\displaystyle x\mapsto f(x)/p(x)}$${\displaystyle p}$

• ${\displaystyle n\mapsto a^{-n}}$は任意の に対して無視できる:${\displaystyle a\geq 2}$

  ステップ: これは指数関数的減少関数で、 は2 以上の定数です。 として、非常に速く、無視できるようになります。
${\displaystyle a}$${\displaystyle n\to \infty }$${\displaystyle a^{-n}\to 0}$

• ${\displaystyle f(n)=3^{-{\sqrt {n}}}}$無視できるほど小さい:

  ステップ: この関数は 3 を底とする指数関数的減少を示しますが、指数は よりも遅く増加します( の場合のみ)。、であるため、依然として無視できるほど小さいですが、 よりも遅く減少します。
${\displaystyle n}$${\displaystyle {\sqrt {n}}}$${\displaystyle n\to \infty }$${\displaystyle 3^{-{\sqrt {n}}}\to 0}$${\displaystyle 3^{-n}}$

• ${\displaystyle f(n)=n^{-\log n}}$無視できるほど小さい:

  ステップ: この場合、は多項式減衰を表し、指数は により負に増加します。 減衰率は とともに増加するため、関数は任意の定数 のような多項式関数よりも速く 0 に近づくため、無視できます。
${\displaystyle n^{-\log n}}$${\displaystyle \log n}$${\displaystyle n}$${\displaystyle n^{-k}}$${\displaystyle k}$

• ${\displaystyle f(n)=(\log n)^{-\log n}}$無視できるほど小さい:

  ステップ: この関数は、 の対数を負の指数で累乗するにつれて減少し、 のにつれて急速に 0 に近づきます。ここでの減少は、逆対数または多項式率よりも速いため、無視できます。
${\displaystyle n}$${\displaystyle -\log n}$${\displaystyle n\to \infty }$

• ${\displaystyle f(n)=2^{-c\log n}}$は無視できない。正の場合：${\displaystyle c}$

  ステップ: これを と書き直すと、指数関数的減少ではなく多項式的減少になります。 は正なのでとなりますが、 に関して真の指数関数ほど急速に減少しないため、無視できなくなります。
${\displaystyle f(n)=n^{-c}}$${\displaystyle c}$${\displaystyle f(n)\to 0}$${\displaystyle n\to \infty }$${\displaystyle n}$

と仮定すると、極限は次のようになります。 ${\displaystyle n>0}$${\displaystyle n\to \infty }$

無視できる:

• ${\displaystyle f(n)={\frac {1}{x^{n/2}}}}$:

  ステップ: この関数は、底の乗に対して指数的に減少します。 となると急速に減少し、無視できるようになります。
${\displaystyle x}$${\displaystyle -{\frac {n}{2}}}$${\displaystyle n\to \infty }$${\displaystyle x^{-{\frac {n}{2}}}\to 0}$

• ${\displaystyle f(n)={\frac {1}{x^{\log {(n^{k})}}}}}$のために：${\displaystyle k\geq 1}$

  ステップ:を として簡略化できます。これは、どの多項式よりも速く減少します。 として、関数はゼロに近づき、任意のおよびに対して無視できると見なされます。
${\displaystyle x^{-\log(n^{k})}}$${\displaystyle n^{-k\log x}}$${\displaystyle n\to \infty }$${\displaystyle k\geq 1}$${\displaystyle x>1}$

• ${\displaystyle f(n)={\frac {1}{x^{(\log n)^{k}}}}}$のために：${\displaystyle k\geq 1}$

  ステップ: 減衰は、 の累乗された底によって決まります。はとともに増加するため、この関数は多項式減衰よりも速くゼロに近づき、無視できるようになります。
${\displaystyle x}$${\displaystyle -(\log n)^{k}}$${\displaystyle (\log n)^{k}}$${\displaystyle n}$

• ${\displaystyle f(n)={\frac {1}{x^{\sqrt {n}}}}}$:

  ステップ: ここで、は を で乗じて まで指数的に減少します。 として急速に減少するため、無視できると考えられます。
${\displaystyle f(n)}$${\displaystyle x}$${\displaystyle -{\sqrt {n}}}$${\displaystyle n\to \infty }$${\displaystyle f(n)\to 0}$

無視できない:

• ${\displaystyle f(n)={\frac {1}{n^{1/n}}}}$:

  ステップ:であるため、この関数は非常にゆっくりと減少し、無視できるほど急速にゼロに近づくことができません。
${\displaystyle n^{1/n}\to 1}$${\displaystyle n\to \infty }$

• ${\displaystyle f(n)={\frac {1}{x^{n(\log n)}}}}$:

  ステップ: 指数底と指数の場合、この関数は急速にゼロに近づき、無視できることを示します。
${\displaystyle n(\log n)}$

• 無視できるセット
• コロンボー代数
• 非標準番号
• 多項式増加群に関するグロモフの定理
• 非標準微積分

• ゴールドライヒ、オデッド（2001）。暗号の基礎：第1巻、基本ツール。ケンブリッジ大学出版局。ISBN 0-521-79172-3。
• Sipser, Michael (1997)。「セクション 10.6.3: 一方向関数」。計算理論入門。PWS Publishing。pp. 374–376。ISBN 0-534-94728-X。
• Papadimitriou, Christos (1993)。「セクション 12.1: 一方向関数」。計算複雑性(第 1 版)。Addison Wesley。pp. 279–298。ISBN 0-201-53082-1。
• Colombeau, Jean François (1984)。新しい一般化関数と分布の乗算。数学研究 84、北ホラント。ISBN 0-444-86830-5。
• ベラーレ、ミヒル (1997)。 「無視できる機能に関するメモ」。暗号学ジャーナル。１５．カリフォルニア大学サンディエゴ校コンピュータ サイエンス & エンジニアリング学部: 2002。CiteSeerX  10.1.1.43.7900。