mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-08-04, 17:02   #1
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

15148 Posts
Default 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
ValerieVonck is online now   Reply With Quote
Old 2005-08-04, 18:56   #2
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

22×691 Posts
Default

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.
garo is offline   Reply With Quote
Old 2005-08-04, 21:44   #3
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

22·211 Posts
Default

Ok just asking.

But what do you mean with:

Quote:
Mersenne numbers. 2^p - 1 will only have factors of the form 2*k*p+1.
ValerieVonck is online now   Reply With Quote
Old 2005-08-05, 11:19   #4
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

113428 Posts
Default

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
ET_ is offline   Reply With Quote
Old 2005-08-05, 13:10   #5
Unregistered
 

2·3·1,163 Posts
Default

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

Luigi
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.
  Reply With Quote
Old 2005-08-05, 13:13   #6
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

483410 Posts
Default

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
ET_ is offline   Reply With Quote
Old 2005-08-05, 14:04   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·103 Posts
Default

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.
wblipp is offline   Reply With Quote
Old 2005-08-05, 18:29   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

266328 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2005-08-05, 18:55   #9
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

10010111000102 Posts
Default

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
ET_ is offline   Reply With Quote
Old 2005-08-05, 22:31   #10
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

22×211 Posts
Default

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!
ValerieVonck is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
NFS sieving? Dubslow Factoring 8 2012-09-28 06:47
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
10^420 + 1 sieving juno1369 Factoring 20 2010-04-28 01:11
Sieving OmbooHankvald Prime Sierpinski Project 4 2005-06-30 07:51
Sieving 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.