One of my professors gave this problem as a homework question a while ago. By now I would expect that it is in wide circulation, but just in case you haven’t seen it already, please enjoy.
Imagine that you are an arctic explorer. You are about to leave town to head into the wild, for some irrelevant reason, and when you get to your destination, you will need to light a fire in order to survive. If you can’t light a fire when you get there, then you will die. At your destination there is plenty of fuel and a fool-proof furnace that always lights on the first try, so you don’t need to worry about that. The thing that you need to worry about is getting there with a match to light the furnace. Unfortunately, you don’t have any matches yet.
In the town there is a store that sells matches. The clerk of the store is the only other inhabitant of the town. You have enough money to buy many boxes of matches, and the clerk in the store is happy to sell you as many boxes of matches as you like. Each box is guaranteed to contain 100 matches. If you are worried that the clerk will sell you a box filled with nothing, you can open each box and count them before you buy them. The clerk won’t mind.
However, there is a twist. For reasons that are beyond the scope of this problem, the clerk wants to kill you, and you are well aware of this fact. You also know that the clerk has found a way to undetectably remove matches from a matchbox, tamper with them so that they don’t light and put them back into the box. The only way to tell whether a match has been tampered with is to try it–if it lights, then it was good, but it’s no longer good. Each match can only be used once, so the only way to find out whether a match is good or bad is to destroy it. The matches are 100% reliable when they arrive at the store; the only ones that will fail are the matches that the clerk has ruined.
So, the problem really boils down to this: you need to buy matches from the clerk. If you leave the store with at least one working match, you live. Otherwise, you’re dead.
Your honest and pacifist beliefs prevent you from killing the clerk, stealing his matches, or trying to influence him in any other way. The clerk, for similar reasons, can only kill you by selling you boxes of matches that he’s carefully manipulated. The only interaction you can have is to make sure that each box contains the expected number of matches, buy boxes of matches, and try them.
What’s a good strategy?
This might all seem a little contrived, but hey, it’s a math problem.
Well, actually it’s not only a math problem. It’s also related to cryptography, and so we’re going to make it a little more difficult.
The clerk knows your strategy. You can’t keep any secrets from him, even though he can keep secrets from you. He will know what steps you are going to take before you do. He can practice and hone his strategy to increase his effectiveness at killing you.
This is exactly what cryptographers have to deal with. Their adversaries can buy or acquire duplicates of the systems that they want to break and spend as much time as they need studying the system before they make their real attack. When a burglar picks the lock of your door, it isn’t beginners luck–he’s been practicing opening locks just like yours for months.
And just to make things a little more interesting, let’s throw in a little game theory. Let’s say that you don’t really need to go on your expedition. You could skip the whole thing and stay home. You’ll give up your chance for fortune and glory, but you’ll probably live to a ripe old age and die comfortably, surrounded by loved ones, rather than cursing the name of the clerk while you freeze to death in the middle of nowhere.
What to do?
I’ll let you think about it for a little while, but before I do I’m going to drop a bunch of clues. You should stop reading now if you would prefer to bash your head against this problem for a while.
There are certain kinds of mathematical problems that nobody knows how to solve–or at least, if anyone knows how to solve them, they aren’t saying so. This may be because some of the problems have the property that being able to solve these kinds of problems could be enormously valuable to certain people and/or governments.
Despite the temptation, I will avoid describing any of these problems in depth, and will only mention one quickly and without any rigor.
Given a very large number (say, several hundred digits in length) that is the product of two large primes (a few hundred digits in length), there is no known efficient way to discover those two primes. If you can keep those primes secret, it is extremely unlikely that someone else will be able to figure them out, and since there are a mind-numbing number of such large primes, the probability that someone else will stumble across one is not even worth mentioning. (they only need to find one, because after they’ve found one, they can find the other by dividing the product by it to find the second.)
This is an example of a particular kind of problem that is very hard to solve, but very easy to verify the solution. Another example is opening a safe; for any given sequence of numbers, it’s easy to check whether they open the safe, but there’s no way to find the right sequence short of trying many, many sequences.
All of this would be no more than a mathematical curiosity, however, if it wasn’t for a second fact. Large numbers that are the product of two large primes can be used as the building blocks for mathematical structures that behave in some ways like ordinary numbers and in other ways quite differently. Most importantly, it is impossible to interpret the results in a meaningful way without knowing the prime factors.
I’m sure that mathematicians are cringing by now, but that’s OK. They’re probably inured to this sort of casual imprecision from the hoi polloi.
So, if you know the prime factors, you can do calculations that nobody else will be able to understand. By paths that I will not cover, I will assert that this can be used to create secret codes that are unbreakable by anyone who can’t find the primes, which is, as far as anyone knows, everyone.
This has all been known for a long time, but it had very little practical use until relatively recently, because there was a terrible problem that remained to be solved: finding large primes is as difficult as factoring large numbers. The only way to prove that a number is prime is by showing that it has no non-trivial factors, and the only way to do that is by trial and error. For large numbers, that’s a lot of trials and errors.
Primes were so hard to find, and so incredibly valuable–since they could be used to create nearly unbreakable codes–that some of them were considered state secrets.
Fortunately, a way was discovered around this.
Gary Miller discovered (or observed, or whatever) that there are certain functions that can test with absolute certainty whether a number is not a prime. Instead of the usual “yes” or “no” that we expect from most tests, these functions have the outcomes “I don’t know” or “no”. If the Miller test answers “no”, then the number is absolutely not a prime. This doesn’t tell us what its factors are (in the general case) but we know that it’s not a prime.
The Miller test takes a number and computes a function of that number and the candidate number. If the number fails the test (when the answer is “no”) then it is called a witness to the non-prime nature of the candidate.
That’s not very useful yet–we could construct a test that did the same thing just by saying “I don’t know” nearly all of the time, except when it happened to stumble across a factor, and then it would say “no”. This would not represent progress.
Miller wasn’t the first to develop such a test; Fermat had one, all the way back at the dawn of number theory, but it wasn’t very good and some composites actually didn’t have any witnesses at all. Solovay and Strassen had a much better one–more witnesses–but Miller’s was the best because it said “no” much more often as “I don’t know” for most composites. For an arbitrary large non-prime, approximately three quarters of the numbers less than the non-prime are witnesses.
Unfortunately, there was no telling where the witnesses might be. They didn’t arrange themselves nicely, and instead were sometimes clumpy.
Rabin, in what in retrospect seems obvious but at the time was a completely new and ground-breaking idea, suggested using sampling to choose witnesses. We don’t know where the witnesses are, but we know how approximately how many there are, and so we know the probability of selecting one at random.
Here is the Miller-Rabin test: select a potential witness at random, and try Miller’s test. If the answer is “no”, then it’s a composite, end of story. If the answer is “I don’t know”, however, then the probability that the number is prime is approximately 0.75. Repeat; if the second potential witness doesn’t work out, then the probability that the number is prime is approximately 0.9375. After three iterations, 0.984. After ten, 0.999999. After twenty, 0.999999999999.
After a few hundred iterations, if you haven’t found a witness then you can be reasonably certain that the number is prime, or that you are the unluckiest person to ever walk the earth. If you’re not sure which, just tack on a few hundred more iterations. Miller’s test is quick and easy to compute, even for ridiculously large numbers.
So, if you want to have your own crypto keys that nobody but you can ever crack, here’s what you do: pick a random number, and test to see whether it’s prime. If so, keep it; otherwise ditch it and begin again. Repeat until you have all the primes you need. There are plenty of primes out there, so you’ll find a couple eventually.
Now you either have a practically unbreakable crypto scheme, or else you’re the unluckiest person imaginable.
Rabin’s insight was that there are certain problems that we can’t solve with complete certainty, but only with very high probability. We can make that probability as close to 1.0 as we like, but we will never get there.
This way of thinking has made possible practical solutions to problems that would otherwise be unthinkably intractable. Every once in a while–say perhaps once between now and when the last star in the sky winks out–they will give the wrong answer, but it’s worth that risk.
It’s no coincidence that Rabin was the professor who assigned this problem.
I will let you think about this for a moment or two.
