Lagrange, Fermat, and Euler
Fermat’s and Euler’s Theorems
See this video and these notes
Remember that $U(n)$ is the multiplicative group of integers mod $n$ that have no factor in common with $n$.
 \[U(5)=\{1,2,3,4\}\]
 \[U(10) = \{1,3,7,9\}\]
 \[U(30) = \{1,7,11,13,17,19,23,29\}\]
Definition: $\phi(n)$ is the number of elements in $U(n)$ for any integer $n\ge 1$.
Lemma: If $p$ is prime, then $\phi(p)=p1$.
Fermat’s (Little) Theorem: Let $p$ be a prime number and let $a$ be an integer not divisible by $p$. Then \(a^{p1}\equiv 1\pmod{p}.\)
Euler’s Theorem: Let $n\ge 1$ and let $a$ be an integer such that $gcd(a,n)=1$. Then \(a^{\phi(n)}\equiv 1\pmod{n}\)
Both of these are versions of Lagrange’s Theorem.
The RSA (RivestShamirAdelman) Public Key Cryptosystem
See Section 7.2 of the text. See also this video and these notes

Choose two prime numbers $p$ and $q$, and compute $m=(p1)(q1)=\phi(pq)$. Then find two numbers $D$ and $E$ so that $DE\equiv 1\pmod{m}$.

Spy central publishes $E$ and $n$ and keeps $D$ and $m$ secret.

Agent X wants to send a message to Spy Central. They convert their message to a number $x$, and work out $y=x^{E}\pmod n$.

Spy central computes $z\equiv (x^{E})^{D}\equiv x^{ED}\equiv x\pmod{n}$ by Euler’s Theorem.
For anyone else to crack this code, they need to figure out D, which means they need to know $m$. To find $m$, they need to factor $n=pq$. If $p$ and $q$ are large enough, this is not feasible.
Fast modular exponentiation
See Section 4.3 of the text. See also this video and these notes
RSA is impractical unless there is an efficient way to compute $a^{E}\bmod{n}$ efficiently, where $E$ might be very large.
The method of “repeated squares mod $n$” makes this possible.
Algorithm: Given $a$, $E$, and $N$, the goal is to compute $a^{E}\bmod{n}$.
 Initialize: Set S=a, P=1, T=E
 Loop: While T>1:
 if T is odd, set P = (S*P) mod N.
 Replace S by S*S mod N.
 Divide T by 2, dropping any remainder
 Finish: Return (S*P) mod N
Example: Let $N=2^{2^5}+1$ and $a=3$. Compute $3^{(N1)}\bmod N$.
S  P  T 

9  1  4294967296 
81  1  2147483648 
6561  1  1073741824 
43046721  1  536870912 
3793201458  1  268435456 
1461798105  1  134217728 
852385491  1  67108864 
547249794  1  33554432 
1194573931  1  16777216 
2171923848  1  8388608 
3995994998  1  4194304 
2840704206  1  2097152 
1980848889  1  1048576 
2331116839  1  524288 
2121054614  1  262144 
2259349256  1  131072 
1861782498  1  65536 
1513400831  1  32768 
2897320357  1  16384 
367100590  1  8192 
2192730157  1  4096 
2050943431  1  2048 
2206192234  1  1024 
2861695674  1  512 
2995335231  1  256 
3422723814  1  128 
3416557920  1  64 
3938027619  1  32 
2357699199  1  16 
1676826986  1  8 
10324303  1  4 
3029026160  1  2 
3029026160  1 
Thus \(3^{N1}\equiv 3029026160\pmod{N}\).
Incidentally this proves that $N$ is not prime.