Prime number software.

[Zach010]

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!

[paulunderwood]

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

or this one:

1296000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000639269244000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000105109353478476000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005760731904621792049

which has a factor:

6000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000986527

[Zach010]

Originally Posted by paulunderwood

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

or this one:

1296000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000639269244000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000105109353478476000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005760731904621792049

which has a factor:

6000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000986527

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

[paulunderwood]

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.

[CRGreathouse]

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.

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.

[PhilF]

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?

[VBCurtis]

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".

[ATH]

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.

[science_man_88]

https://rob-bell.net/2009/06/a-begin...ig-o-notation/

[PhilF]

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.

[CRGreathouse]

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.