\begin{definition}[Definition:RSA Algorithm]
The '''RSA algorithm''' is a technique of encoding a message such that the method of encoding can be made public without compromising the security.
Let Alice be sending a message to Bob.
Alice and Bob both agree on two large primes $p$ and $q$, each having at least $100$ digits.
Let $M = p q$.
$M$ can be made public if they so wish.
Let $K = \left({p - 1}\right) \left({q - 1}\right)$.
$K$ is to be kept secret.
Let Alice choose some number $a$ such that $a \perp K$.
$a$ is made known to Bob, and may even be made public.
Alice represents her message in a series of numbers in the range $0$ to $M$.
Let $x$ be one such number.
Alice calculates $y \equiv x^a \pmod M$.
The sequence of numbers $y$ is sent to Bob as the coded message.
Bob needs to know a number $b$ such that $a b \equiv 1 \pmod K$.
This number needs to be kept secret.
To decode $y$, Bob computes $y^b \pmod M$.
This works because of Fermat's Little Theorem:
:$y^b \equiv \left({x^a}\right)^b \equiv x^1 = x \pmod M$
The method works because:
:$(1): \quad$ There are efficient tests to find large primes
:$(2): \quad$ There are no known methods for finding the prime factors of large numbers efficiently.
So making $p q$ public does not help $p$ and $q$ be found, and without those it is impossible to work out what $b$ is.
{{NamedforDef|Ronald Linn Rivest|name2 = Adi Shamir|name3 = Leonard Max Adleman|cat = Rivest|cat2 = Shamir|cat3 = Adleman}}
\end{definition}