It is public-key cryptosystem and depends on several facts of number theory, many of which relate to modular arithmetic.

Brief algorithm

1. Pick at random two very large prime numbers, $p$ and $q$ (at least 1024 bits each), that are not equal to each other.
2. Compute $n = p*q$. That’s a number with at least 2048 bits.
3. Compute $r = (p-1)*(q-1)$, which is almost as large as n.
4. Select a small odd integer $e$ that is relatively prime to $r$
5. Compute $d$ as the Multiplication inverse of $e$, modulo $r$. That is, $e*d \space (mod \space r) \equiv 1$.
6. Declare my RSA public key to be the pair $P = (e, n)$.
7. Keep the pair $S = (d, n)$ as my RSA secret key, revealed to nobody.
8. Define the functions $F_{P}$ and $F_{S}$ by: $F_{P} = x^e \space mod \space n$; $F_{S} = x^d \space mod \space n$. These functions can operate on either a block of plaintext or a block of ciphertext, whose bits we interpret as representing large integers.

<aside> 💡 Example

Algorithms Unlocked - Thomas H. Cormen (2013)

</aside>

Algorithm explaination

How to find a large prime number?

Randomly generate a large odd number and use the primality test (Miller-Rabin preferred) to determine whether it’s prime, stopping once you find a prime number.

<aside> 💡 But we can spend a huge amount of time searching for a prime, right? Actually, no.

The Prime Number Theorem tells us that, as $x$ approaches infinity, the number of prime numbers less than or equal to $x$ approaches $x$ / $\ln{x}$.

</aside>

How to select a small odd integer $e$ that is relatively prime to $r$

Relatively prime means that the only common divisor of $e$ and $r$ should be 1 (and so greatest common divisor is 1 too). Any such small integer is fine here.

But how to compute relatively prime integer? We just try to find it by computing d = gcd(e, r) (which must be 1 for relatively prime integer and at this moment we can say that we’ve found it!) for all numbers from 2 until finding it.

How to compute multiplicative inverses in modular arithmetic?