Fermat's and Euler's Theorems

1994. Princeton. Andrew Wiles announces the proof of Fermat's Last Theorem - the one Fermat scribbled in a margin in 1637: 'I have a wonderful proof, but this margin is too small to contain it.' Seven years in secret. 129 pages. The first version contains an error. Another year to fix it. Meanwhile Fermat's little theorem - far more modest in statement, far more consequential in impact - guards every HTTPS connection on the planet. RSA-2048 is secure today. A quantum computer running Shor's algorithm would crack it in hours. NIST knows this - hence CRYSTALS-Kyber, standardized in 2024 as the post-quantum replacement.

• **RSA-2048:** key generation uses $\varphi(n) = (p-1)(q-1)$; every encryption and decryption call is modular fast-exponentiation. Every HTTPS handshake in the browser.
• **Miller-Rabin primality test:** probabilistic test built directly on Fermat's little theorem - used in Python `sympy.isprime`, OpenSSL, Java `BigInteger.isProbablePrime`. With k=40 rounds, error probability is below $4^{-40}$.
• **Post-quantum cryptography:** RSA is vulnerable to Shor's algorithm. NIST 2024 standardized CRYSTALS-Kyber (lattice-based) precisely because Fermat's little theorem will no longer be a defense against sufficiently powerful quantum computers.

Предварительные знания

• Modular Arithmetic

Fermat's Little Theorem

1640. Pierre de Fermat drops a remark in a letter: if p is prime and p does not divide a, then $a^{p-1} \equiv 1 \pmod{p}$. No proof. Just the fact. Euler would prove it a century later. Four centuries after that, this same fact guards every TLS handshake on the internet - billions of times per second, through OpenSSL's `BN_mod_exp`.

**Fermat's Little Theorem:** If p is prime and gcd(a, p) = 1, then: $a^{p-1} \equiv 1 \pmod{p}$ Equivalent form (for any a): $a^p \equiv a \pmod{p}$ **Corollary:** $a^{-1} \equiv a^{p-2} \pmod{p}$ - instant modular inverse when the modulus is prime.

The proof is a small masterpiece. Consider $\{a, 2a, 3a, \ldots, (p-1)a\}$ modulo p. All residues are distinct (if $ia \equiv ja$ then $i \equiv j$ since gcd(a,p)=1) and none is zero - so this is a permutation of $\{1, 2, \ldots, p-1\}$. Multiply both sides: $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$, giving $a^{p-1} \equiv 1$. Python's `pow(a, p-1, p)` runs exactly this logic - hundreds of billions of times daily for OpenSSL.

The converse fails: $a^{n-1} \equiv 1 \pmod{n}$ does NOT imply n is prime. Carmichael numbers (561, 1105, 1729...) fool the Fermat test for every base coprime to n. Miller-Rabin in the next lesson (nt-07) closes this gap.

Euler's Totient and Euler's Theorem

Fermat only worked with prime moduli. Euler asked: what if the modulus is composite? The key is counting how many integers from 1 to n actually have a multiplicative inverse modulo n. That count is $\varphi(n)$ - the size of the multiplicative group $\mathbb{Z}_n^*$. RSA security rests entirely on the fact that computing $\varphi(n) = (p-1)(q-1)$ from n alone - without knowing p and q - is computationally equivalent to factoring n.

**Euler's totient $\varphi(n)$:** count of integers $a \in \{1, \ldots, n\}$ with $\gcd(a, n) = 1$. **Formulas:** - $\varphi(p) = p - 1$ (p prime) - $\varphi(p^k) = p^{k-1}(p - 1)$ - $\varphi(mn) = \varphi(m)\cdot\varphi(n)$ when $\gcd(m, n) = 1$ (multiplicativity) - $\varphi(n) = n \cdot \prod_{p \mid n}\left(1 - \frac{1}{p}\right)$ **Euler's Theorem:** if $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}$ **Special case:** for prime p, $\varphi(p) = p-1$ recovers Fermat's little theorem.

Fast Modular Exponentiation

RSA-2048 operates on numbers with 617 decimal digits. Computing $a^e \bmod n$ where e is on the order of $2^{1024}$ must happen in milliseconds. Naive repeated multiplication would require more operations than there are atoms in the observable universe. Square-and-multiply does it in O(log e) - roughly 2048 multiplications.

