Number Theory Foundations
Number Theory Foundations
Cryptography is built on number theory — the study of integer properties. Modular arithmetic, prime numbers, and Euler's totient function are the mathematical bedrock beneath every modern cipher and protocol.
Definition
\(a \equiv b \pmod{n}\) means \(n\mid(a-b)\). Euler's totient \(\phi(n)\) counts integers \(1\leq k\leq n\) coprime to \(n\). For prime \(p\): \(\phi(p)=p-1\); for \(n=pq\): \(\phi(n)=(p-1)(q-1)\).
Key Result
Fermat's little theorem: \(a^{p-1}\equiv 1\pmod{p}\) for prime \(p\) and \(\gcd(a,p)=1\). Euler's theorem generalises: \(a^{\phi(n)}\equiv 1\pmod{n}\) whenever \(\gcd(a,n)=1\). Both underpin RSA.
Example 1
Extended Euclidean algorithm finds \(\gcd(a,b)\) and integers \(x,y\) such that \(ax+by=\gcd(a,b)\). For \(a=240, b=46\): \(\gcd = 2\), and \(240(-9)+46(47) = 2\). Use to compute modular inverses.
Example 2
Chinese Remainder Theorem (CRT): given \(x\equiv a_i\pmod{n_i}\) with pairwise coprime \(n_i\), there is a unique solution mod \(N = \prod n_i\). CRT speeds RSA by performing computations mod \(p\) and \(q\) separately.
Loading modular-arithmetic...
Practice
- Compute \(3^{1000} \pmod{7}\) using Fermat's little theorem.
- Find the modular inverse of 17 modulo 3120 using the extended Euclidean algorithm.
- State and prove Euler's theorem.
- Why must \(p\) and \(q\) be kept secret in RSA?
Show Answer Key
1. Fermat: $a^{p-1} \equiv 1 \pmod{p}$ for $\gcd(a,p)=1$. $3^6 \equiv 1 \pmod{7}$. $1000 = 166\times6+4$. So $3^{1000} = (3^6)^{166}\cdot3^4 \equiv 1^{166}\cdot81 \equiv 81 \bmod 7 \equiv 4 \pmod{7}$.
2. Extended Euclidean: find $x,y$ with $17x+3120y=1$. $3120 = 183\times17+9$, $17 = 1\times9+8$, $9 = 1\times8+1$. Back-substitute: $1 = 9-8 = 9-(17-9) = 2\times9-17 = 2(3120-183\times17)-17 = 2\times3120-367\times17$. So $17^{-1} \equiv -367 \equiv 2753 \pmod{3120}$.
3. Euler's theorem: $a^{\phi(n)}\equiv 1\pmod{n}$ for $\gcd(a,n)=1$. Proof: consider the set $S = \{r_1,\ldots,r_{\phi(n)}\}$ of residues coprime to $n$. The map $r \mapsto ar\bmod n$ is a bijection on $S$. Product: $\prod(ar_i) \equiv \prod r_i \pmod{n}$, so $a^{\phi(n)}\prod r_i \equiv \prod r_i$, giving $a^{\phi(n)} \equiv 1$. ✓
4. RSA: $n=pq$, $\phi(n)=(p-1)(q-1)$. If $p,q$ are known, $\phi(n)$ is known, so the private key $d=e^{-1}\bmod\phi(n)$ can be computed directly. Factoring $n$ breaks RSA. Keeping $p,q$ secret is equivalent to keeping the private key secret. Additionally, knowing $\phi(n)$ reveals $p+q = n-\phi(n)+1$ and $p-q = \sqrt{(p+q)^2-4n}$, directly giving $p$ and $q$.