Given a composite positive integer $n$, find $p> 1$ and $q > 1$ such that $n=pq$.
Fastest known classical algorithm works in sub-exponential time:
$$ L[n] = \exp\Big( \Big( \sqrt[3]{\frac{64}{9}+o(1)} \Big) (\log n)^{\frac 13}(\log \log n)^{\frac 23}\Big) $$
This is better than exponential, but still slow when $n$ is large enough.
It is an important open problem whether one can find an efficient classical algorithm for integer factorization.
RSA is an Asymmetric Cryptosystem invented by Ron Rivest, Adi Shamir and Leonard Adleman (1977).
It uses a pair of keys:
The security of this cryptosystem is based on the assumption that factoring large integers is a hard computational problem.
Applications:
Step 1 - Choose Two Large Primes: