Informally, a function 
is a one-way function if
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
theory NP-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.
4. Subset sum problem: 
, for 
, and 
-bit integers 
.
5. Quadratic residue problem.
