20190826, 18:25  #1 
Jun 2019
Boston, MA
2×19 Posts 
Certifying primality of PRP numbers
Hi all,
This is probably a very basic question for you all, but I've searched around various subforums here and elsewhere and wanted further clarification. I noticed that according to mersenne.ca all prime Mersenne cofactors discovered beyond M78737 are only probable primes rather than certified prime. 1) I understand that to confirm these as primes, a true primality test must be run. What is the fastest available test for numbers of this format? I realize LL (and LLR) are not viable for these numbers, so what test is used? 2) What software is available for confirmatory primality testing? 3) What ballpark timeframe are these tests going to take (e.g. in gHzdays)? Is there a way to estimate an assignment length in gHzdays based on #digits of the number being tested? Is there somewhere these assignments get reserved and distributed, similar to primenet/GIMPS? Thanks in advance! 
20190826, 18:48  #2  
Apr 2019
5×41 Posts 
There is software called Primo for primality proving.
It uses ECPP To get an idea of how long it takes, or the upper limit of practically testable number, there is a list of the largest primes proven with the software here: https://www.ellipsa.eu/public/primo/top20.html For the top record of 34987 decimal digits: Quote:


20190826, 19:04  #3  
Jun 2019
Boston, MA
2×19 Posts 
Quote:
I guess it just goes to show how ridiculous fast LL is compared to other primality tests... 

20190826, 20:46  #4  
Sep 2002
Database er0rr
6103_{8} Posts 
Quote:
Prime/ECPP uses elliptic curve arithmetic and is O(log(n)^(4+eps)) which means a test of half the digit length will take 1/16 of the time. So, on similar hardware, a 17.5k digit number will take about 1,5 months. See: https://primes.utm.edu/prove/index.html Last fiddled with by paulunderwood on 20190826 at 21:02 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pretty Fast Primality Test (for numbers = 3 mod 4)  tapion64  Miscellaneous Math  40  20140420 05:43 
Proof of Primality Test for Fermat Numbers  princeps  Math  15  20120402 21:49 
primo primality certificates  (un)lucky numbers  klajok  Factoring  0  20110721 08:23 
PRIMALITY PROOF for Wagstaff numbers!  AntonVrba  Math  96  20090225 10:37 
Two Primality tests for Fermat numbers  T.Rex  Math  2  20040911 07:26 