mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2018-12-30, 06:49   #12
Zach010
 
Zach010's Avatar
 
Dec 2018

2×3 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Or the 2-year 16-core proof of 2^116224-15905? Note the 1 core test Fermat+Lucas test that took 37.00 seconds.
Yeah but they had to run that 16 core proof because the Fermat+Lucas tests aren't 100% accurate. Like I asked: Fast and accurate for any prime? Only if you are a mathematical god.
2^116224-15904 took 0.0 seconds to return false because its 1 less than 2^116224-15905 and it found a divisor quickly. If I do 2^116224-15907 which is -2 (so it stays odd like all primes) it still takes less than a second.
2^116224-15905 would take a looooong time to fully calculate. It hasn't returned false after 10 minutes so far...That gives it a higher prime probability!

Last fiddled with by Zach010 on 2018-12-30 at 07:06
Zach010 is offline   Reply With Quote
Old 2018-12-30, 07:45   #13
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,931 Posts
Default

Try this number: (2^16603+1)/3. Hint: it has a factor 15585137074585080458129252635718353

or this one:

Code:
1296000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000639269244000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000105109353478476000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005760731904621792049
which has a factor:

Code:
6000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000986527

Last fiddled with by paulunderwood on 2018-12-30 at 08:02
paulunderwood is offline   Reply With Quote
Old 2018-12-30, 08:15   #14
Zach010
 
Zach010's Avatar
 
Dec 2018

1102 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Try this number: (2^16603+1)/3. Hint: it has a factor 15585137074585080458129252635718353

or this one:

Code:
1296000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000639269244000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000105109353478476000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005760731904621792049
which has a factor:

Code:
6000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000986527
You got me there. That'll be slow. This is where moving on to factoring and Lucas methods like Prime 95 win.

Last fiddled with by Zach010 on 2018-12-30 at 08:24
Zach010 is offline   Reply With Quote
Old 2018-12-30, 08:32   #15
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,931 Posts
Default

