- What is the prime factorization of ?
This is the most obvious question we could ask. The Fundamental Theorem tells us such a prime factorization must exist (and must be unique up to the order of the factors), so we can simply ask what it is. For example, if , then the answer would be . What we really want is some sort of machine (let’s call it a factorization machine) where we can put a positive integer in one end, the machine makes whirring, griding, and beeping sounds for a while, and then a factorization pops out the other end:
Another question we could ask about would be:
- What is one prime factor of ?
An answer to this question is a similar sort of machine, except instead of getting the entire prime factorization out, we just get one prime factor; let’s call this a factor machine. For example, it might work like this:
These first two machines are very closely related. If we have a factorization machine we can easily use it to build a factor machine: just run through the factorization machine, pick one of the factors to return, and throw the rest away.
Slightly less obviously, we can also use a factor machine to build a factorization machine: run through the factor machine to get a prime factor . Now we can compute (by definition, must evenly divide ); to get the rest of the factorization of we just need to factor . So we run through the factor machine to get a prime factor ; we compute ; and so on. We are done when putting into the factor machine returns itself; that means is prime. Finally, we return the factorization .
For example, if we run through the factor machine and get , then we compute . Next we run through the factor machine again and get, say, , and then compute the remaining part that needs to be factored, ; and so on.
Finally, here’s a third question we could ask:
- Is prime?
In answer to this we could imagine another similar machine which outputs a simple yes/no answer. Let’s call this a primality machine:
Given a factor machine, we can easily use it to build a primality machine: take the input and run it through the factor machine. If the answer is , then is prime so output “YES”; otherwise, is not prime (since it is divisible by the output factor), so output “NO”.
But what about the converse? If we have a working primality machine, can we use it to build a factor machine? Given some , if the primality machine says YES then is prime, so the factor machine should output . But what if the primality machine says NO? On the face of it, the mere fact of knowing that is composite does not help us find a factor. But what is the primality machine doing on the inside? If it knows that is not prime, it must have figured out a way to factor , right? That is, somewhere in the internals of the machine, there must have been a factor that it simply isn’t telling us about:
If this is true, it means we could rip open the guts of the primality machine and use it to build a factor machine. Or, put more simply, this would be saying that the only way to make a primality machine is to build it out of a factor machine. This seems intuitively reasonable: how could you know that is composite without factoring it?
The punchline is that this is not true!! That is,
It is possible to make working primality machines that truly do not know anything about any factors of .
Not only that, but we know how to make primality machines that run much faster than the fastest known factor machines!
Let that sink in for a minute. It is really quite surprising that we can find out whether has any prime divisors without actually finding out what they are, and that moreover it is much faster if you don’t care what the prime factors are. Think of it as a sort of “computational loophole” in our universe.
This is no mere curiosity; it turns out that this “loophole” is actually the basis of almost all of modern cryptography. When your browser makes an encrypted connection to a website in order to securely transmit your credit card information, it is relying on this loophole: your browser needs to pick some numbers and make sure that they are prime, which it can do quickly; but for anyone intercepting the messages to steal your credit card, they would have to factor another number, which (as far as we know) cannot be done quickly. (This is really cool and a topic for another post.)
It gets stranger, though: you may have noticed that I keep using phrases such as “fastest known”, “seems”, and “as far as we know”. It turns out that no one has been able to prove that making faster factor machines can’t be done! So it’s possible that the “loophole” isn’t a loophole at all; perhaps with a clever enough idea it will turn out to be possible to factor numbers just as fast as we can test whether they are prime. But most people don’t believe that.
In some upcoming posts I plan to talk a bit more about what we actually mean when we are talking about these machines being “fast” or “slow”, and then finally get around to explaining some different ways of building fast primality machines.
Possibly a product of no prime factors, which accounts for .↩