Skip to main content
Loading Explore guides…
Large Prime Number Generation · Acedra
Home
Explore
Mathematics
Large Prime Number Generation
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
44 segments
Copy
Hide video
0:00
What if I asked you to come up with a prime number that has thousands of digits? Could you do it? I mean, we’ve known for millennia that such huge primes exist, but how do you actually find one? To see why this is tricky, let’s take a smaller number, say 43, and try to divide it by 2, 3, 4, 5, up to 42. None of these divide 43 evenly, so 43 is prime. But for a thousand-digit number this doesn’t work -- you’d need far more
0:30
time and space than the universe allows to check through all those possible divisors. And yet, computers can churn out prime numbers with thousands of digits! Or at least, they can generate huge numbers that they are almost certain are prime -- up to 99.9999% confidence. This isn’t just some party trick or obscure math experiment -- large prime number generation is essential to keeping your information secure on the internet.
0:57
But, how do computers find such big prime numbers? And why aren’t they 100% sure these numbers are actually prime? To answer that, we need to go back to the 17th century, where the famous French mathematician Pierre de Fermat was studying various properties of prime numbers. In the year 1640, he discovered a fundamental property that all prime numbers share, which would later become one of the central techniques for testing if a number is prime.
1:25
The setup Fermat was exploring involves choosing any prime number p, like 17, and any positive integer a less than p, for example, 2. What he proved was that if you take a^(p - 1) and you divide that number by p, then the remainder of the division is always 1. Another way of saying that is a^(p - 1) is always 1 more than a multiple of p. In fancier Number Theory terms, we’d write this as a^(p - 1) ≡ 1 (mod p), which became known as Fermat’s Little Theorem.
2:06
The word “mod” here stands for modular arithmetic, which is a type of number system where, essentially, all numbers are thought of as congruent to their remainder when divided by the modulus, which in this case is p. It should be noted here that the way computers actually do exponentiation in modular arithmetic (or modular exponentiation) works a bit differently than simply exponentiating and taking the remainder afterwards.
2:32
Doing things like this, the numbers would get way too big. So instead there’s a much more efficient way that computers do modular exponentiation. I’ve put the pseudocode for this on screen here if you’re interested. We’ll be doing modular exponentiation repeatedly throughout this video, so you should know that at times when I simply assert a result like 12^34 ≡ 16 (mod 56), I used this algorithm to do that calculation quickly. Now, back to the story.
3:00
After Fermat proved his little Theorem, mathematicians were interested in using it to test whether a number is prime, leading to what we now know as the Fermat Primality Test: If you want to know whether a number n is prime, say 51, first pick a number “a” which is less than n (let’s pick a = 2). Now, see if a^(n - 1) ≡ 1 (mod n). In our case that’s 2^50 which is congruent to 4 (mod 51), not congruent to 1. This tells us that 51 (our value for n) is composite
3:36
(meaning not prime) -- otherwise it would be a counterexample to Fermat’s Little Theorem. And 51 is indeed composite: it factors into 3 × 17. Here we would say that the value of a we used (which was 2) is a “witness” to the compositeness of 51. Let’s do another example, this time where the number is prime. Say we want to test n = 17, and we use a = 5. Now we compute a^(n - 1) (mod n) which in this case is 1, satisfying the congruence of Fermat’s Little Theorem. So the test declares
4:13
that 17 is prime. And this is of course true. But everyone knew there was a big problem with the Fermat Primality Test. It was… wrong. Or at least, sometimes it was wrong. For example, let’s test if 561 is prime using a = 100. 100^560 ≡ 1 (mod 561). It passes the test. But 561 is not prime! It’s equal to 3 × 11 × 17. The problem is that while Fermat’s Little Theorem guarantees a^(n - 1) ≡ 1 (mod n) when n is prime, the congruence could also hold in some cases when n is composite!
4:58
Here, the value for a of 100 is called a “liar” since in a sense it “lied” about the primality of 561 -- satisfying the congruence from Fermat’s little theorem despite 561 not being prime. You might think, “Okay, let’s just try more values of a.” And this could work: with a = 42, we get 42^560 ≡ 375 (mod 561). 375 is not equal to 1, so in this case 561 correctly fails the test. But as it turns out, for the number 561,
5:36
most values of a -- most “bases” as they’re called are liars -- in fact 561 is the first in a special group of numbers called Carmichael numbers where the chances of Fermat’s Test giving an incorrect answer are exceedingly large. Carmichael numbers are composite, but they have the special property that they nevertheless always pass the Fermat Test unless they share a factor with the base used. 42 was able to correctly identify 561 as
6:06
composite because 42 and 561 share a factor: they’re both multiples of 3. So here’s the problem: after the first seven Carmichael numbers were discovered by Václav Šimerka, a Czech mathematician from the 1800s, another famous mathematician, Paul Erdős, would come up with heuristic evidence leading him to conjecture that there were infinitely many of them. Robert Carmichael himself, who studied these numbers extensively, agreed.
6:34
If there were indeed infinitely many Carmichael numbers, it would also mean there are really really big ones. And randomly stumbling on a base that shares a factor with these gigantic Carmichael numbers is incredibly unlikely — basically as hard as factoring the number outright, like we were talking about at the beginning of the video. You may as well not even try -- there were likely huge numbers out there for
6:57
which Fermat’s Test is doomed to fail. In 1994, Red Alford, Andrew Granville and Carl Pomerance would prove that there are in fact infinitely many Carmichael numbers, confirming everyone’s suspicion that the Fermat Test had a fatal flaw. But two decades before then, in the early 1970s, a PhD student at UC Berkeley named Gary Miller was already designing a better primality test. He wanted to find a way to improve on the Fermat test by avoiding the false positives caused by
7:28
Carmichael numbers. His moment of insight came when he realized he could break up the exponentiation of a^(p - 1) from Fermat’s Little Theorem into a sequence of smaller exponentiations. Here’s how it works: imagine you have a number n and want to check if it’s prime. Fermat’s Little Theorem says that if n is prime, then a^(n - 1) ≡ 1 (mod n). This congruence alone gives some evidence towards n being prime, but remember, it’s not definitive -- there could be composite
8:01
numbers that satisfy the congruence too. So instead of just computing a^(n - 1), Miller has a clever idea. Let’s do an example with n = 561 and a = 100 again. Miller’s first step is still to compute a^(n - 1) (mod n) -- for us that’s 100^560, which is congruent to 1 (mod 561). This is where Fermat’s Test would stop and falsely declare 561 to be prime. But Miller doesn’t stop here -- now he divides 560
8:37
by 2 to get a new exponent, 280, and takes 100^280 (mod 561). And now we keep dividing this exponent by 2, computing 100^140, 100^70, and 100^35. 35 is odd, so we can’t divide by 2 anymore, which means we stop here. For the Fermat Test, we just computed a^(n - 1). But here we have more information: a whole sequence of smaller exponentiations leading up to a^(n - 1). For our example, the sequence goes 298, 166, 67, 1, and 1. So how does Miller use this sequence? Well,
9:22
Miller’s Test says a number is prime if two conditions are true. For now, I’ll tell you what they are, and a little later, I’ll tell you the reason behind them. The first condition is that the sequence ends with the number 1. Here, that’s true. But the second condition is that any time there is a 1 in the sequence, any number immediately before it must itself be a 1 or it must be n - 1 (in this case, 560). Here you can see that the number immediately
9:51
before the final 1 is also a 1, but the number before that is 67 -- not 1 and also not 560. Condition number 2 fails, so the result of the test is that 561 is composite, which is correct! 100 is a witness to the compositeness of 561 using Miller’s test, whereas we saw earlier that 100 is a liar for 561 using Fermat’s Test! Let’s do another example with n = 41. The first step is to pick a base “a”. Let’s go with 8. Now take a^(n - 1) (mod n), or 8^40 (mod
10:32
41), and from here compute the sequence of smaller exponentiations in reverse by repeatedly dividing the exponent by 2. Here the final sequence is 9, 40, 1, and 1. Let’s bring back Miller’s two conditions to say whether n is prime. The first condition is that the sequence ends with a 1. Here that’s true. Next, we need to check that every number before a 1 is either 1 or n - 1 (in this case, 40). And here this is also true: the number before the final 1 is a 1 and the number before
11:08
that is 40. Because both conditions are satisfied, the test says 41 is prime, which is correct! So why did Miller choose these two conditions? Well, the first condition (that the final number in the sequence must be a 1) is actually exactly the same as Fermat’s Test, which says that a^(n - 1) (which is the final number in the sequence) has to be congruent to 1 (mod n). The heart of Miller’s Test comes from condition number 2, where he leverages a neat fact from Number Theory.
11:41
This fact is that that if you're working in modular arithmetic with a prime modulus, p, then the only square roots of 1 are 1 and p - 1. In other words, if some number squared is congruent to 1 mod p, where p is prime, then that number must be either 1 or p - 1. This is kind of like how in the real numbers, the only square roots of 1 are 1 and -1. In modular arithmetic, p - 1 is congruent to -1 since it’s 1 less than a multiple of p. So the interesting thing
12:15
to take note of here is that this fact about square roots still holds in modular arithmetic, as long as the modulus is prime. Now why does that matter? Well, think about the sequence of exponentiations you get when you do Miller’s Test. Taking our example from earlier, each subsequent exponent doubles from the previous one, which means that each subsequent term in the sequence is congruent to the previous term
12:39
squared. So if n is prime, then any time there’s a 1 somewhere in the sequence, its predecessor must be 1 or n - 1. Otherwise, the number 1 would have a square root that isn’t 1 or n - 1, and that can only happen if n is composite. This requirement is what causes 561 to be recognized as composite in this example, since, as we see here, the number 67 is a square root of 1 mod 561. That’s the core insight behind Miller’s test: by watching for these “illegal” square roots in the
13:15
sequence of exponentiations, this second condition can catch numbers that would otherwise sneak past Fermat’s test. So Miller’s Test was a strict upgrade to Fermat’s Test -- it worked correctly on all the examples that Fermat’s Test did, plus many more due to condition number 2. But despite this improvement, Miller’s Test still wasn’t perfect. We can see this with the following example: Let’s test n = 221 with a = 174. The results of the exponentiations in this case go 47, 220,
13:48
and 1. Here both conditions are met -- there’s a 1 at the end of the sequence, and the number before it is 220, which is n - 1. So the test says 221 is prime. But 221 is not prime -- it’s 13 × 17! 174 is a liar to the primality of 221. So was Miller’s test also doomed? Well, not exactly. Miller knew that his test could still be fooled by some bases, just like Fermat’s Test. But he had one more trick up his sleeve. In sifting through centuries of relevant
14:27
literature, he had come across the work of Emil Artin from the 1920s, who first formulated an extension of a famous unproven conjecture known as the Riemann Hypothesis. The specifics of the Extended Riemann Hypothesis are a whole new can of worms, but long story short it has implications on the distribution of prime numbers, and Miller could mathematically prove that if the Extended Riemann Hypothesis is true, his primality test would never
14:54
be fooled too many times -- with enough different bases, it would never give an incorrect answer. Specifically, for every composite number n, there would always be some base less than 2(ln n)^2 that serves as a witness to n’s compositeness. In other words, to check whether a number n is prime, all you need to do is run Miller’s test using every base less than 2(ln n)^2. You can see here that you really don’t need to check too many additional bases as the numbers get bigger -- even
15:28
when you start getting to many thousands of digits, this is still efficient enough to do on a computer. With this test you can definitively verify primality, and you can do it efficiently! But this was all contingent on the Extended Riemann Hypothesis being true -- a conjecture that is still unproven as of this video’s publication. So we had two options: option 1 was to carry on using Miller’s test, and assuming that the Extended Riemann Hypothesis is true.
15:55
After all, most mathematicians believe it is, and all evidence we have so far suggests so too. But option 1 was dangerous for an unexpected reason. In the years following the invention of Miller’s test, other number theorists had begun to come up with cryptography schemes whose heart and soul relied on the generation of huge prime numbers. If Miller’s test was wrong, it could put millions of peoples’ private information in jeopardy. You can learn how large prime number generation
16:23
is involved in modern encryption from my previous two videos if you’d like. Option 1 wasn’t good enough. So what was option 2? It was to change the test. You see, in creating his original algorithm, Miller had managed to figure out something quite interesting -- even though some bases would cause the test to mark a composite number as prime, he could show that for any odd composite number,
16:49
at least 50% of the possible bases were witnesses to its compositeness. That might not seem like a very high proportion, but it means that if you run the test over and over again with random bases and each time it says a number is prime, the chance that number was actually composite drops exponentially -- after just 10 iterations that all say a number is prime, the chance of a false positive is at most one in a thousand. You’d be more likely to flip
17:16
10 heads in a row with a coin. If you want to run it even more times just to be sure, you can get as close to 100% confidence as you’d like with enough iterations. Years after he published his paper, Miller crossed paths with Michael Rabin, at the time a professor at Harvard. Rabin immediately recognized the importance of Miller’s work and eventually was able to show that the proportion of bases that are witnesses is even better than
17:44
50% -- it’s at least 75%. This gave an improved estimate on how many times you’d have to run the test to have a high confidence of correctness -- now with just 10 iterations, the chance of a false positive would be at most 1 in a million. Rabin published a paper in 1980 popularizing this probabilistic approach, which people quickly started calling the Miller-Rabin primality test. The Miller-Rabin test became the gold standard for primality testing in practice. You’ve
18:14
probably already used it today multiple times without even thinking about it. Every time you visit a secure website, or send a message on the internet, there’s a good chance the encryption algorithms involved were using the Miller-Rabin test to generate big primes. But hold on -- testing if a number is prime and generating a prime from scratch are two different things. So there’s still one more piece to the puzzle here. And it
18:38
yet again involves another fundamental and beautiful result from Number Theory. What I find most interesting about how computers generate huge prime numbers is that the core idea behind it is almost absurdly simple. The basic strategy to generate a prime number with n digits is as follows. Step 1: pick a random number with n digits. Step 2: check if that number is prime. If it is, output that number. If it isn’t, then repeat! And keep repeating until you find a prime.
19:09
But the logic behind repeating until you find a prime is nuanced. It requires that the chances of a random number actually being prime are high enough to guarantee that a prime number will be found in a reasonable amount of time. Here’s where one of the most famous results from Number Theory comes in: the Prime Number Theorem. The Prime Number Theorem gives a remarkably simple estimate for the density of prime numbers. In a probabilistic interpretation, It states that
19:37
the chance of a random n-digit number being prime is roughly 1/(ln(10)*n), or 1/2.3n. Here’s a graph that shows the probability of a random n-digit number being prime. Roughly 1 in every 23 ten-digit numbers is prime, and roughly 1 in every 230 hundred-digit numbers is prime. For thousand-digit numbers, it’s 1 in 2300. And so on. 1 in 2300 might seem like a pretty low chance but if you change your perspective a bit, it means if we pick numbers at random and check
20:12
them using the Miller-Rabin test, we’ll likely find a thousand-digit prime after just a couple thousand tries on average. For computers, that’s no problem at all: they can perform these tests in milliseconds, meaning they can generate huge prime numbers in no time. Since we’ve been talking purely in theory so far, I thought it would be nice to code up a large prime number generator using the Miller-Rabin test, and actually use it
20:36
to generate a huge prime. Here you can see my implementation in Python -- The full code for this and also the modular exponentiation code I showed earlier is in my Discord server as well in case you want to take a closer look. Just for fun, let’s generate a prime number with one digit for every 10 subscribers to this channel, which is 22812 as I’m making this part of the video, so 2281 digits. If you want to make this video out of date as soon as possible,
21:06
feel free to subscribe! And there’s our 2281-digit prime! (with 99.9999% confidence from using 10 random bases per iteration). I’m sure a bunch of you will find lots of ways to optimize this code, but with the implementation I have here, running this program took just a couple minutes on my computer, and I also got a bit lucky this time in that the program finished in fewer iterations than expected. Something I love about this story is that one
21:36
of the core ideas that made everything work was allowing for randomness and uncertainty in an algorithm that had a purely deterministic purpose. But there’s one more plot twist! In 2002, decades after the Miller-Rabin algorithm was published and became the gold standard primality test, a Professor and two undergraduate students at IIT Kanpur in India devised a completely deterministic primality test -- one that was always correct with
22:02
100% certainty. The test became known as the AKS primality test, named after its three inventors. However the AKS test, while a remarkable theoretical achievement, is unfortunately not very useful in practice, as it runs much slower than the Miller-Rabin test. The full story is maybe for another video but it raises an intriguing possibility: could there be an even better primality test out there, one that’s both fast and completely deterministic? Or could advances in
22:32
Number Theory one day prove the Extended Riemann Hypothesis, finally making Miller’s original test unconditionally correct? Either way, the search for prime numbers continues, and it remains one of the most fascinating intersections of mathematics and computer science. Thanks for watching.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat