Nobody ever asks the interesting questions at presidential press conferences. But if somehow I could choose a question, it would be this:
“Mr. President, has the NSA solved the integer factorization problem?”
Of course it’s unlikely he’d know off the top of his head, and even if he did he certainly wouldn’t give me an answer. That’s the kind of codebreaking knowledge that quickly becomes useless if everyone knows you know. Large chunks of modern cryptography are based on the fact that it’s easy to multiply numbers like 17863 * 8161 = 145779943. But given a number like 223233911, it’s a lot harder to say which numbers you multiply together to get that number. A computer can easily do it for “small” numbers like the one I just gave, but for the 1000+ digit numbers used in cryptography it’s beyond the reach of even the best known techniques implemented on the best computers… unless someone like the NSA has found a more efficient way to do the calculations.
Personally if I had to guess I’d say they haven’t. There’s fairly good mathematical evidence that integer factorization just can’t be done “quickly”, in a particular mathematical sense of the word. But I wouldn’t be dogmatic about it; stranger things have happened. The primes are pretty mysterious in a lot of ways. Despite the vast ocean of knowledge mathematicians have developed about them, the depths of that ocean in many ways remain unexplored. Even the shallows contain strange and amazing things. For instance, take this ordinary-looking second order polynomial:
Start by putting some whole numbers into it, in sequence. First n = 0, then n = 1, then n = 2, and so on. You’ll get back the various values of the function for each n. Here they are, for all n between 0 and 10, inclusive:
41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151
You can take my word or check for yourself, but all of those are prime. You can keep going too. That polynomial won’t generate a non-prime number until n = 40, where f(40) = 1681, which is itself 41*41.
Normally in a Sunday Function I’d now tell you why this particular very simple polynomial should do such a strange thing. But I’m afraid this is pretty far beyond my area of mathematical expertise, and I don’t have a clean answer. The place to look for more detail is the theory of quadratic forms, my knowledge of which is somewhat sparse.
That doesn’t stop me from admiring the mathematical beauty of it.