Prime number software.

[Zach010]

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: Github 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.

[LaurV]

It seems to be just trial division/SoE.

[paulunderwood]

Originally Posted by Zach010

Also, what language is Prime95 written in? Tell me how I can help.

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

[Zach010]

Originally Posted by LaurV

It seems to be just trial division/SoE.

It seems to "just" be trial division? Okay. I guess that means its crap.

[paulunderwood]

Originally Posted by paulunderwood

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

A better guess for the GUI is Visual Basic.

[CRGreathouse]

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.

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

[CRGreathouse]

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%).

[Zach010]

Originally Posted by CRGreathouse

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%).

Yes, I was about to say that. My script is for any 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.

[CRGreathouse]

Originally Posted by Zach010

An algorithm that works 100.0% of the time and is fast?

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?

[paulunderwood]

Originally Posted by CRGreathouse

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?

Or the 2-year 16-core proof of 2^116224-15905? Note the 1 core test Fermat+Lucas test that took 37.00 seconds.

[Zach010]

Originally Posted by CRGreathouse

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?

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)