Built on Facts

Sunday Function

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:

i-d4bb9fe09d6b78eb832985821d8a307f-1.png

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.

Comments

  1. #1 Comrade PhysioProf
    May 31, 2009

    I have always found the properties of integers to be much more fascinating than real numbers. Another excellent Sunday Function, motherfucker!

  2. #2 Uncle Al
    May 31, 2009

    Euler’s n^2 + n + 41 generates primes 47.5% of the time. Ulam’s 4n^2 + 4n + 59 gives 43.7%. Homewood’s 2n^2 + 4n + 31 gives 43.5% correct.

    http://www.recmath.org/contest/PGP/index.php
    http://www.relativitydomains.com/Mathematics/Primes.pdf
    http://mathdl.maa.org/images/upload_library/22/Polya/07468342.di020763.02p0067y.pdf

    p1(n) = 4x^2 – 146x + 1373
    p2(n) = 4x^2 – 144x + 1459
    p3(n) = 4x^2 – 142x + 1301
    p4(n) = 4x^2 – 140x + 1877

  3. #3 meichenl
    June 1, 2009

    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.

  4. #4 meichenl
    June 1, 2009

    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.

  5. #5 meichenl
    June 1, 2009

    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

  6. #6 isherm
    June 1, 2009

    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.

  7. #7 kiwi
    June 1, 2009

    You can find other polynomials which generate primes at Wolfram MathWorld.

The site is undergoing maintenance presently. Commenting has been disabled. Please check back later!