View Single Post
Old 2006-07-25, 22:59   #21
Citrix
 
Citrix's Avatar
 
Jun 2003

30648 Posts
Default

I am not completely sure, but I think jjsieve already does this for me. k=25 seems faster to sieve than k=5. So I think you do not have to implement anything.

I think when you do discrete log, based on factors of p-1, the first factor 2, eliminates the primes if it does not have the right power of 2 in p-1.


edit:
I am working on k=3^16 for base 2^16 from 0 to 2 Million, I am getting about 2150kp/s on a 1.4 ghz p4. What would the speed be for your program, with the above implementation ie. only considering primes 32*a+1?

Last fiddled with by Citrix on 2006-07-25 at 23:29
Citrix is offline   Reply With Quote