Ten Little Algorithms, Part 8: Miller-Rabin Primality Test (and Living with Uncertainty) - Jason Sachs

-->

--><br>-->

-->

--><br>-->

-->

Blogs

Home<br>Blogs<br>Forums<br>Quizzes!<br>Courses<br>Tutorials<br>Books<br>Free PDFs<br>Webinars<br>Code Snippets<br>Login / Register

Home<br>Blogs<br>From the Editor

Recent Posts

Popular (this month)

Popular (all time)

Forums<br>Quizzes!<br>Courses<br>Tutorials<br>Books<br>Free PDFs<br>Webinars<br>Code Snippets

-->

--><br>Blogs Jason Sachs<br>Ten Little Algorithms, Part 8: Miller-Rabin Primality Test (and Living with Uncertainty)<br>Jason Sachs●May 18, 2026

It’s been a while since I wrote the last part in this series, but in working on something else, I accidentally ran into a good candidate for a follow-up with the Miller-Rabin primality test. We’ll explore this algorithm — and as a bonus, if you read this article, you’ll get Pollard’s rho algorithm for factoring — absolutely ☞☞☞ FREE ✪✪✪, operators are standing by, so act now!

Other articles in this series:<br>This article is available in PDF format for easy printing

Part 1: Russian Peasant Multiplication

Part 2: The Single-Pole Low-Pass Filter

Part 3: Welford's Method (And Friends)

Part 4: Topological Sort

Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method

Part 6: Green’s Theorem and Swept-Area Detection

Part 7: Continued Fraction Approximation

A funny thing happened to mathematics and physics in the 20th century. Rigid concepts of provability and certainty broke down around 1930, notably with Gödel’s incompleteness theorem and Heisenberg’s uncertainty principle. There are, of course, more everyday notions of incompleteness and uncertainty. I don’t think we’ve grasped these ideas very well in the embedded systems world, and instead of improving our engineering tradeoffs, we’re going down a dangerous road in the name of expediency, understating the consequences of making mistakes. I’ll explain in a roundabout way in this article, through prime numbers and RSA encryption, and in a follow-up article. (This article was originally going to be titled Good, Fast, Cheap: Choose Two, but I decided to save that for another day.)

We’ll start with prime numbers.

Prime Numbers

Suppose you are in need of a large prime number — remember, these are positive integers that cannot be written as a product of two smaller positive integers — because you want to use RSA encryption to communicate securely. Or maybe you just collect prime numbers, and you want one to tattoo on your arm. Whatever.

So you generate some large odd random numbers which are candidates, and you want to check to see if they are prime. This isn’t a wild goose chase: the Prime Number Theorem says that for large \( N \), the prime-counting function \( \pi(N) = \) the number of primes less than \( N \), is approximately \( N / \ln N \), asymptotically approaching it as N gets larger. Prime numbers aren’t actually that rare; the density of prime numbers around \( N \) is approximately \( 1 / \ln N \). This means that for M-bit numbers (that are on the order of \( N=2^M \)), approximately one out of every \( \frac{1}{2} M \ln 2 \) odd values is prime, so on average roughly one out of every 11 odd 32-bit numbers is prime, one out of every 22 odd 64-bit numbers is prime, one out of every 44 odd 128-bit numbers is prime, and so on.

You might say: well, that’s just the average distance between prime numbers; surely there are bunches where they are more common, and “deserts” where they are less common. This is an area of obsessive study among a subset of very respectable mathematicians, who have defined the “prime gap” \( g_n = p_{n+1} - p_n \) as the difference between successive prime numbers; indeed, there was a recent improvement in 2014 on a lower bound on this gap, proving that

$$\max_{p_{n+1} \leq X} (p_{n+1}-p_n) \gg \frac{\log X \log \log X\log\log\log\log X}{\log \log \log X},$$

which is oddly mesmerizing, something like a mathematical analogloglogue of the phrase “How much wood could a woodchuck chuck if a woodchuck could chuck wood?” They — the subset of very respectable mathematicians — have also defined a ratio called the “merit” of prime gaps, which is the ratio \( M = g_n / \ln p_n \) — basically how much larger the actual gap \( g_n \) is than the average gap \( \ln p_n \) — and so far, the largest known merit \( M \) has topped out at just under 42: the 288-bit number \( p_n = \) 293703234068022590158723766104419463425709075574811762098588798217895728858676728143227 has a gap \( g_n = 8350 \) between it and its next-higher prime neighbor. So for 288-bit numbers, you might have to check half of the worst-case gap \( g_n = 8350 \) — in other words, 4175 different odd 288-bit numbers — instead of the average gap of 100 odd numbers. Even 4175 isn’t a very large set of numbers to check.

(A list of prime gaps was maintained for about 20 years by a Dr. Nicely, now sadly deceased, who also discovered the Pentium division bug while running calculations in his number theory research. In this...