7 Replies - 7331 Views - Last Post: 07 March 2013 - 06:55 PM

#1 Kryptofan  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 2
  • Joined: 05-March 13

Playing with ciphers and the Sieve of Atkin

Posted 07 March 2013 - 07:46 AM

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.
Is This A Good Question/Topic? 1
  • +

Replies To: Playing with ciphers and the Sieve of Atkin

#2 snoopy11  Icon User is offline

  • Engineering ● Software
  • member icon

Reputation: 841
  • View blog
  • Posts: 2,472
  • Joined: 20-March 10

Re: Playing with ciphers and the Sieve of Atkin

Posted 07 March 2013 - 08:17 AM

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.
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10807
  • View blog
  • Posts: 40,286
  • Joined: 27-December 08

Re: Playing with ciphers and the Sieve of Atkin

Posted 07 March 2013 - 08:31 AM

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. :)
Was This Post Helpful? 0
  • +
  • -

#4 Adak  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 331
  • View blog
  • Posts: 1,168
  • Joined: 01-April 11

Re: Playing with ciphers and the Sieve of Atkin

Posted 07 March 2013 - 11:55 AM

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.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10807
  • View blog
  • Posts: 40,286
  • Joined: 27-December 08

Re: Playing with ciphers and the Sieve of Atkin

Posted 07 March 2013 - 01:03 PM

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.
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3662
  • View blog
  • Posts: 11,467
  • Joined: 05-May 12

Re: Playing with ciphers and the Sieve of Atkin

Posted 07 March 2013 - 06:37 PM

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. :-(
Was This Post Helpful? 0
  • +
  • -

#7 Nikitin  Icon User is offline

  • D.I.C Regular

Reputation: 56
  • View blog
  • Posts: 264
  • Joined: 02-August 10

Re: Playing with ciphers and the Sieve of Atkin

Posted 07 March 2013 - 06:53 PM

View Postmacosxnerd101, 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).
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10807
  • View blog
  • Posts: 40,286
  • Joined: 27-December 08

Re: Playing with ciphers and the Sieve of Atkin

Posted 07 March 2013 - 06:55 PM

Bad wording on my part! That's what I meant. Sorry for the confusion. :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1