Integer Factorization

Integer factorization of large semi-primes is one candidate for a one way function.

A semi-prime being a number which is the product of two prime numbers, therefore the candiate one way function is simply \(f(p, q) = pq\) where \(p\) and \(q\) are prime numbers of similar (but not exact) bit length. Although there is no formal proof, when the length of the resulting semi-prime is at least 2048 bits, the factoring process is considered difficult enough to be the basis of modern cryptography.

Practical Applications

[[ RSA ]] relies on integer factorization being a one-way function to prevent easy calculation of private keys from a public key.