Quote:
Originally Posted by Zach010 View Post
You got me there. That'll be slow. This is where moving on to factoring and Lucas methods like Prime 95 win.
Quite. GIMPS employs, amongst other methods, TF (trial factoring), P-1 (Pollard's P-1 method), PRP (Fermat) and LL (Lucas-Lehmer).

The second number I gave is a Carmichael number which passes any Fermat PRP but not certain Lucas tests (although visa versa is possible too with some other numbers), but no one has yet claimed the $620 for a composite number that passes both a (strong) base 2 Fermat PRP test and a (specific) Lucas PRP test i.e. the BPSW test.

Last fiddled with by paulunderwood on 2018-12-30 at 08:42
paulunderwood is offline   Reply With Quote
Old 2018-12-30, 14:40   #16
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by Zach010 View Post
2^116224-15905 would take a looooong time to fully calculate. It hasn't returned false after 10 minutes so far...That gives it a higher prime probability!
Here's the problem, though. About 1 out of every 123 numbers has no prime factors less than 10^30, of which only a vanishingly small fraction of these are prime. But even if you had 10 billion machines like the i9 you described working in parallel, it would take something like 40,000 years to check up to this limit. So higher prime probability, perhaps, but not very much, since you'll always have big errors even with huge resources.

Quote:
Originally Posted by Zach010 View Post
The script also accepts pythonic syntax such as 2^61-1 as 2**61-1 for a Mersenne Prime around 2.3 quintillion. On my 8 core 16 thread i9 it does this in around 20 seconds at 4.7 ghz.
CRGreathouse is offline   Reply With Quote
Old 2018-12-30, 16:42   #17
PhilF
 
PhilF's Avatar
 
"6800 descendent"
Feb 2005
Colorado

23×5×17 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Quite. GIMPS employs, amongst other methods, TF (trial factoring), P-1 (Pollard's P-1 method), PRP (Fermat) and LL (Lucas-Lehmer).

The second number I gave is a Carmichael number which passes any Fermat PRP but not certain Lucas tests (although visa versa is possible too with some other numbers), but no one has yet claimed the $620 for a composite number that passes both a (strong) base 2 Fermat PRP test and a (specific) Lucas PRP test i.e. the BPSW test.
One program I see mentioned only rarely is primo. Isn't that a good one (and relatively fast) when wanting to prove the primality of very large non-Mersenne numbers?
PhilF is offline   Reply With Quote
Old 2018-12-30, 17:33   #18
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

33·5·37 Posts
Default

Quote:
Originally Posted by PhilF View Post
One program I see mentioned only rarely is primo. Isn't that a good one (and relatively fast) when wanting to prove the primality of very large non-Mersenne numbers?
Yes, but you wouldn't use Primo to search for candidates to prove! After one uses some flavor of prp test to find candidates, Primo is the only way for no-particular-form numbers of interesting size to go from "it's PRP so I believe it's prime" to "proven prime".
VBCurtis is online now   Reply With Quote
Old 2018-12-30, 19:36   #19
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

52×127 Posts
Default

Quote:
Originally Posted by PhilF View Post
One program I see mentioned only rarely is primo. Isn't that a good one (and relatively fast) when wanting to prove the primality of very large non-Mersenne numbers?
I think the problem is how you define "very large" numbers. In "every day" terms numbers up to 34,987 digits is insanely huge, the number of atoms in the visible universe is only an ~80 digit number.

But in this forum regarding GIMPS and even most of the side projects going on here, numbers up to 34,987 digits are not very big and are even considered "small", and remember that number took ~2 years on 16 cores to test. Considering more reasonable run times Primo can only test up to ~20K digits.
GIMPS new prime and the current wavefront is around 25 million digits! That is NOT ~714 times as large as 34,987 digits but 24965013 orders of magnitude larger!


Edit: @PhilF I know you know this, this post was meant for the OP.

Last fiddled with by ATH on 2018-12-30 at 19:38
ATH is offline   Reply With Quote
Old 2018-12-30, 19:50   #20
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

https://rob-bell.net/2009/06/a-begin...ig-o-notation/
science_man_88 is offline   Reply With Quote
Old 2018-12-30, 22:56   #21
PhilF
 
PhilF's Avatar
 
"6800 descendent"
Feb 2005
Colorado

23·5·17 Posts
Default

Quote:
Originally Posted by ATH View Post
I think the problem is how you define "very large" numbers. In "every day" terms numbers up to 34,987 digits is insanely huge, the number of atoms in the visible universe is only an ~80 digit number.

But in this forum regarding GIMPS and even most of the side projects going on here, numbers up to 34,987 digits are not very big and are even considered "small", and remember that number took ~2 years on 16 cores to test. Considering more reasonable run times Primo can only test up to ~20K digits.
GIMPS new prime and the current wavefront is around 25 million digits! That is NOT ~714 times as large as 34,987 digits but 24965013 orders of magnitude larger!


Edit: @PhilF I know you know this, this post was meant for the OP.
Thanks for the info. Primo supports up to nearly 40,000 digits now. I understand that isn't very large in terms of Mersenne numbers, but if I wanted to prove primality of a number in a non-special form that was larger than that, I would have no idea how to go about it.
PhilF is offline   Reply With Quote
Old 2019-01-11, 05:51   #22
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by Zach010 View Post
I don't know much about PARI/GP. I did a search and found that its a "computer algebra system". Have to learn more.
PARI/GP is a tool for doing calculations, especially in number theory. It can be used as a calculator or as a C/C++ library.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
software advise? big number with GUI skan Programming 14 2013-03-24 00:32
Prime testing software suggestions please. ishkibibble Conjectures 'R Us 15 2013-03-14 08:41
[SunOS 5.10] Software for prime search pacionet Programming 3 2008-02-12 12:36
Prime 95 and Software OC'ing Matt_G Hardware 13 2004-02-01 04:16
Network Administration software for Prime ? fuzzfuzz Software 6 2002-09-10 08:46

All times are UTC. The time now is 19:44.


Tue Oct 19 19:44:16 UTC 2021 up 88 days, 14:13, 0 users, load averages: 1.82, 1.80, 1.69

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.