mersenneforum.org > Math Sieving
 Register FAQ Search Today's Posts Mark Forums Read

 2005-08-04, 17:02 #1 ValerieVonck     Mar 2004 Belgium 15148 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^n-1 (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
 2005-08-04, 18:56 #2 garo     Aug 2002 Termonfeckin, IE 22×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.
2005-08-04, 21:44   #3
ValerieVonck

Mar 2004
Belgium

22·211 Posts

But what do you mean with:

Quote:
 Mersenne numbers. 2^p - 1 will only have factors of the form 2*k*p+1.

2005-08-05, 11:19   #4
ET_
Banned

"Luigi"
Aug 2002
Team Italia

113428 Posts

Quote:
 Originally Posted by CedricVonck Ok just asking. But what do you mean with: Mersenne numbers. 2^p - 1 will only have factors of the form 2*k*p+1.
It means that a factor of a Mersenne number will always be of the form 2kp+1.

Luigi

2005-08-05, 13:10   #5
Unregistered

2·3·1,163 Posts

Quote:
 Originally Posted by ET_ It means that a factor of a Mersenne number will always be of the form 2kp+1. Luigi

WHERE p is the exponent you are currently attempting to test 2^p-1 for primality,

AND

where k is a positive integer up to such that 2kp+1 <= sqrt (2^p-1)

AND

such that (2kp+1) is itself prime too.

2005-08-05, 13:13   #6
ET_
Banned

"Luigi"
Aug 2002
Team Italia

483410 Posts

Quote:
 Originally Posted by Unregistered For clarity I will add.... WHERE p is the exponent you are currently attempting to test 2^p-1 for primality, AND where k is a positive integer up to such that 2kp+1 <= sqrt (2^p-1) AND such that (2kp+1) is itself prime too.
Correct!

Luigi

2005-08-05, 14:04   #7
wblipp

"William"
May 2003
New Haven

23·103 Posts

Quote:
 Originally Posted by Unregistered such that (2kp+1) is itself prime too.
This isn't required for the mathematical statement. Multiplying two numbers of this form together gives another number of this form, so ALL factors, both prime and composite, are of this form.

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.

2005-08-05, 18:29   #8
ewmayer
2ω=0

Sep 2002
República de California

266328 Posts

Quote:
 Originally Posted by wblipp 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.
...But directly testing each candidate q (shorthand for a number of form 2kp+1) for compositeness requires more work than doing the 2^p modular powering, so we use a sieve-within-a-sieve to a priori eliminate all q's which have factors smaller than some reasonable lower bound (between 50000 and 1000000 seems to work well for 64-bit factor candidates.) Thus a fair fraction of composite q's slips through the net, but the end effect is still faster than rigorously checking each q for primality prior to trial-dividing.

2005-08-05, 18:55   #9
ET_
Banned

"Luigi"
Aug 2002
Team Italia

10010111000102 Posts

Quote:
 Originally Posted by ewmayer ...But directly testing each candidate q (shorthand for a number of form 2kp+1) for compositeness requires more work than doing the 2^p modular powering, so we use a sieve-within-a-sieve to a priori eliminate all q's which have factors smaller than some reasonable lower bound (between 50000 and 1000000 seems to work well for 64-bit factor candidates.) Thus a fair fraction of composite q's slips through the net, but the end effect is still faster than rigorously checking each q for primality prior to trial-dividing.
Do composite factors of the form 2kp+1 pass the mod120 operation? :surprised

Luigi

2005-08-05, 22:31   #10
ValerieVonck

Mar 2004
Belgium

22×211 Posts

Quote:
 Originally Posted by ewmayer ...But directly testing each candidate q (shorthand for a number of form 2kp+1) for compositeness requires more work than doing the 2^p modular powering, so we use a sieve-within-a-sieve to a priori eliminate all q's which have factors smaller than some reasonable lower bound (between 50000 and 1000000 seems to work well for 64-bit factor candidates.) Thus a fair fraction of composite q's slips through the net, but the end effect is still faster than rigorously checking each q for primality prior to trial-dividing.
Ok thx for the nfo!

 Similar Threads Thread Thread Starter Forum Replies Last Post Dubslow Factoring 8 2012-09-28 06:47 JHansen NFSNET Discussion 9 2010-06-09 19:25 juno1369 Factoring 20 2010-04-28 01:11 OmbooHankvald Prime Sierpinski Project 4 2005-06-30 07:51 robert44444uk Sierpinski/Riesel Base 5 8 2005-04-02 22:30

All times are UTC. The time now is 19:20.

Thu Dec 2 19:20:30 UTC 2021 up 132 days, 13:49, 1 user, load averages: 1.88, 1.75, 1.54