mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data

Reply
 
Thread Tools
Old 2019-08-26, 18:25   #1
mnd9
 
Jun 2019
Boston, MA

2×19 Posts
Default 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 gHz-days)? Is there a way to estimate an assignment length in gHz-days based on #digits of the number being tested? Is there somewhere these assignments get reserved and distributed, similar to primenet/GIMPS?

Thanks in advance!
mnd9 is offline   Reply With Quote
Old 2019-08-26, 18:48   #2
hansl
 
hansl's Avatar
 
Apr 2019

5×41 Posts
Default

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:
The certification process took 694 days for the phase 1 and 58 days for the phase 2 using a Dual Intel E2667 processor (16 cores at 3.2 GHz).
hansl is offline   Reply With Quote
Old 2019-08-26, 19:04   #3
mnd9
 
Jun 2019
Boston, MA

2×19 Posts
Default

Quote:
Originally Posted by hansl View Post
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:
Thanks for the response -- wow 2 years to prove a ~35k digit number prime means there's really no practical way to prove primality of large prime cofactors with >2M digits.

I guess it just goes to show how ridiculous fast LL is compared to other primality tests...
mnd9 is offline   Reply With Quote
Old 2019-08-26, 20:46   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

61038 Posts
Default

Quote:
Originally Posted by mnd9 View Post
Thanks for the response -- wow 2 years to prove a ~35k digit number prime means there's really no practical way to prove primality of large prime cofactors with >2M digits.

I guess it just goes to show how ridiculous fast LL is compared to other primality tests...
LL or PRP of Mersenne numbers is fast for several reasons apart from the simplicty of the test, It is quick to do a modular reductions and we can use FFT multiplication. There are other almost as quick methods to prove Proth and Riesel numbers.

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 2019-08-26 at 21:02
paulunderwood is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Pretty Fast Primality Test (for numbers = 3 mod 4) tapion64 Miscellaneous Math 40 2014-04-20 05:43
Proof of Primality Test for Fermat Numbers princeps Math 15 2012-04-02 21:49
primo primality certificates - (un)lucky numbers klajok Factoring 0 2011-07-21 08:23
PRIMALITY PROOF for Wagstaff numbers! AntonVrba Math 96 2009-02-25 10:37
Two Primality tests for Fermat numbers T.Rex Math 2 2004-09-11 07:26

All times are UTC. The time now is 22:24.

Sun Mar 29 22:24:37 UTC 2020 up 4 days, 19:57, 3 users, load averages: 1.91, 1.70, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.