Matt Springer is a graduate student of physics at Texas A&M university. He is also an occasional writer and tinkerer, and he is probably too curious for his own good.
when you order from Amazon, and a fraction of the purchase price will be sent to me at zero cost to you. Much obliged, and thanks for your patronage.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.
Physical Science
Comments
I have always found the properties of integers to be much more fascinating than real numbers. Another excellent Sunday Function, motherfucker!
Posted by: Comrade PhysioProf | May 31, 2009 5:19 PM
I don't know much about the math either, but it's easy to see that no such polynomial will continuously generate primes. If you have
c_n*x^n + c_{n-1}*x^{n-1} + ... + c_1*x + c_0
with the c_j all integers, then by plugging in x = c_0 you can factor c_0 out of all the the terms, so the answer is composite.
On the other hand, you could always create a polynomial that gives you n consecutive primes. Just start with foreknowledge of those primes, then create an n-1 degree polynomial through those points. It wouldn't be useful, though, since it doesn't give you any primes you don't already know about.
Posted by: meichenl | June 1, 2009 12:26 AM
If you look at formulas
n^2 + n + c
and ask how many consecutive primes they generate, the most possible is (c-1), from n=0 to n=(c-2), because when you plug in n=(c-1) the expression simplifies to c^2.
41 isn't the only integer to generate a streak this long. For example, if c=5, we get
5, 7, 11, 17, 25
so it generates 4 consecutive primes, saturating the upper bound. Other values of c that do this are 1, 3, 11, and 17. But there are no other numbers between 41 and one million that accomplish this. In fact, no c less than one million even generates another streak of 40 consecutive primes.
The formula
3n^2 + 3n + 256
generates 45 consecutive primes, but I can't find any quadratic with relatively small coefficient that does significantly better than that.
Posted by: meichenl | June 1, 2009 1:39 AM
Oops, that last part about 3n^2+3n+256 is obviously incorrect. There was a bug in my code, and now I can't anything that does better than n^2+n+41
Posted by: meichenl | June 1, 2009 2:35 AM
The Ulam spiral and the Sacks spiral make for a pretty illustration of this. If the integers >= 41 are written down consecutively in a spiral pattern, and colored according to their primality, then a pattern emerges: the sequence n^2 + n + 41 describes the numbers along the diagonal.
Posted by: isherm | June 1, 2009 4:20 AM
You can find other polynomials which generate primes at Wolfram MathWorld.
Posted by: kiwi | June 1, 2009 10:10 AM