**Binary exponentiation (square-and-multiply):** Key idea: decompose the exponent in binary. $a^{13} = a^8 \cdot a^4 \cdot a^1$ because 13 = 1101₂ Algorithm: 1. result = 1, base = a 2. Iterate over bits of e from LSB to MSB 3. If current bit is 1: result *= base 4. Always: base = base² Complexity: O(log e) multiplications - vs O(e) naively.

Python's `pow(base, exp, mod)` is not just a convenience wrapper. It is a C implementation of Montgomery multiplication, optimized per CPU architecture. OpenSSL generates RSA keys through the same algorithm - hundreds of billions of calls per day across the internet. For modular inverse: `pow(a, mod-2, mod)` at prime modulus, or `pow(a, -1, mod)` (Python 3.8+) for any modulus.

RSA: Euler's Theorem in Action

RSA is not just 'exponentiation modulo n'. It is a direct application of Euler's theorem. If $ed \equiv 1 \pmod{\varphi(n)}$, then $(m^e)^d = m^{ed} = m^{k\varphi(n)+1} \equiv m \cdot 1 = m \pmod{n}$. Decryption undoes encryption precisely because Euler proved $a^{\varphi(n)} \equiv 1$. Every certificate in the global PKI infrastructure rests on this identity.

**RSA key generation:** 1. Choose large primes p, q 2. $n = p \cdot q$ (public modulus) 3. $\varphi(n) = (p-1)(q-1)$ 4. Choose e: $1 < e < \varphi(n)$, $\gcd(e, \varphi(n)) = 1$ (commonly e = 65537) 5. Find d: $e\cdot d \equiv 1 \pmod{\varphi(n)}$ via extended Euclidean 6. Public key: (n, e). Private key: (n, d) **Encrypt:** $c = m^e \bmod n$ **Decrypt:** $m = c^d \bmod n$ **Correctness:** $c^d = m^{ed} = m^{1+k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m \cdot 1 = m \pmod{n}$

RSA security rests not on Euler's theorem but on integer factorization hardness. Given n = p·q, computing $\varphi(n) = (p-1)(q-1)$ without knowing p and q is equivalent to factoring n. The best classical algorithm (General Number Field Sieve) runs in sub-exponential time. Shor's algorithm on a quantum computer runs in polynomial time. This is why NIST standardized CRYSTALS-Kyber in 2024 - a lattice-based replacement for RSA, deployed before quantum computers grow threatening.

Key Ideas

• **Fermat:** $a^{p-1} \equiv 1 \pmod{p}$ for prime p with $\gcd(a,p)=1$; corollary: $a^{-1} \equiv a^{p-2} \pmod{p}$
• **$\varphi(n)$:** count of integers coprime to n; $\varphi(p) = p-1$; $\varphi(pq) = (p-1)(q-1)$ - the secret RSA cannot reveal
• **Euler:** $a^{\varphi(n)} \equiv 1 \pmod{n}$ when $\gcd(a,n)=1$ - generalizes Fermat to composite moduli
• **RSA correctness:** decryption works because $ed \equiv 1 \pmod{\varphi(n)}$ makes $c^d \equiv m \pmod{n}$ by Euler's theorem
• **Threat:** Shor's algorithm on a quantum computer factors n in polynomial time - RSA stops working

Related Topics

Fermat and Euler sit at the crossroads of number theory and cryptography:

• Modular Arithmetic — The multiplicative group $\mathbb{Z}_n^*$ is the foundation for both theorems
• Primality Tests — The Fermat and Miller-Rabin tests are direct applications of Fermat's little theorem
• Number Theory in Cryptography — Full RSA walkthrough, DLP, and Diffie-Hellman all build on Euler's theorem

Вопросы для размышления

• Why does real RSA use e = 65537 (= 2¹⁶ + 1) rather than e = 3? What could go wrong with a small e?
• If an attacker learns $\varphi(n)$, what can they compute? Why does this break RSA completely?
• Euler's theorem requires $\gcd(a, n) = 1$. What happens if a message m is divisible by p or q?
• Shor's algorithm factors n in O(log³ n) quantum operations. What RSA key size would be needed to make this take longer than the age of the universe?

Связанные уроки

• nt-03 — The multiplicative group Zn* is the foundation for both theorems
• nt-07 — Miller-Rabin is built directly on Fermat's little theorem
• nt-11 — Full RSA - key generation to attacks - is a direct consequence of Euler's theorem
• prob-03-conditional — Analogous structure: gcd=1 condition acts like conditional independence
• crypto-24-rsa-math
• crypto-26-ecc-math