20050804, 17:02  #1 
Mar 2004
Belgium
1514_{8} Posts 
Sieving
Is the Gimps project sieving?
At home, I am doing a little experiment with the newPgen program. My input parameters are: base: 2 k: 1 nmin: 25 M nmax 25.5 M Type: k*b^n1 (with k fixed) Of the 500.000 candidates I have (for the monemt): 37.000 candidates Couldn't this be a way to speed up the search? Regards, Cedric Vonck 
20050804, 18:56  #2 
Aug 2002
Termonfeckin, IE
2^{2}×691 Posts 
GIMPS does not sieve, it trial factors. The reason for this is the special form of all factors of Mersenne numbers. 2^p  1 will only have factors of the form 2*k*p+1. Hence it makes very little sense to check a potential factor against more than one candidate which is the essence of sieving.

20050804, 21:44  #3  
Mar 2004
Belgium
2^{2}·211 Posts 
Ok just asking.
But what do you mean with: Quote:


20050805, 11:19  #4  
Banned
"Luigi"
Aug 2002
Team Italia
11342_{8} Posts 
Quote:
Luigi 

20050805, 13:10  #5  
2·3·1,163 Posts 
Quote:
WHERE p is the exponent you are currently attempting to test 2^p1 for primality, AND where k is a positive integer up to such that 2kp+1 <= sqrt (2^p1) AND such that (2kp+1) is itself prime too. 

20050805, 13:13  #6  
Banned
"Luigi"
Aug 2002
Team Italia
4834_{10} Posts 
Quote:
Luigi 

20050805, 14:04  #7  
"William"
May 2003
New Haven
23·103 Posts 
Quote:
Of course if you are trial factoring, it's not necessary to try the composites because the only time a composite would divide the Mersenne number is when the composite is a product of primes that you should have tested earlier. 

20050805, 18:29  #8  
∂^{2}ω=0
Sep 2002
República de California
26632_{8} Posts 
Quote:


20050805, 18:55  #9  
Banned
"Luigi"
Aug 2002
Team Italia
1001011100010_{2} Posts 
Quote:
Luigi 

20050805, 22:31  #10  
Mar 2004
Belgium
2^{2}×211 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
NFS sieving?  Dubslow  Factoring  8  20120928 06:47 
Line sieving vs. lattice sieving  JHansen  NFSNET Discussion  9  20100609 19:25 
10^420 + 1 sieving  juno1369  Factoring  20  20100428 01:11 
Sieving  OmbooHankvald  Prime Sierpinski Project  4  20050630 07:51 
Sieving  robert44444uk  Sierpinski/Riesel Base 5  8  20050402 22:30 