# 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)=p-1$.

Fermat’s (Little) Theorem: Let $p$ be a prime number and let $a$ be an integer not divisible by $p$. Then $a^{p-1}\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 (Rivest-Shamir-Adelman) 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=(p-1)(q-1)=\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^{(N-1)}\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^{N-1}\equiv 3029026160\pmod{N}$.

Incidentally this proves that $N$ is not prime.