1. The description of
is publicly known and does not require any secret information for its operation.

2. Given ,
it is easy to compute .

3. Given ,
in the range of ,
it is hard to find an
such that .
More precisely, any efficient algorithm solving a P-problem
succeeds in inverting
with negligible probability.

The existence of one-way functions is not proven. If true, it would imply . Therefore, it would answer the complexity
theoryNP-problem question of whether all apparently
NP-problems are actually P-problems. Yet a number of conjectured one-way functions
are routinely used in commerce and industry. For example, it is conjectured, but
not proved, that the following are one-way functions:

1. Factoring problem: ,
for randomly chosen primes .

2. Discrete logarithm problem:

for
a generator of
for some prime .

3. Discrete root extraction problem: , for in , in and relatively prime to , and primes. This is the function commonly known as RSA
encryption.