Lehmer sieve (opens in new tab)

Very cool. I thought to myself, before clicking on the article, "this is Hacker News, so its probably some interesting number theoretic sieve... but then again there are a lot of people who like to cook so maybe its some kind of novel mechanical sieve". So it was quite satisfying to see discover that it was BOTH in some sense.

"Lehmer sieves were very fast, in one particular case factoring 2^93 + 1 in 3 seconds."

Impressive. I wondered how fast my computer could do it. Here's the GNU coreutils factor:

    $ time factor 9903520314283042199192993793
    9903520314283042199192993793: 3 3 529510939 715827883 2903110321

    real    0m0.007s
    user    0m0.004s
    sys     0m0.000s

Still impressive. This led me down factor's documentation to the Pollard Rho algorithm: http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

So D-wave is basically a Lehmer sieve?