一方向性関数

一方向性関数（いちほうこうせいかんすう、英: one-way function）とは、関数値は容易に計算できるが逆関数の計算は非常に困難である関数を指す。暗号理論などで用いられる概念である。素因数分解問題の困難性を用いたものが代表的。 下では、単に「多項式時間アルゴリズム」と書いたら「平均多項式時間確率アルゴリズム」を指す。