3 ms·
Lehmer sieve
- gajomi 13y agoVery 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.
- coherentpony 13y agoThis is indeed where the name comes from :)
- jerf 13y ago"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 http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
- darkbot 13y agoSo D-wave is basically a Lehmer sieve?