落とし戸関数とは？わかりやすく解説

一方向性関数（いちほうこうせいかんすう、英: one-way function）とは、関数値は容易に計算できるが逆関数の計算は非常に困難である関数を指す。

以下では、単に「多項式時間アルゴリズム」と書いた場合は「平均多項式時間確率アルゴリズム」を指す。

厳密な定義

${\mathbb {N} }$


	(C)Shogakukan Inc. 株式会社小学館
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアの一方向性関数 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。