Sieving

[ValerieVonck]

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

[garo]

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.

[ValerieVonck]

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.

[ET_]

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

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.

[ET_]

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

[wblipp]

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.

[ewmayer]

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.

[ET_]

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

[ValerieVonck]

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!