View Single Post
Old 2018-12-30, 06:38   #11
Zach010's Avatar
Dec 2018

2·3 Posts

Originally Posted by CRGreathouse View Post
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)

Last fiddled with by Zach010 on 2018-12-30 at 07:37
Zach010 is offline   Reply With Quote