「一方向性関数」の版間の差分
削除された内容 追加された内容
「断り」はない。lk: +多項式時間, +乱択アルゴリズム。+{{lang-en-short}} |
Texvc2LaTeXBot (会話 | 投稿記録) m 廃止された数式構文をmw:Extension:Math/Roadmapに従って置き換える |
||
4行目:
==厳密な定義==
<math>{\
Σ = {0, 1} とし、<math>\Sigma^* = \cup_{k\in{\
関数 <math>f : \Sigma^* \to \Sigma^*</math> が以下を満たす時、関数 ''f'' は'''一方向性関数'''であるという：
# ''f'' は[[多項式時間]]で計算可能。すなわちある多項式時間アルゴリズム ''C'' があって ''C''(''x'') = ''f''(''x'')
# 任意の多項式時間アルゴリズム ''A'' に対し、ある [[negligible]] な関数 ν とある <math>k_0 \in {\
#:<math>Pr\left[x \gets_R \Sigma^k, y \gets f\left(x\right),x' \gets A\left(1^k, y\right) : y=f\left(x'\right)\right] \le \nu\left(l\right) .</math>
33行目:
# ''G''<sub>2</sub> は ''n'' ∈ ''I'' を入力すると ''x'' ∈ ''D''<sub>''n''</sub> を出力するアルゴリズム。
# ある多項式時間アルゴリズム ''C'' があって ''C''(''x'', ''n'') = ''f''<sub>''n''</sub>(''x'')。
# 任意の多項式時間アルゴリズム ''A'' に対し、ある negligible な関数 ν とある ''k''<sub>0</sub> ∈ <math>{\
一方向性関数が存在する事は一方向性関数族が存在する事の必要十分条件である事が知られている。
62行目:
==一方向性関数の候補==
集合 {(''p'', ''q'') ∈ <math>{\
==必要十分条件==
| |||