Easy one way, impossible the other

What is a one-way function

All of modern cryptography rests on an idea as simple as it is surprising: some operations are easy to perform but practically impossible to undo. These are called one-way functions.

An intuitive definition

A function f is said to be one-way when:

computing y = f(x) is fast, even for a modest computer;
recovering x from y alone is infeasible in practice, even with considerable resources.

The important word is infeasible: it does not mean "slow" but "out of reach" — millions of years of computation for the sizes used in cryptography.

Two founding examples

Multiplying two large prime numbers. Multiplying p and q is instantaneous; recovering p and q from the product n = p × q alone is the factorization problem, for which no fast algorithm is known.

        FACILE  ------------------->
   p, q                              n = p × q
        <-------------------  IMPOSSIBLE
              (factorisation)

Modular exponentiation. Computing y = g^x mod p is fast. Recovering the exponent x from y, g and p is the discrete logarithm problem, also reputed to be very hard.

Two analogies to remember

The broken egg. Breaking an egg takes a second; putting it back together intact is impossible. The forward direction is trivial, the reverse direction out of reach.
Mixed paint. Mixing two pots of color is immediate; separating the original pigments again is next to impossible.

These images make tangible what "easy one way, infeasible the other" means.

A crucial point: nothing is proven

Here is the paradox every student must understand: the existence of one-way functions has not been proven. No one has proven that factoring is necessarily slow — we have only observed that, despite decades of effort, no one manages to do it quickly.

This question is intimately tied to the great open problem P vs NP of theoretical computer science. Until it is settled, the hardness of these problems remains a solid but unproven conjecture.

Aspect	One-way function
Forward direction	easy, fast
Reverse direction	infeasible in practice
Existence	conjectured, not proven
Theoretical link	P vs NP problem

We therefore build security on problems we believe to be hard, for lack of absolute certainty. It is a gamble — but a gamble backed by an enormous cryptanalytic effort.

In summary