mersenneforum.org Prime number software.
 Register FAQ Search Today's Posts Mark Forums Read

2018-12-30, 06:49   #12
Zach010

Dec 2018

2×3 Posts

Quote:
 Originally Posted by paulunderwood 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

 2018-12-30, 07:45 #13 paulunderwood     Sep 2002 Database er0rr 2·1,931 Posts 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
2018-12-30, 08:15   #14
Zach010

Dec 2018

1102 Posts

Quote:
 Originally Posted by paulunderwood 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

2018-12-30, 08:32   #15
paulunderwood

Sep 2002
Database er0rr

2×1,931 Posts

Quote:
 Originally Posted by Zach010 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 2018-12-30, 14:40 #16 CRGreathouse Aug 2006 3×1,993 Posts Quote:  Originally Posted by Zach010 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 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. 2018-12-30, 16:42 #17 PhilF "6800 descendent" Feb 2005 Colorado 23×5×17 Posts Quote:  Originally Posted by paulunderwood 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?

2018-12-30, 17:33   #18
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

33·5·37 Posts

Quote:
 Originally Posted by PhilF 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".

2018-12-30, 19:36   #19
ATH
Einyen

Dec 2003
Denmark

52×127 Posts

Quote:
 Originally Posted by PhilF 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

 2018-12-30, 19:50 #20 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts
2018-12-30, 22:56   #21
PhilF

"6800 descendent"
Feb 2005

23·5·17 Posts

Quote:
 Originally Posted by ATH 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.

2019-01-11, 05:51   #22
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by Zach010 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post skan Programming 14 2013-03-24 00:32 ishkibibble Conjectures 'R Us 15 2013-03-14 08:41 pacionet Programming 3 2008-02-12 12:36 Matt_G Hardware 13 2004-02-01 04:16 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