one-way function (original) (raw)

where x has length n and all numbers of length n are equally likely.

That is, no probabilistic, polynomial time function can effectively compute f-1.

Note that, since f need not be injective, this is a stricter requirement than

since not only is g⁢(f⁢(x)) (almost always) not x, it is (almost always) no value such that f⁢(g⁢(f⁢(x)))=f⁢(x).