「一方向性関数」の版間の差分
削除された内容 追加された内容
El bot de la dieta (会話 | 投稿記録) m ロボットによる 変更: he:פונקציה חד-כיוונית |
|||
10行目:
# ''f'' は[[多項式時間]]で計算可能。すなわちある多項式時間アルゴリズム ''C'' があって ''C''(''x'') = ''f''(''x'')
# 任意の多項式時間アルゴリズム ''A'' に対し、ある [[negligible]] な関数 ν とある <math>k_0 \in {\Bbb N}</math> が存在して、全ての ''k'' > ''k''<sub>''0''</sub> に対し、
▲<math>Pr[x \gets_R \Sigma^k, y \gets f(x),x' \gets A(1^k, y) : y=f(x')] \le \nu(l)</math>。
==一方向性関数の存在性==
| |||