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.