Prime number software.
 

I don't really know how good this program is. I wrote it over the past few months and was wondering if anyone wanted to try it and let me know. I posted it on Git hub for anyone to see. It is written in Python and requires the scientific mpmath module to run. It uses the multiprocessing module and does calculations in parallel. Here is the link: [URL="https://github.com/zach010/PrimeOptimus"]Github[/URL] Tell me what you think. I can turn this code into a network cluster with multiprocessing server managers pretty easily. Also, what language is Prime95 written in? Tell me how I can help.

It seems to be just trial division/SoE.

[QUOTE=Zach010;504083]Also, what language is Prime95 written in? Tell me how I can help.[/QUOTE]

Prime95 is written in C and assembly, and I guess some C++ for the GUI.

[QUOTE=LaurV;504099]It seems to be just trial division/SoE.[/QUOTE]
It seems to "just" be trial division? Okay. I guess that means its crap.

[QUOTE=paulunderwood;504105]Prime95 is written in C and assembly, and I guess some C++ for the GUI.[/QUOTE]

A better guess for the GUI is Visual Basic. :groan:

Trial division is a slow general-purpose algorithm, while Lucas-Lehmer is a fast special-purpose algorithm. Your program took 70.2 seconds to verify the primality of 2^61-1, while my GP script (essentially the same as the one I uploaded to Rosetta Code) takes 36 microseconds to do the same. Prime95 uses a lot of specialized techniques and tricks that make it substantially faster than my simple-minded script.

[code]LL(p)=
{
my(m=Mod(4,2^p-1));
for(i=3,p, m=m^2-2);
m==0;
}[/code]

Of course for non-Mersenne numbers there still algorithms much faster than trial division. Below 2^64 BPSW works, above that a prp test and ECPP is good (and you can do less if you only need near-certainty, like 99.999999%).

[QUOTE=CRGreathouse;504328]Of course for non-Mersenne numbers there still algorithms much faster than trial division. Below 2^64 BPSW works, above that a prp test and ECPP is good (and you can do less if you only need near-certainty, like 99.999999%).[/QUOTE]Yes, I was about to say that. My script is for [B][U]any[/U][/B] prime. An algorithm that works 100.0% of the time and is fast? I have done many trials and tests with different methods and this modular trial division is the only method that always returns 100% correct. Sieves such as the Sieve of Eratosthenes are fast, but can take a while to initialize sieve data into memory. Sieves can also be ram expensive and only work up to a certain number before you reach your memory limit. Read the description of my code. If the program is taking too long, then terminate the process. If you enter a huge number that is 300 thousand digits long, if it is not prime, the program will be able to realize it in under a few seconds 99% of the time. If it runs....and keeps running, it has a much higher chance of prime-ness especially if you have a system with a high core-count because it takes evenly spaced samples of the whole number at once. This gives it a higher chance to find an odd divisor by sampling calculations of the number from multiple vantage points simultaneously. 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.

[QUOTE=Zach010;504329]An algorithm that works 100.0% of the time and is fast?[/QUOTE]

Yes. For example, the next prime after the Mersenne prime tested above is 2^61 + 15. PARI/GP proves its primality in 500 nanoseconds.

Moving to somewhat larger numbers, PARI/GP takes 150 ms to prove that 10^100 + 267 is prime. How long do you project that would take your program, assuming you networked all the computers in the world for the task?

[QUOTE=CRGreathouse;504331]Yes. For example, the next prime after the Mersenne prime tested above is 2^61 + 15. PARI/GP proves its primality in 500 nanoseconds.

Moving to somewhat larger numbers, PARI/GP takes 150 ms to prove that 10^100 + 267 is prime. How long do you project that would take your program, assuming you networked all the computers in the world for the task?[/QUOTE]

Or the 2-year 16-core [I]proof[/I] of [URL="https://primes.utm.edu/primes/page.php?id=123996"]2^116224-15905[/URL]? Note the 1 core test Fermat+Lucas test that took 37.00 seconds.

[QUOTE=CRGreathouse;504331]Yes. For example, the next prime after the Mersenne prime tested above is 2^61 + 15. PARI/GP proves its primality in 500 nanoseconds.

Moving to somewhat larger numbers, PARI/GP takes 150 ms to prove that 10^100 + 267 is prime. How long do you project that would take your program, assuming you networked all the computers in the world for the task?[/QUOTE]

Good question. Assuming I could get a core count, it would obviously be a linear increase in speed per 'x' number of cores and would have noticeable speed limits. I really wanted to try to code a cuda version with the same idea. I don't know much about PARI/GP. I did a search and found that its a "computer algebra system". Have to learn more.

Let me be clear. This script is not meant for calculations of huge numbers without a comparable system to handle the time. It is really meant for "fishing" for probable primes and it works well. On a quad core processor if one enters 10**100 - 266, it returns false immediately or 10**100 - 268 it returns false immediately. But 10**100 - 267 will continue because its prime and won't find a divisor to terminate the program. So it will continue to calculate to the end unless you terminate it. I could easily implement an add-on to the code where it has a time limit of a 1 minute calculation per number where it will store the probable prime in a list if it doesn't return true or false and map them to known primes to see how probable the probability is.

Prime95 is not 100% accurate:

To perform the Mersenne prime search, the program implements two algorithms:

Lucas–Lehmer (LL) test – proves any specific number is either a Mersenne prime, or a composite (in practice it has reliability of about 96%)
Probable prime (PRP) test – proves a number to be composite (but in practice has very low chance of reporting a false positive); this method is preferred for large numbers because of better error correction

It also implements a few algorithms which try to factor the numbers:

Trial factoring – this method is primarily used before applying the aforementioned algorithms
Pollard's factorization algorithm (P-1)
Elliptic-curve factorization method (ECM)

[QUOTE=paulunderwood;504332]Or the 2-year 16-core [I]proof[/I] of [URL="https://primes.utm.edu/primes/page.php?id=123996"]2^116224-15905[/URL]? Note the 1 core test Fermat+Lucas test that took 37.00 seconds.[/QUOTE]
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!

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

or this one:

[CODE]1296000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000639269244000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000105109353478476000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005760731904621792049[/CODE]

which has a factor:

[CODE]6000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000986527[/CODE]

[QUOTE=paulunderwood;504339]Try this number: (2^16603+1)/3. Hint: it has a factor 15585137074585080458129252635718353

or this one:

[CODE]1296000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000639269244000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000105109353478476000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005760731904621792049[/CODE]

which has a factor:

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

[QUOTE=Zach010;504343]You got me there. That'll be slow. This is where moving on to factoring and Lucas methods like Prime 95 win.[/QUOTE]

Quite. GIMPS employs, amongst other methods, TF (trial factoring), P-1 (Pollard's P-1 method), PRP (Fermat) and LL (Lucas-Lehmer). :smile:

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.

[QUOTE=Zach010;504334]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![/QUOTE]

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=Zach010;504329]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.[/QUOTE]

[QUOTE=paulunderwood;504345]Quite. GIMPS employs, amongst other methods, TF (trial factoring), P-1 (Pollard's P-1 method), PRP (Fermat) and LL (Lucas-Lehmer). :smile:

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.[/QUOTE]

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?

[QUOTE=PhilF;504382]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?[/QUOTE]

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

[QUOTE=PhilF;504382]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?[/QUOTE]

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.

[url]https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/[/url]

[QUOTE=ATH;504408]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.[/QUOTE]

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.

[QUOTE=Zach010;504333]I don't know much about PARI/GP. I did a search and found that its a "computer algebra system". Have to learn more.[/QUOTE]

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.