Number Theory and RSA

8.1 Modular Arithmetic Review

• $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n} \implies ac \equiv bd \pmod{n}$
• $a \equiv b \pmod{n} \implies a^k \equiv b^k \pmod{n}$

8.2 Euler's Theorem

8.3 RSA Algorithm

1. Choose large primes $p, q$
2. Compute $n = pq$, $\phi(n) = (p-1)(q-1)$
3. Choose $e$ with $\gcd(e, \phi(n)) = 1$
4. Compute $d = e^{-1} \pmod{\phi(n)}$
5. Public key: $(n, e)$, Private key: $(n, d)$ Encryption: $c = m^e \pmod{n}$ Decryption: $m = c^d \pmod{n}$ Why it works: $c^d \equiv (m^e)^d \equiv m^{ed} \equiv m^{1 + k\phi(n)} \equiv m \cdot (m^{\phi(n)})^k \equiv m \pmod{n}$

✅ Practice Questions

Solution

$n = 5 \times 11 = 55$, $\phi(55) = 4 \times 10 = 40$. Choose $e = 3$ (coprime with 40). $d = 3^{-1} \pmod{40} = 27$ since $3 \times 27 = 81 \equiv 1 \pmod{40}$. Q2: Encrypt $m=7$ using the above keys. Solution

$c = 7^3 \pmod{55} = 343 \pmod{55} = 343 - 6 \times 55 = 343 - 330 = 13$. Join Discord PreviousGraph AlgorithmsNextBoolean Algebra