Certifying primality of PRP numbers

[mnd9]

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!

[hansl]

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:

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

[mnd9]

Originally Posted by hansl

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

[paulunderwood]

Originally Posted by mnd9

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

[MiauiKatze]

I wonder if there is a eecutable file for windows because it would be much easier than everything else (self-compiling, Execute a script etc...)

[bur]

From the Primo FAQ:

Does it exist a Primo version for an other operating system than Linux?
No, there is not and there will not be. (Why would I pay for an OS? Linux is free.)

For serious prime search you might as well setup a Linux machine, but for just playing around it would be nice to have a Windows build.