20170125, 21:55  #1 
Mar 2016
11·23 Posts 
Mersenne presieve by f(n)=2n^21
A peaceful night for you,
I plan to calculate the polynomial f(n)=2^n1 up to n=2^41 and make a factorisation, which will need a month calculation time. I want to use the sieved out primes to scan a certain list of mersenne number, maybe p=73 000 000 up to p=74 000 000 for Mp. Is there a list availible which i could use ? I thougt the best thing for finding mersenne factors is to calculate the sieved out primes f mod p (f=2*k*p+1) and then i could calculate the corresponding n(mp) mod f. What is nice, that i do not have to calculate Mp mod f, but n(Mp) mod f, which will speed up the factorisation time. For people who want to know the mathematical background i recommand my page http://devalco.de/quadr_Sieb_2x%5E21.php To get an idea which size of factors the algorithm delivers : http://devalco.de/quadr_Sieb_x%5E2+1.php#4d mathematical improvements or ideas are welcome Greetings from the primes Bernhard 
20170125, 22:19  #2 
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
"Also that means that all factors of Mersenne numbers can be found on this polynomial."
2(n^2)1 =23 doesn't work for integer n value... this suggest 2(n^2)=24 or that n^2=12 which doesn't have an integer ( or even rational) sqrt. 
20170126, 21:21  #3  
Mar 2016
11×23 Posts 
I think you did not get the idea of the algorithm
Quote:
A prime occurs periodically in the quadratic function. If p  f(n) then also p  f(n+p) If a mersenne number has factors, resp p  f(n) then p  f(np) also. Therefore, if a mersenne number is not prime then all factors will appear before in the sequence as factors of f(n)=2n^21 Greetings from the primes Bernhard 

20170126, 22:11  #4  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
Last fiddled with by science_man_88 on 20170126 at 22:12 

20170201, 22:11  #5 
Mar 2016
FD_{16} Posts 
A peaceful evening for all,
there was a bad typo in the last post. I use the polynomial f(n)=2n^21 for searching for factors of mersenne numbers, and not the polynomial 2^n1 of course. I have started the program five days ago up to n=2^41 and picked 70 mersenne numbers up from exponent = 73 000 000 which were investigated up to 2^75 with no factors found. There is still some programming work possible which could fasten up the calculation. There was not so much feedback for this topic, why not speed up Gimps with an alternativ presieve. I think i could manage to sieve up 100 mersenne numbers parallel up to n=2^42 with 4 weeks runtime, maybe more candidates and perhaps even further if i could parallise the sieving procedure. I am courios if i will find some factors ... Greetings from the primes Bernhard 
20170201, 22:22  #6  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
http://mersenneforum.org/showthread.php?t=17126 and possibly more like knowing you only have to check the first r, k values or so some prime r or do some modular math and you can eliminate a lot of k values form being checked etc. 

20170202, 14:56  #7 
Aug 2006
2^{2}·5·293 Posts 

20170202, 18:07  #8 
Mar 2016
11·23 Posts 
A peaceful evening for you,
Perhaps i am not very skilled to describe the topic of a presieve for mersenne numbers. Nevertheless the topic was discussed twice times and the main argument was that presieving with graphiccards are more efficient. There is only a question of speed. Therefore i tried to speed up my sieving routine. I changed the datastructure and can give a first runtime test: I check the first 70 mersenne numbers from the exponent 73 000 000 and do a factorisation for all primes. I need appr. for up to n=2^41 that means 1,6*10^12 primes a month calculation time on a Amd Fx (tm) X6 6300 with 32gbyte Ram and 5 Terabyte Harddisk with one thread. I think this is not a bad result. What do you think about it ? Greetings from the primes Bernhard 
20170202, 18:24  #9  
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3
2344_{16} Posts 
Bernhard,
What you are trying to say is not clear to anyone, and you don't make it any clearer. Quote:
What does this mean? You try to factor all primes??  That's useless. You try to divide by every prime?  This is known to be completely wasteful, because Mersenne numbers cannot have "all primes" as factors. They have very few possible divisors  that is exactly what makes them better to mine than many other classes of numbers. What is the relevance of this technical mumbojumbo? 

20170202, 23:47  #10  
Aug 2006
5860_{10} Posts 
Quote:


20170203, 09:28  #11  
Mar 2016
FD_{16} Posts 
A peaceful day for you,
Quote:
I use the polynomial f(n)=2*n^21, for n=0, 1, 2, 3 up to n=2^41 i calculate the f(n) and make a sieving procedure. As result i get all primes with p  f(n) I use these primes to make a trial factorisation test of mersenne primes. For example:f(9)=161=23*7 after the sieving procedure i get the prime 23, I check M(11) with f(2^5)=2*2^101=2^11  1, n=2^5=32 mod 23 = 9 This means that f(9)=23 and 2^5 mod 23 = 9 is in the same residue class (9), therefore 23  M(11) Please note that this method is faster than the calculation of M(11) mod 23 My calcualation will find appr. 1,6*10^12 primes, which is use for a trial factorisation of 70 mersenne numbers in parallel. I choose from http://www.mersenne.org/report_expon...xp_hi=73000100 the first 70 mersenne numbers with No factors below 2°75 @Batalov the describtion "mumbojumbo" is nice i add some technical describtion in order to give a correct benchmark Comparing this test to the trial factorisation with a graphic card: A modern graphic card needs 14 days for searching a factor of Mp up to 2^75 i guess, I need a month calculation time with one core with using 1,6*10^12 where the primes reached up to 2^83 binary digit, i use all primes below 2^41 for trial factoring and could use the sieved out primes for several mersenne numbers. I think this is a good first result. I hope i could clarify some question, thanks for yours replies and patient. Greetings from the primes Bernhard 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Small inconsistencies between mersenne.org and mersenne.ca factor databases  GP2  Data  44  20160619 19:29 
mersenne.ca (ex mersennearies.sili.net)  LaurV  Information & Answers  8  20131125 21:01 
GaussianMersenne & EisensteinMersenne primes  siegert81  Math  2  20110919 17:36 
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods  optim  PrimeNet  13  20040709 13:51 