mersenneforum.org Mersenne presieve by f(n)=2n^2-1
 Register FAQ Search Today's Posts Mark Forums Read

 2017-01-25, 21:55 #1 bhelmes     Mar 2016 11·23 Posts Mersenne presieve by f(n)=2n^2-1 A peaceful night for you, I plan to calculate the polynomial f(n)=2^n-1 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%5E2-1.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
 2017-01-25, 22:19 #2 science_man_88     "Forget I exist" Jul 2009 Dumbassville 203008 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.
2017-01-26, 21:21   #3
bhelmes

Mar 2016

11×23 Posts

I think you did not get the idea of the algorithm

Quote:
 Originally Posted by science_man_88 "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.
23 | f(9)=161 und 23 | f(14)=391 with f(n)=2n^2-1

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(n-p) also.

Therefore, if a mersenne number is not prime then all factors will appear before in the sequence as factors of f(n)=2n^2-1

Greetings from the primes
Bernhard

2017-01-26, 22:11   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by bhelmes I think you did not get the idea of the algorithm 23 | f(9)=161 und 23 | f(14)=391 with f(n)=2n^2-1 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(n-p) also. Therefore, if a mersenne number is not prime then all factors will appear before in the sequence as factors of f(n)=2n^2-1 Greetings from the primes Bernhard
I would say as a divisors of the function or something similar on to me would mean as a value of the function. I commented in your other thread before, and I partially know what you mean. also 2^2-1=3 doesn't work so it's not technically all mersenne numbers ( in fact it only works with odd exponents ( so it's at best only accurate under an odd number exponent definition of mersenne numbers)).

Last fiddled with by science_man_88 on 2017-01-26 at 22:12

 2017-02-01, 22:11 #5 bhelmes     Mar 2016 FD16 Posts A peaceful evening for all, there was a bad typo in the last post. I use the polynomial f(n)=2n^2-1 for searching for factors of mersenne numbers, and not the polynomial 2^n-1 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
2017-02-01, 22:22   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by bhelmes A peaceful evening for all, there was a bad typo in the last post. I use the polynomial f(n)=2n^2-1 for searching for factors of mersenne numbers, and not the polynomial 2^n-1 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
there is plenty that makes GIMPS fast on this forum even like:

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.

2017-02-02, 14:56   #7
CRGreathouse

Aug 2006

22·5·293 Posts

Quote:
 Originally Posted by bhelmes There was not so much feedback for this topic, why not speed up Gimps with an alternativ presieve.
Yes, I don't think you were clear enough to be understood.

2017-02-02, 18:07   #8
bhelmes

Mar 2016

11·23 Posts

A peaceful evening for you,

Quote:
 Originally Posted by CRGreathouse Yes, I don't think you were clear enough to be understood.
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

2017-02-02, 18:24   #9
Batalov

"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

234416 Posts

Bernhard,
What you are trying to say is not clear to anyone, and you don't make it any clearer.
Quote:
 Originally Posted by bhelmes I check the first 70 mersenne numbers from the exponent 73 000 000 and do a factorisation for all primes.
"do a factorisation for all primes."
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.

Quote:
 Originally Posted by bhelmes 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.
What is the relevance of this technical mumbo-jumbo?

2017-02-02, 23:47   #10
CRGreathouse

Aug 2006

586010 Posts

Quote:
 Originally Posted by bhelmes 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.
So you did a calculation which took one CPU-core-month on a particular machine. But I'm not clear on what the calculation was. Would you explain? I'm not asking how it was performed, just what it showed. I don't know what "the first 70 mersenne numbers from the exponent 73 000 000" means nor what " do a factorisation for all primes" means, and I think "up to n=2^41" is meant to modify the last somehow.

2017-02-03, 09:28   #11
bhelmes

Mar 2016

FD16 Posts

A peaceful day for you,

Quote:
 Originally Posted by CRGreathouse So you did a calculation which took one CPU-core-month on a particular machine. But I'm not clear on what the calculation was. Would you explain? I'm not asking how it was performed, just what it showed. I don't know what "the first 70 mersenne numbers from the exponent 73 000 000" means nor what " do a factorisation for all primes" means, and I think "up to n=2^41" is meant to modify the last somehow.
I will try to clarify the calculation which i am doing:
I use the polynomial f(n)=2*n^2-1, 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^10-1=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 "mumbo-jumbo" 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

 Similar Threads Thread Thread Starter Forum Replies Last Post GP2 Data 44 2016-06-19 19:29 LaurV Information & Answers 8 2013-11-25 21:01 siegert81 Math 2 2011-09-19 17:36 optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 04:30.

Wed Jun 3 04:30:15 UTC 2020 up 70 days, 2:03, 2 users, load averages: 2.46, 2.92, 3.23