View Single Post
Old 2007-05-28, 02:32   #28
geoff's Avatar
Mar 2003
New Zealand

115710 Posts

I have uploaded version 1.5.5x which takes the switch `sr2sieve -x X' and only tests for factors of the form p-1 (mod X). X doesn't have to be a power of 2 but it is more efficient if it is.

I speculated in another thread about modifying the Sieve of Eratosthenes so that it only sieved numbers of the form N*x+1 for some constant N, but I haven't found a way to do this efficiently, except when N is a power of 2.

Citrix, even if this were done, you talk about finding the factors of (p-1)%N, which is another problem altogether. Sr2sieve doesn't need to do this, it only ever looks at the value gcd(p-1,N).

Here is the general technique I would use to find the factors of gcd(p-1,N).

0. Precompute T[0] ... T[N-1] where T[i] contains the factors of gcd(i,N).

1. For any p > 0, the factors of gcd(p-1,N) are T[(p-1)%N].

This only requires one division per p and so is a huge improvement over computing (p-1)%n for each divisor n of N. However it can't be used to find factors of (p-1)%N that are not themselves divisors of N.
geoff is offline   Reply With Quote