## Preparation

- Choose arbitrary large primes \(p,q\).
- Compute \(N = p\cdot q\).
- Choose arbitrary exponent \(e\) relatively prime
^{1}to \((p-1)(q-1)\). - Compute \(d = e^{-1}\mod (p-1)(q-1) \).
- Publicly release \(N, e\) for encryption, keep \(d\) private for decryption.

## Encryption

- Convert message into a positive integer \(m\le N\).
- Compute \(c=m^e\mod N\).
- Send recipient \(c\).

## Decryption

- Compute \(m=c^d\mod N\)

"is relatively prime to" is equivalent to "shares no common factors with" ↩