[Kryptofan]

Are there any crypto-hobbyists on this forum that use the Sieve of Atkinapproach for prime numbers in their noodlings? I'm just getting into crypto and am curious about how you all started designing schemes.

[snoopy11]

Hi,

There is pseudo- code available for this on wikipedia

this would be an obvious choice just translate the pseudo-code to c++ code or whatever
language you are comfortable in.


Snoopy.

[macosxnerd101]

Are you looking for help with implementation or are you looking to discuss prime sieving? If you are looking for discussion, I can move the thread to a more appropriate forum.

[Adak]

I used the Sieve of Atkin to speed up a prime number search for an SPOJ problem. In my tests, it was slower than the Sieve of Eratosthenes. I also tried the Sieve of Sundaram, and again, the Sieve of Eratosthenes was faster.

This was done on an i7 cpu, which might have made the difference between what my tests found, and what was reported by the author of the respective articles in Wikipedia. I read an article that one of the world record prime number computations had been done using a modified SOE.

As far as Cryptology, Wikipedia has a lot of info on it, but you really need to Google for the Cryptology forums. I haven't seen it in a long time, but there also used to be a usenet group (newsgroup) in Cryptology that was quite good.

[macosxnerd101]

With the Sieve of Eratosthenes, you can stop after you hit a prime that is greater than sqrt(n), which is a big optimization. A lot of naieve implementations (including some that I've implemented a ways back) test all the primes until the list has been exhausted. This optimization follows from the fact that n has no more than sqrt(n) primes.

Also, I'm going to move this to CS.

[Skydiver]

My results were similar to Adak while I was trying to solve Project Euler #10. I managed to get a more speed out of the Sieve of Atkin by dumping the naive approach described in Wikipedia and implementing the optimizations suggested by professor to his masters students. And even better, it was more compatible for parallel processing. The only problem though was that even though it was faster, I must have misinterpreted the optimizations because it was skipping some primes. :-(

[Nikitin]

macosxnerd101, on 07 March 2013 - 02:03 PM, said:

This optimization follows from the fact that n has no more than sqrt(n) primes.

That's not how/why it works. If n=3, there are more than sqrt(n) primes. What you're "hitting" are not primes, they are factors of composite numbers you're trying to remove. The reason you can stop at sqrt(n) is because any composite number <= n will have at least one factor <= sqrt(n). Since you only need to "hit" one of their factors you can stop at sqrt(n).

[macosxnerd101]

Bad wording on my part! That's what I meant. Sorry for the confusion.