View Single Post
Old 2007-05-12, 00:15   #1
Citrix
 
Citrix's Avatar
 
Jun 2003

112×13 Posts
Default Idea for faster sieve

I would like to propose a new idea for the sieve programs.

Instead of looking at all primes (p%2==1) if we looked at primes that were p%4==1 only. Then we would test only 1/2 the primes and would only find 1/2 the factors in a given range. But, we would be able to test the range faster as primes with smooth p-1's can be tested faster due to SPH algorithm. So the extra 2 will make things faster.

Also we don't need to test all factors of p-1, only the factors such that the product of these factors is less than 50M (worst case scenario). This should already have been implemented...

Some of the problems people have raised with this method:
1) Some of the factors are missed, as only a fraction will be tested.
2) We will reach 2^62 very soon and very few factors will be found.
3) Difficult to keep track of which primes have already been tested.
4) Difficult to generate the smooth p-1 primes.

Advantages:
We can find more factors everyday and thus eliminate more candidates, saving PRP tests and increasing chances of finding primes. The projects may finish faster.

Method:
Overcomes the 4 problems stated above.
1) Assuming we are going to 50M, so we generate a array x of smooth numbers for which we want all our p-1 (of primes used) to be multiples of.

2) During the sieve of Eratosthenes step, first you sieve using array x and set value =1 of all values that have p-1 as smooth. Then you sieve further and see if any values are prime. (As normally most programs do).

3)Sieve the .dat file using these selected primes.


This method solves problem 4. Problem 2, is not relevant as there are more than enough primes of this type under 2^62. I verified this using a simple program I wrote.

Problem 3: This can be solved by doing the inverse of step 2. During the sieve of Eratosthenes step, first you sieve using array x and set value =0 of all values that have p-1 as smooth. Then you sieve further and see if any of the other values are prime. (As normally most programs do).

Problem 1: Once this method has been used for finding the faster factors till 2^62, we can switch back to look for other factors.

I would really request some one (people who have access to source of proth_sieve or jjsieve) to implement this, it should not take much time. It will save alot of tests and help find primes faster.

Any other thoughts/ problems/ suggestions...

Thank you.

Citrix is online now   Reply With Quote