RSA Algorithm

The RSA algorithm is a public-key cryptosystem invented by Rivest, Shamir, and Adleman in 1977. It was the first practical realization of asymmetric encryption: anyone can encrypt a message using the public key, but only the holder of the corresponding private key can decrypt it.

The security of RSA rests on the (unproven) assumption that factoring the product of two large prime numbers is computationally intractable. This is a problem in number theory that is easy to state and apparently hard to solve. The best known classical factoring algorithm, the general number field sieve, runs in sub-exponential time, but still cannot factor numbers of cryptographic size in practice. The existence of Shor's algorithm for quantum computers means that a sufficiently large quantum computer would break RSA entirely — a fact that has driven the development of post-quantum cryptography.

RSA has been the backbone of internet security for decades, securing everything from email to e-commerce. Its relative simplicity and long track record have made it the default choice, though elliptic curve cryptography is increasingly preferred for its superior efficiency.