trial factoring for Mps

[bhelmes]

"The GIMPS factoring code creates a modified sieve of Eratosthenes with each bit representing a potential 2kp+1 factor. The sieve then eliminates any potential factors that are divisible by prime numbers below 40,000 or so. Also, bits representing potential factors of 3 or 5 mod 8 are cleared. This process eliminates roughly 95% of potential factors. The remaining potential factors are tested using the powering algorithm above."

Only a short mathematical or algorithmic question:

Why not making a list of 2kp+1 factors, clearing potential factors of 3 or 5 mod 8 and making then a sieving by the primes found by the quadratic sieve concerning f(n)=2n²-1.

IMHO you need less primes to sieve and the result should be equal.

P.S. I refer to the quadratic sieve described under:
http://devalco.de/quadr_Sieb_2x%5E2-1.php

[kriesel]

I think that quote is from the old days before GPU TF came to dominate.
As I understand it, there's a speed optimization involved. It can be faster to attempt factoring a Mersenne number with a set of factor candidates that contains a small fraction of composite factor candidates, than to spend additional effort to weed out more of the remaining composites and then trial factor the Mersenne number with a slightly reduced number of factor candidates. That's #9 of Concepts in GIMPS trial factoring (TF).
Perhaps another candidate factor screening method would help throughput. I don't recall seeing whether it was considered during the applications' development. Any such method would need to be sufficiently faster at eliminating 75-81 bit (22-24 digit) candidate factors to justify the effort of modification.

[LaurV]

Originally Posted by kriesel

I think that quote is from the old days before GPU TF came to dominate.

Nope. Both CPU and GPU programs do it exactly the same. They only differ in how they split the candidates in classes, and how far they sieve (for example, mfaktc sieves with prime to ~87k by default, but you can change the limit in the ini file). But the algorithm is EXACTLY the same. Optimizations are at very low level, how the data is stored, what you do with it, do its parents know, etc. But the algorithm is the same, and the same as described in the math section from where it was reproduced.

Originally Posted by bhelmes

Why not making a list of 2kp+1 factors, clearing potential factors of 3 or 5 mod 8 and making then a sieving by the primes found by the quadratic sieve concerning f(n)=2n²-1.

First, because that would be stupid. You would get exactly the OPPOSITE result. You will eliminate from the matrix numbers from your series, which HAVE a chance to be factors. You must eliminate the others, which are divisible by 13, 17, 19, 23, etc., when 4620 classes are used, or 11, 13, 17, 19, 23, etc., if you use 420 classes (the smaller primes are taken care by splitting in classes itself). Think about it.

Second, that would be slower. How many arbitrary numbers from 3 to a million are divisible by 13, 17, etc? And how many are divisible by primes generated by the series? (which are larger). In your matrix in the memory, there are more numbers divisible by small primes, than are divisible by large primes. So, using small primes gets rid of bad candidates faster.

[kriesel]

Originally Posted by bhelmes

"The sieve then eliminates any potential factors that are divisible by prime numbers below 40,000 or so."

The shallow sieving, only 40,000 or so, indicates it's likely from prime95, from before GPUs. Or maybe during the transition period when factoring was done on GPUs but with candidate sieving on CPU. Default for sieving on GPUs in mfaktc or mfakto is 82486 and 81157 respectively.
# Default: GPUSievePrimes=82486
# Default: GPUSievePrimes=81157
Tuning sometimes raises mfaktc's GPUSievePrimes setting up to 100,000 or more.
I've never seen it lower as far as 50,000.

bits representing potential factors of 3 or 5 mod 8 are cleared.

Factors of Mersenne numbers must be of form 1 or 7 mod 8, so 3 or 5 mod 8 gotta go, or never be added by the wheel generator to begin with.

[bhelmes]

A peaceful night for you,

I try to describe a possible trial factor algorithm for mps:

0. Consider one mp.
1. Generate 10^9 primes and the n0 from the polynomial f(n)=2n²-1
2. Make a linear substitution for n0=2^[(p-1)/2]=2pk+1, you get a quadratic polynomial g(k)
3. h(k)= |g(k)- (2^p-1)| (The numbers should be smaller)
4. Recalculate from n0 for the 10⁹ primes the smallest k0, so that all primes t | h(k0) and sieve h(k0)
5. Check if q=h*(k0) (divised by the sieved primes) q =1 mod p
6. If q = 1 mod p then q is a factor of mp.

Is this mathematical possible and senseful ?
I am trying to program it, in order to check this.

It would be nice to get some feedback.

[bhelmes]

Originally Posted by bhelmes

1. Generate 10^9 primes and the n0 from the polynomial f(n)=2n²-1

This was wrong, I have implemented this idea, but the primes generating by the polynomial f(n)=2n²-1 do not "cover" completely the resulting quadratic polynomial. I think a sieve of Eratosthenes will be better.

Nevertheless I have as result of the linear substitution a quadratic polynomial and can sieve it.
Besides I can calculate (thanks to Nick) with the Tonelli-Shanks algorithm the roots for half of the primes.
What is more I think a simple mod with the exponent of the Mp for the sieved out primes will be sufficient, that is better than a powermod.

Is this mathematical correct or not ?