--- title: Modular Exponentiation & Primality module: Mathematical Algorithms moduleNumber: 10 lessonNumber: 2 order: 1002 summary: | Computing $a^n \bmod m$ naively costs $n$ multiplications; **repeated squaring** does it in $O(\log n)$ by reading the bits of the exponent. We use this routine to state **Fermat's little theorem** (and the modular inverse it gives), then to test primality — trial division, the probabilistic **Fermat** and **Miller–Rabin** tests, and the deterministic witness set that settles primality for every 64-bit number. topics: [Number Theory] sources: - book: CLRS ref: "Ch. 31 — Number-Theoretic Algorithms (§31.6, §31.8)" - book: Skiena ref: "§ — Number Theory" - book: Erickson ref: "Ch. — (number theory)" practice: - title: 'Pow(x, n)' slug: powx-n difficulty: Medium - title: 'Super Pow' slug: super-pow difficulty: Medium - title: 'Count Primes' slug: count-primes difficulty: Medium - title: 'Closest Prime Numbers in Range' slug: closest-prime-numbers-in-range difficulty: Medium --- The previous lesson built the [arithmetic](/algorithms/mathematical-algorithms/number-theory-basics) of $\mathbb{Z}_m$: addition, multiplication, and the modular inverse via the extended Euclidean algorithm. One operation remains: **exponentiation** — given $a$, $n$, and a modulus $m$, compute $a^n \bmod m$. The obvious loop multiplies $a$ into an accumulator $n$ times, which is $\Theta(n)$, far too slow when $n$ is a 1024-bit number, as it routinely is in cryptography. **Repeated squaring** does it in $O(\log n)$ multiplications, and underlies primality testing, the modular inverse, and the public-key primitives that secure the internet. ## Binary exponentiation: repeated squaring The idea is to read $n$ in binary. Write $n = \sum_i b_i 2^i$ with $b_i \in \{0,1\}$. Then $$ a^n = a^{\sum_i b_i 2^i} = \prod_{i \,:\, b_i = 1} a^{2^i}. $$ The numbers $a^{2^i}$ are just the **repeated squares** of $a$: each one is the square of the previous, since $a^{2^{i+1}} = \parens{a^{2^i}}^2$. So we sweep the bits of $n$ from least to most significant, keeping a running square $a^{2^i}$, and whenever the current bit is $1$ we multiply that square into the result. $$ % caption: Square at each step; multiply the running square into the accumulator where the % bit of $n$ is $1$ \begin{tikzpicture}[ every node/.style={font=\small}, box/.style={draw, minimum width=12mm, minimum height=7mm, inner sep=2pt}, >=stealth] \definecolor{acc}{HTML}{2348F2} % bit column of n = 13 = 1101 \node (lab) at (-1.7,0.4) {$n=13$}; \node (lab2) at (-1.7,-0.1) {$=1101_2$}; \node[box] (b0) at (0,0) {$b_0{=}1$}; \node[box] (b1) at (0,-1) {$b_1{=}0$}; \node[box] (b2) at (0,-2) {$b_2{=}1$}; \node[box] (b3) at (0,-3) {$b_3{=}1$}; % squares column \node[box] (s0) at (3,0) {$a$}; \node[box] (s1) at (3,-1) {$a^2$}; \node[box] (s2) at (3,-2) {$a^4$}; \node[box] (s3) at (3,-3) {$a^8$}; \draw[->] (s0) -- node[right, font=\footnotesize] {square} (s1); \draw[->] (s1) -- node[right, font=\footnotesize] {square} (s2); \draw[->] (s2) -- node[right, font=\footnotesize] {square} (s3); % accumulator: selected squares (bits 0,2,3) multiplied in \node[box, fill=acc!15, draw=acc, very thick] (r) at (7,-1.5) {$a\,a^4\,a^8=a^{13}$}; \draw[->, draw=acc, thick] (s0.east) -- (r.west); \draw[->, draw=acc, thick] (s2.east) -- (r.west); \draw[->, draw=acc, thick] (s3.east) -- (r.west); \end{tikzpicture} $$ Each square is one multiplication and there are $\lfloor \log_2 n \rfloor + 1$ of them; each bit costs at most one more multiplication into the accumulator. So the total is at most $2\lfloor \log_2 n \rfloor + O(1)$ multiplications, which is $O(\log n)$.[^clrs-modexp] Reducing modulo $m$ after every multiplication keeps every intermediate value below $m^2$. ```algorithm caption: $\textsc{ModPow}(a, n, m)$ — iterative bit-scan, returns $a^n \bmod m$ $result \gets 1$ $a \gets a \bmod m$ while $n > 0$ do if $n \bmod 2 = 1$ then // low bit set $result \gets (result \cdot a) \bmod m$ $a \gets (a \cdot a) \bmod m$ // square for next bit $n \gets \lfloor n / 2 \rfloor$ return $result$ ``` ::impl{algo="mod_pow"} For example, run this on $3^{13}\bmod 7$: the running square is $3,2,4,2$ across the bits of $13=1101_2$, and the accumulator picks up a factor at each set bit, finishing at $3$. $$ % caption: $\textsc{ModPow}(3,13,7)$ traced — bits of $13=1101_2$ drive % square-and-multiply \begin{tikzpicture}[every node/.style={font=\small}, x=1cm, y=1cm] \definecolor{acc}{HTML}{2348F2} \node at (0,0) {bit}; \node at (1.3,0) {$a^{2^i}\bmod 7$}; \node at (3.3,0) {mult?}; \node at (4.9,0) {result}; \draw[thick] (-0.6,-0.4) -- (5.6,-0.4); \node at (0,-0.9) {$1$}; \node at (1.3,-0.9) {$3$}; \node[acc] at (3.3,-0.9) {yes}; \node at (4.9,-0.9) {$3$}; \node at (0,-1.6) {$0$}; \node at (1.3,-1.6) {$2$}; \node at (3.3,-1.6) {no}; \node at (4.9,-1.6) {$3$}; \node at (0,-2.3) {$1$}; \node at (1.3,-2.3) {$4$}; \node[acc] at (3.3,-2.3) {yes}; \node at (4.9,-2.3) {$5$}; \node at (0,-3.0) {$1$}; \node at (1.3,-3.0) {$2$}; \node[acc] at (3.3,-3.0) {yes}; \node at (4.9,-3.0) {$3$}; \draw[acc, very thick] (4.4,-2.7) rectangle (5.4,-3.3); \node[acc, font=\footnotesize] at (2.5,-3.9) {$3^{13}\bmod 7 = 3$}; \end{tikzpicture} $$ The same computation has a clean recursive shape, splitting the exponent in half: $$ a^n = \begin{cases} 1 & n = 0,\\[2pt] \parens{a^{n/2}}^2 & n \text{ even},\\[2pt] \parens{a^{\lfloor n/2 \rfloor}}^2 \cdot a & n \text{ odd}. \end{cases} $$ ```algorithm caption: $\textsc{ModPow-Rec}(a, n, m)$ — recursive halving if $n = 0$ then return $1$ $h \gets \textsc{ModPow-Rec}(a, \lfloor n/2 \rfloor, m)$ $h \gets (h \cdot h) \bmod m$ if $n \bmod 2 = 1$ then $h \gets (h \cdot a) \bmod m$ return $h$ ``` The recursion descends by halving the exponent and rebuilds the answer on the way back up: each return squares the child's value, and an odd exponent multiplies one extra copy of $a$. For $a^{13}$ the four downward halvings $13\to6\to3\to1\to0$ unwind into four squarings, three of them carrying the extra $\cdot a$ from an odd level. $$ % caption: Recursive halving for $a^{13}$ — each level squares, odd exponents multiply one % extra $a$ \begin{tikzpicture}[ every node/.style={font=\small}, box/.style={draw, minimum width=14mm, minimum height=7mm, inner sep=2pt}, >=stealth, x=1cm, y=1.2cm] \definecolor{acc}{HTML}{2348F2} \node[box] (e13) at (0,0) {$a^{13}$}; \node[box] (e6) at (0,-1) {$a^{6}$}; \node[box] (e3) at (0,-2) {$a^{3}$}; \node[box] (e1) at (0,-3) {$a^{1}$}; \node[box, fill=acc!15, draw=acc, very thick] (e0) at (0,-4) {$a^{0}{=}1$}; \draw[->] (e13) -- node[right, font=\footnotesize] {13 odd: f\/loor(13/2) = 6} (e6); \draw[->] (e6) -- node[right, font=\footnotesize] {6 even: 6/2 = 3} (e3); \draw[->] (e3) -- node[right, font=\footnotesize] {3 odd: f\/loor(3/2) = 1} (e1); \draw[->] (e1) -- node[right, font=\footnotesize] {1 odd: f\/loor(1/2) = 0} (e0); \draw[->, acc, thick] (e0.west) to[bend left=40] node[left, font=\footnotesize] {$1^2\,a=a$} (e1.west); \draw[->, acc, thick] (e1.west) to[bend left=40] node[left, font=\footnotesize] {$a^2\,a=a^3$} (e3.west); \draw[->, acc, thick] (e3.west) to[bend left=40] node[left, font=\footnotesize] {$(a^3)^2=a^6$} (e6.west); \draw[->, acc, thick] (e6.west) to[bend left=40] node[left, font=\footnotesize] {$(a^6)^2\,a=a^{13}$} (e13.west); \end{tikzpicture} $$ > **Warning (Overflow).** If $m$ is near the machine word size, the product $result \cdot a$ can > exceed 64 bits before the reduction. Use a **128-bit** accumulator (`__int128`), or a > $\textsc{MulMod}$ routine that multiplies modulo $m$ without overflowing. This bites > exactly in the Miller–Rabin tests below, where $m$ may be a full 64-bit number. The doubling structure is not special to integers. Replace "multiply" with **matrix multiply** and the identity $\brackets{\begin{smallmatrix}1&1\\1&0\end{smallmatrix}}^n = \brackets{\begin{smallmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{smallmatrix}}$ gives the $n$-th **Fibonacci number** in $O(\log n)$ matrix multiplications by the very same repeated-squaring loop. ::impl{algo="fibonacci_matrix"} ## Fermat's little theorem Repeated squaring lets us _compute_ large powers; number theory tells us what those powers _are_ modulo a prime. > **Theorem (Fermat's little).** If $p$ is prime and $\gcd(a, p) = 1$, then > $$a^{p-1} \equiv 1 \pmod p.$$ > **Proof sketch.** The set $\{a, 2a, \dots, (p-1)a\}$ taken mod $p$ is a permutation of > $\{1, 2, \dots, p-1\}$ (multiplication by a unit is a bijection on $\mathbb{Z}_p^\ast$). > Multiplying both lists, $a^{p-1}(p-1)! \equiv (p-1)! \pmod p$, and canceling the unit > $(p-1)!$ gives $a^{p-1} \equiv 1$. $\qed$ A corollary recovers the modular inverse from the previous lesson without the extended Euclidean algorithm: multiplying $a^{p-1} \equiv 1$ by $a^{-1}$ gives $$ a^{-1} \equiv a^{p-2} \pmod p, $$ a single $\textsc{ModPow}$ call. This only works for a **prime** modulus, but that is exactly the common case in competitive programming, where arithmetic is done modulo a fixed prime such as $10^9 + 7$.[^skiena-nt] For a general modulus, **Euler's theorem** generalizes Fermat: if $\gcd(a, m) = 1$ then $a^{\varphi(m)} \equiv 1 \pmod m$, where $\varphi$ is Euler's totient, giving $a^{-1} \equiv a^{\varphi(m) - 1}$. ::impl{algo="modular_inverse"} ## Primality testing How do we decide whether a number $n$ is prime? Three approaches, in increasing power. ### Trial division — $O(\sqrt n)$ If $n$ has a nontrivial factor it has one no larger than $\sqrt n$ (factors come in pairs $d \cdot (n/d)$, and the smaller is $\le \sqrt n$). So testing every candidate divisor up to $\lfloor \sqrt n \rfloor$ settles the question. ```algorithm caption: $\textsc{IsPrime-Trial}(n)$ — $O(\sqrt n)$ deterministic test if $n < 2$ then return false $d \gets 2$ while $d \cdot d \le n$ do if $n \bmod d = 0$ then return false $d \gets d + 1$ return true ``` ::impl{algo="primality_trial_division"} This is perfectly adequate for one moderate number (say $n \le 10^{14}$), and is the right tool when a problem hands you a single value. It is hopeless for a 200-digit cryptographic number, where $\sqrt n$ is astronomically large. ### The Fermat test — probabilistic Fermat's little theorem runs in reverse as a _compositeness_ detector. If $n$ is prime, then $a^{n-1} \equiv 1 \pmod n$ for every $a$ coprime to $n$. So if we find a single **witness** $a$ with $a^{n-1} \not\equiv 1 \pmod n$, then $n$ is _certainly composite_, and one $\textsc{ModPow}$ call refutes primality. If instead $a^{n-1} \equiv 1$, then $n$ is only _probably_ prime; repeat with several random $a$ to raise confidence. This asymmetry mirrors the [soundness](/algorithms/foundations/what-is-an-algorithm) versus [completeness](/algorithms/foundations/what-is-an-algorithm) distinction from the foundations. Read as a **primality test** ("declare prime when $a^{n-1} \equiv 1$"), it is _complete_: Fermat's little theorem guarantees that every prime passes, so no prime is ever wrongly rejected. But it is _not sound_ as a primality certifier: some composites pass too, so a "prime" verdict can be a false positive. Read as a **compositeness test** ("declare composite when $a^{n-1} \not\equiv 1$"), the verdicts flip roles: now it is _sound_ (a failing base proves compositeness, so a "composite" verdict is never wrong) but _incomplete_ (it can miss composites that happen to pass). Which property holds depends on which answer is trusted. > **Remark (Which answer to trust).** The Fermat test is _complete_ for primes but > _unsound_ as a primality certifier; equivalently, it is a _sound_ compositeness test > (every "composite" verdict is correct) that is merely _incomplete_. The single > trustworthy output is "composite": a witness convicts $n$ with certainty, while a > "prime" output is only ever provisional. The test is unsound because of the **Carmichael numbers**: composites such as $561 = 3 \cdot 11 \cdot 17$ for which $a^{n-1} \equiv 1 \pmod n$ holds for _every_ $a$ coprime to $n$. No choice of coprime witness exposes them, so the Fermat test declares them prime no matter how many rounds are run, and there are infinitely many of them. A stronger test is needed. ::impl{algo="fermat_test"} The full square-root chain for $561$ shows what the Fermat test misses. With witness $a=2$ and $560 = 2^4\cdot 35$, the chain ends at $1$, so the Fermat test, which checks only that last entry, passes $561$. But the chain reaches $1$ from $67$, a value that is neither $+1$ nor $-1$. A prime can never square a non-$\pm1$ residue to $1$, so this one extra observation proves $561$ composite. $$ % caption: The Carmichael number $561$ passes Fermat ($a^{560}\equiv 1$) but fails % Miller–Rabin: the chain hits $1$ from $67$, a nontrivial square root of $1$. \begin{tikzpicture}[ every node/.style={font=\small}, box/.style={draw, minimum width=11mm, minimum height=8mm, inner sep=2pt}, >=stealth, x=1cm, y=1cm] \definecolor{acc}{HTML}{2348F2} \useasboundingbox (-1.5,1.9) rectangle (10.4,-2.0); \node[box] (x0) at (0,0) {$263$}; \node[box] (x1) at (2.2,0) {$166$}; \node[box, fill=acc!15, draw=acc, very thick] (x2) at (4.4,0) {$67$}; \node[box] (x3) at (6.8,0) {$1$}; \node[box] (x4) at (9.0,0) {$1$}; \node[font=\footnotesize] at (0,0.85) {$a^{35}$}; \node[font=\footnotesize] at (2.2,0.85) {$a^{70}$}; \node[font=\footnotesize] at (4.4,0.85) {$a^{140}$}; \node[font=\footnotesize] at (6.8,0.85) {$a^{280}$}; \node[font=\footnotesize] at (9.0,0.85) {$a^{560}$}; \draw[->] (x0) -- node[above, font=\footnotesize] {sq} (x1); \draw[->] (x1) -- node[above, font=\footnotesize] {sq} (x2); \draw[->] (x2) -- node[above, font=\footnotesize] {sq} (x3); \draw[->] (x3) -- node[above, font=\footnotesize] {sq} (x4); \node[acc, font=\footnotesize, align=center] at (4.4,-1.1) {$67^2 = 1$,\\ but 67 is not +1 or -1}; \node[red!75!black, font=\footnotesize, align=center] at (9.0,-1.1) {Fermat only\\ sees this 1}; \end{tikzpicture} $$ ### Miller–Rabin Miller–Rabin strengthens the Fermat test by exploiting a second fact about primes: in $\mathbb{Z}_p$, the only square roots of $1$ are $\pm 1$. Write the even number $n - 1$ as $$ n - 1 = 2^{s} d, \qquad d \text{ odd}. $$ For a witness $a$, consider the chain obtained by computing $a^d \bmod n$ and then squaring it $s$ times: $$ a^{d},\; a^{2d},\; a^{4d},\; \dots,\; a^{2^{s-1}d},\; a^{2^{s}d} = a^{n-1} \pmod n. $$ If $n$ is prime, this chain must end at $1$ (Fermat), and the _first_ time it reaches $1$ it must arrive from $-1$, because $1$ has no square root other than $\pm 1$. So a prime forces one of two patterns: either $a^d \equiv 1$, or some $a^{2^r d} \equiv -1$ for $0 \le r < s$. If **neither** holds, we have found a $2^{r}d$-step value that is a nontrivial square root of $1$ (it squares to $1$ but is not $\pm 1$), which a prime can never have, so $a$ is a witness that $n$ is composite.[^clrs-mr] $$ % caption: A nontrivial square root of $1$ in the chain betrays a composite \begin{tikzpicture}[ every node/.style={font=\small}, box/.style={draw, minimum width=14mm, minimum height=7mm, inner sep=2pt}, >=stealth] \definecolor{acc}{HTML}{2348F2} \node (lab) at (-2.1,0) {n - 1 = $2^s d$}; \node[box] (x0) at (0,0) {$a^{d}$}; \node[box] (x1) at (2.4,0) {$a^{2d}$}; \node[box, fill=acc!15, draw=acc, very thick] (x2) at (4.8,0) {$a^{4d}$}; \node[box] (x3) at (7.4,0) {$a^{8d}$ = 1}; \draw[->] (x0) -- node[above, font=\footnotesize] {sq} (x1); \draw[->] (x1) -- node[above, font=\footnotesize] {sq} (x2); \draw[->] (x2) -- node[above, font=\footnotesize] {sq} (x3); % annotations \node[font=\footnotesize] at (4.8,-0.95) {not +1 or -1}; \node[acc, font=\footnotesize] at (4.8,-1.5) {nontrivial root of 1}; \node[font=\footnotesize] at (7.4,-0.95) {= 1}; \node[font=\footnotesize, align=center] at (4.8,1.15) {a prime can never\\ square a non-(+1 or -1) to 1}; \end{tikzpicture} $$ ```algorithm caption: $\textsc{Miller-Rabin}(n, a)$ — true if $a$ fails to witness compositeness write $n - 1 = 2^{s} d$ with $d$ odd $x \gets \textsc{ModPow}(a, d, n)$ if $x = 1$ or $x = n - 1$ then return true // probably prime repeat $s - 1$ times $x \gets (x \cdot x) \bmod n$ if $x = n - 1$ then return true // hit $-1$ return false // nontrivial $\sqrt 1$ ⇒ composite ``` ::impl{algo="miller_rabin"} Miller–Rabin remains a _sound_ compositeness test (a witness still proves $n$ composite), but its error is now **one-sided and bounded**. With **random witnesses**, each composite $n$ is exposed by at least three quarters of the possible $a$, so $k$ independent rounds leave a false-"prime" probability below $4^{-k}$. Carmichael numbers are _not_ immune, because the square-root check detects structure the Fermat test cannot. A "prime" verdict is still not a certificate — it reads "probably prime" — but the false-positive rate can be driven arbitrarily low by adding rounds, unlike the unbounded error the Fermat test suffers on Carmichael numbers. The test can also be made **deterministic** for bounded inputs: there is a fixed small set of bases that never errs below a threshold. Testing against the first twelve primes $\{2,3,5,7,11,13,17,19,23,29,31,37\}$ is a proven-correct deterministic primality test for all $n < 3.3 \times 10^{24}$, covering every 64-bit (indeed every 80-bit) integer with a dozen $\textsc{ModPow}$ calls.[^skiena-mr] > **Intuition.** The Fermat test checks only the _last_ link of the chain ($a^{n-1}=1$); > Miller–Rabin watches the whole chain collapse to $1$ and demands it pass through $-1$. > That extra check is what catches Carmichael numbers. Miller–Rabin decides _whether_ $n$ is prime but never produces a factor. [**Factoring**](/algorithms/mathematical-algorithms/sieve-and-factorization) a large composite is a separate, much harder problem; **Pollard's rho** finds a nontrivial factor in expected $O(n^{1/4})$ time using a cycle-detection trick on $x \mapsto x^2 + c \bmod n$, and is the standard tool for splitting numbers too big for trial division. (The next lesson handles factoring _small_ numbers wholesale with a sieve.) ::impl{algo="pollard_rho_factor"} ## Why this matters: cryptography Fast modular exponentiation and fast primality testing together underlie public-key cryptography. **RSA** picks two large random primes (found by Miller–Rabin), and both encryption and decryption are a single modular exponentiation $m \mapsto m^e \bmod N$. **Diffie–Hellman** key exchange computes $g^x \bmod p$ the same way. In every case the security rests on a power being easy to compute but its _inverse_ (factoring $N$, or the discrete logarithm) being infeasible, and $\textsc{ModPow}$ is what makes the easy direction $O(\log n)$. For contrast with the Carmichael trace, run the same square-root chain on a genuine prime, $n = 97$. Write $n - 1 = 96 = 2^5 \cdot 3$, so $s = 5$, $d = 3$; take witness $a = 5$. The chain is $a^d = 5^3 = 125 \equiv 28 \pmod{97}$, then repeated squares $28^2 \equiv 63$, $63^2 \equiv 96 \equiv -1$. It hits $-1$ at the third link, so Miller–Rabin returns "probably prime" immediately — and because $-1$ appeared, every later square is $+1$, exactly the pattern a prime is forced into. A composite would either miss $\pm1$ entirely or reach $1$ from a non-$\pm1$ value, as $561$ did. $$ % caption: Miller-Rabin on the prime $97$ with $a=5$: the chain reaches $-1$ (here % $96$), the pattern a prime must show; contrast $561$, which never does. \begin{tikzpicture}[ every node/.style={font=\small}, box/.style={draw, minimum width=12mm, minimum height=8mm, inner sep=2pt}, >=stealth, x=1cm, y=1cm] \definecolor{acc}{HTML}{2348F2} \useasboundingbox (-1.5,1.4) rectangle (8.4,-1.6); \node[box] (x0) at (0,0) {$28$}; \node[box] (x1) at (2.4,0) {$63$}; \node[box, fill=acc!15, draw=acc, very thick] (x2) at (4.8,0) {$96$}; \node[box] (x3) at (7.2,0) {$1$}; \node[font=\footnotesize] at (0,0.8) {$a^{3}$}; \node[font=\footnotesize] at (2.4,0.8) {$a^{6}$}; \node[font=\footnotesize] at (4.8,0.8) {$a^{12}$}; \node[font=\footnotesize] at (7.2,0.8) {$a^{24}$}; \draw[->] (x0) -- node[above, font=\footnotesize] {sq} (x1); \draw[->] (x1) -- node[above, font=\footnotesize] {sq} (x2); \draw[->] (x2) -- node[above, font=\footnotesize] {sq} (x3); \node[acc, font=\footnotesize, align=center] at (4.8,-1.05) {96 = -1 (mod 97):\\ prime pattern}; \end{tikzpicture} $$ ## Primality, factoring, and the quantum frontier Primality and factoring have sharply different complexity, and the modern results are worth knowing. **Primality is in P (AKS).** For decades, "is $n$ prime?" had fast _randomized_ answers (Miller–Rabin) and a fast answer _assuming_ the Riemann hypothesis (deterministic Miller under GRH), but no unconditional deterministic polynomial algorithm was known. In 2002 Agrawal, Kayal, and Saxena settled it: the **AKS primality test** decides primality in deterministic polynomial time, $\tilde O(\log^{6} n)$ in the original paper, placing PRIMES firmly in **P**.[^aks] It is a theoretical landmark rather than a practical tool — deterministic Miller–Rabin with a fixed base set is far faster for the sizes anyone actually tests — but it closed a question open since antiquity. **Factoring is (believed) hard.** No polynomial algorithm is known for the reverse problem of _splitting_ a composite. Pollard's rho finds a factor in $O(n^{1/4})$; the **quadratic sieve** and the **general number field sieve** (GNFS) do far better for large inputs, GNFS running in sub-exponential $\exp\!\big(O((\log n)^{1/3}(\log\log n)^{2/3})\big)$ time — still super-polynomial, the reason RSA moduli of 2048+ bits remain secure.[^gnfs] The current public factoring record (RSA-250, an 829-bit number, 2020) took thousands of CPU-core-years. **Shor's algorithm.** The asymmetry that protects RSA does not survive quantum computation. In 1994 Peter Shor gave a **quantum** algorithm that factors an $n$-bit integer in $O(n^2\log n\log\log n)$ time by reducing factoring to period-finding and using the quantum Fourier transform.[^shor] A large fault-tolerant quantum computer would break RSA and Diffie–Hellman outright, which is the entire motivation for **post-quantum cryptography** (lattice- and code-based schemes) now being standardized. The [Fast Fourier Transform](/algorithms/mathematical-algorithms/fast-fourier-transform) that appears later in this module is the classical analogue of the quantum Fourier transform in Shor's algorithm. ## Takeaways - **Binary exponentiation** computes $a^n \bmod m$ in $O(\log n)$ multiplications by **repeated squaring**, reading the bits of $n$ and multiplying in each square whose bit is $1$; reduce mod $m$ every step, and guard against **overflow** with 128-bit or $\textsc{MulMod}$ arithmetic. The same doubling gives $O(\log n)$ **Fibonacci** via matrix powers. - **Fermat's little theorem** ($a^{p-1} \equiv 1 \pmod p$) gives the modular inverse $a^{-1} \equiv a^{p-2}$ for a prime modulus; **Euler's theorem** generalizes it to $a^{\varphi(m)} \equiv 1$ for any coprime $a$. - **Trial division** tests divisors up to $\sqrt n$ in $O(\sqrt n)$ time, deterministic, fine for one moderate number. - The **Fermat test** detects composites probabilistically but is fooled by **Carmichael numbers** for every coprime witness. - **Miller–Rabin** writes $n-1 = 2^s d$ and watches the square-root chain $a^d, a^{2d}, \dots$ collapse to $1$, catching the nontrivial square roots that betray a composite; it is probabilistic with random witnesses and **deterministic** below $3.3 \times 10^{24}$ with the first twelve primes as bases. - Modular exponentiation and primality testing power **RSA** and **Diffie–Hellman**; **Pollard's rho** handles factoring of large numbers when a factor is actually needed. [^clrs-modexp]: **CLRS**, Ch. 31 — Number-Theoretic Algorithms (§31.6): modular exponentiation by repeated squaring in $O(\log n)$ multiplications, reducing mod $m$ at each step. [^skiena-nt]: **Skiena**, § — Number Theory: Fermat's little theorem and modular inverse via $a^{p-2}$ for a prime modulus. [^clrs-mr]: **CLRS**, Ch. 31 — Number-Theoretic Algorithms (§31.8): the Miller–Rabin witness test built on nontrivial square roots of $1$, with error below $2^{-2k}$ over $k$ rounds. [^skiena-mr]: **Skiena**, § — Number Theory: deterministic Miller–Rabin with a fixed small base set, and Pollard's rho for factoring. [^aks]: M. Agrawal, N. Kayal, N. Saxena, "PRIMES is in P," _Annals of Mathematics_ **160**(2), 2004 (announced 2002): the first unconditional deterministic polynomial-time primality test. [^gnfs]: A. K. Lenstra, H. W. Lenstra Jr. (eds.), _The Development of the Number Field Sieve_, Springer LNM 1554, 1993; and Pomerance, "A tale of two sieves," _Notices AMS_ **43**(12), 1996, for the quadratic sieve and GNFS running times. [^shor]: P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," _SIAM J. Computing_ **26**(5), 1997 (conference version 1994).