Wikipedia

「一方向性関数」の版間の差分

履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
m編集の要約なし
4行目:
==厳密な定義==
<math>{\Bbb N}</math> で自然数の集合を現す。
<math>\&Sigma; = \{0, 1\}</math> とし、<math>\Sigma^* = \cup_{k\in{\Bbb N}}\Sigma^k</math>とする。
 
関数 <math>f : \Sigma^* \to \Sigma^*</math> が以下を満たす時、関数 <math>''f</math>'' は'''一方向性関数'''であるという：
 
# <math>''f</math>'' は[[多項式時間]]で計算可能。すなわちある多項式時間アルゴリズム <math>''C</math>'' があって <math>''C''(''x'') = ''f''(''x'')</math>。
# 任意の多項式時間アルゴリズム <math>''A</math>'' に対し、ある [[negligible]] な関数 <math>\&nu</math>; とある <math>k_0 \in {\Bbb N}</math> が存在して、全ての <math>''k'' >&gt; k_0''k''<sub>''0''</mathsub> に対し、<br>

<math>Pr[x \mid A(1^k, y) \mid x \gets_R \Sigma^k, y \gets f(x)] \le \nu(l)</math>。
 
==一方向性関数の存在性==
40 ⟶ 42行目:
'''定理'''　一方向性関数が存在する必要十分条件は弱一方向性関数が存在する事である。
 
'''証明の概略'''（&rArr;）自明。<br>
 
（&lArr;）''f'' を弱一方向性関数とする。''g'' を ''g''(''x''<sub>1</sub> || &hellip; || ''x''<sub>''N''</sub>) = ''f''(''x''<sub>1</sub>) || &hellip; || ''f''(''x''<sub>''N''</sub>) と定義する。ただしここで「||」はビット列の連接、''N'' = 2''kP''(''k'')。（''P'' は弱一方向性関数の定義の条件 2 にあるもの）。
この時 ''g''<sup>-1</sup> を求めるには、''f''<sup> -1</sup> を ''N'' 回計算しなければならない。
「https://ja.wikipedia.org/wiki/一方向性関数」から取得