20171125, 16:48  #1 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×1,153 Posts 
Largest Known PRP
I wondered what was the largest known PRP and was expecting to find references to one which was larger than the largest known Prime.
My search came short: https://math.stackexchange.com/quest...stknownprime * Can anyone here do better? * Is it true that PRP tests are generally as slow as LLR tests? ( I doubt it) Thank you very much in advance. 
20171125, 16:57  #2  
"Forget I exist"
Jul 2009
Dartmouth NS
8418_{10} Posts 
Quote:


20171125, 17:08  #3 
"Rashid Naimi"
Oct 2015
Remote to Here/There
4402_{8} Posts 
Thank you very much for the reply SM.
The largest known Prime has 22M+ dd. The largest PRP listed in your link seems to have only 4M+ dd. So it comes much short. 
20171125, 17:09  #4  
Sep 2003
13×199 Posts 
Quote:
For instance, their top twenty prime Mersenne cofactors stop at M63703, although the biggest known PRP Mersenne cofactor belongs to M7080247, whose exponent is more than a hundred times larger. 

20171125, 17:13  #5  
Sep 2003
101000011011_{2} Posts 
Quote:
I might have remembered the details wrong, but I do believe that PRP is slower. Once you divide by known factors, you lose the special form that makes LL testing particularly fast. 

20171125, 17:18  #6  
Sep 2002
Database er0rr
3×1,453 Posts 
Quote:


20171125, 17:45  #7 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×1,153 Posts 
If I understand it correctly any integer that passes any of the multitude of probabilistic primality tests and is not known to be a composite is a PRP.
This particular test for example does not seem that time consuming: https://en.m.wikipedia.org/wiki/Fermat_primality_test It is problematic for large numbers because it requires exponentiation to the powers of the candidates, but not time intensive. Corrections are welcome and appreciated. Thank you for all the replies. Last fiddled with by a1call on 20171125 at 17:47 
20171125, 17:53  #8 
Sep 2002
Database er0rr
1000100000111_{2} Posts 
Taking a modulo k*b^n+c is much faster than taking a general modulo.
Edit: I should add that taking modulo Eisenstein numbers is also fast. Last fiddled with by paulunderwood on 20171125 at 18:21 
20171125, 19:37  #9 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×1,153 Posts 
Similarly this test does not seem to involve any significant programmatic loops and the exponentiation does not necessarily go as high as to the power of the candidate.
Interestingly it was originally introduced as deterministic but relies on unproven theorem. https://en.m.wikipedia.org/wiki/Mill...primality_test Last fiddled with by a1call on 20171125 at 19:39 
20171125, 21:35  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·3,329 Posts 

20171125, 21:45  #11 
Sep 2002
Database er0rr
3×1,453 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Largest known k?  Uncwilly  Data  38  20090717 05:39 
Largest known prime  Unregistered  Information & Answers  24  20081213 08:13 
Largest 64 bit prime?  amcfarlane  Math  6  20041226 23:15 
largest factor ,i think.  heryu  Miscellaneous Math  10  20040908 11:15 
need Pentium 4s for 5th largest prime search (largest proth)  wfgarnett3  Lounge  7  20021125 06:34 