mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-01-25, 21:55   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

11·23 Posts
Default 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
bhelmes is offline   Reply With Quote
Old 2017-01-25, 22:19   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

"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.
science_man_88 is offline   Reply With Quote
Old 2017-01-26, 21:21   #3
bhelmes
 
bhelmes's Avatar
 
Mar 2016

11×23 Posts
Default

I think you did not get the idea of the algorithm

Quote:
Originally Posted by science_man_88 View Post
"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
bhelmes is offline   Reply With Quote
Old 2017-01-26, 22:11   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-02-01, 22:11   #5
bhelmes
 
bhelmes's Avatar
 
Mar 2016

FD16 Posts
Default

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
bhelmes is offline   Reply With Quote
Old 2017-02-01, 22:22   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

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

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.
science_man_88 is offline   Reply With Quote
Old 2017-02-02, 14:56   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·5·293 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-02-02, 18:07   #8
bhelmes
 
bhelmes's Avatar
 
Mar 2016

11·23 Posts
Default

A peaceful evening for you,

Quote:
Originally Posted by CRGreathouse View Post
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
bhelmes is offline   Reply With Quote
Old 2017-02-02, 18:24   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

234416 Posts
Default

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 View Post
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 View Post
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?
Batalov is offline   Reply With Quote
Old 2017-02-02, 23:47   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

586010 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-02-03, 09:28   #11
bhelmes
 
bhelmes's Avatar
 
Mar 2016

FD16 Posts
Default

A peaceful day for you,

Quote:
Originally Posted by CRGreathouse View Post
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
bhelmes is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Small inconsistencies between mersenne.org and mersenne.ca factor databases GP2 Data 44 2016-06-19 19:29
mersenne.ca (ex mersenne-aries.sili.net) LaurV Information & Answers 8 2013-11-25 21:01
Gaussian-Mersenne & Eisenstein-Mersenne primes siegert81 Math 2 2011-09-19 17:36
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.