mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-05-29, 20:31   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32×41 Posts
Default trial factoring for Mps

"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


bhelmes is offline   Reply With Quote
Old 2021-05-29, 20:46   #2
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

3×52×79 Posts
Default

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.

Last fiddled with by kriesel on 2021-05-29 at 21:03
kriesel is offline   Reply With Quote
Old 2021-05-30, 10:21   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

231208 Posts
Default

Quote:
Originally Posted by kriesel View Post
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.

Quote:
Originally Posted by bhelmes View Post
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.

Last fiddled with by LaurV on 2021-05-30 at 10:29
LaurV is offline   Reply With Quote
Old 2021-05-30, 11:02   #4
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

3×52×79 Posts
Default

Quote:
Originally Posted by bhelmes View Post
"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.

Quote:
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.

Last fiddled with by kriesel on 2021-05-30 at 11:18
kriesel is offline   Reply With Quote
Old 2021-06-30, 00:14   #5
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32·41 Posts
Default

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.

Last fiddled with by bhelmes on 2021-06-30 at 00:14
bhelmes is offline   Reply With Quote
Old 2021-07-14, 23:29   #6
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32·41 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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 ?



Last fiddled with by bhelmes on 2021-07-14 at 23:30
bhelmes is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Trial Factoring on AMD/ATI GPU's? Stargate38 GPU Computing 9 2018-08-31 07:58
How much Trial Factoring to do? odin Software 4 2010-08-08 20:23
over trial factoring JFB Software 23 2004-08-22 05:37
Trial factoring Citrix Software 7 2004-02-26 03:24
About trial factoring gbvalor Math 4 2003-05-22 02:04

All times are UTC. The time now is 05:43.


Mon Dec 6 05:43:54 UTC 2021 up 136 days, 12 mins, 0 users, load averages: 1.27, 1.33, 1.45

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.