![]() |
![]() |
#1 |
"Rashid Naimi"
Oct 2015
Remote to Here/There
23·293 Posts |
![]()
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...st-known-prime * 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. |
![]() |
![]() |
![]() |
#2 | |
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts |
![]() Quote:
|
|
![]() |
![]() |
![]() |
#3 |
"Rashid Naimi"
Oct 2015
Remote to Here/There
23×293 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. |
![]() |
![]() |
![]() |
#4 | |
Sep 2003
3×863 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. |
|
![]() |
![]() |
![]() |
#5 | |
Sep 2003
258910 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. |
|
![]() |
![]() |
![]() |
#6 | |
Sep 2002
Database er0rr
5·29·31 Posts |
![]() Quote:
![]() |
|
![]() |
![]() |
![]() |
#7 |
"Rashid Naimi"
Oct 2015
Remote to Here/There
23·293 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 2017-11-25 at 17:47 |
![]() |
![]() |
![]() |
#8 |
Sep 2002
Database er0rr
5·29·31 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 2017-11-25 at 18:21 |
![]() |
![]() |
![]() |
#9 |
"Rashid Naimi"
Oct 2015
Remote to Here/There
23×293 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 2017-11-25 at 19:39 |
![]() |
![]() |
![]() |
#10 |
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×7×479 Posts |
![]() |
![]() |
![]() |
![]() |
#11 |
Sep 2002
Database er0rr
106178 Posts |
![]() |
![]() |
![]() |
![]() |
Thread Tools | |
![]() |
||||
Thread | Thread Starter | Forum | Replies | Last Post |
Largest known k? | Uncwilly | Data | 38 | 2009-07-17 05:39 |
Largest known prime | Unregistered | Information & Answers | 24 | 2008-12-13 08:13 |
Largest 64 bit prime? | amcfarlane | Math | 6 | 2004-12-26 23:15 |
largest factor ,i think. | heryu | Miscellaneous Math | 10 | 2004-09-08 11:15 |
need Pentium 4s for 5th largest prime search (largest proth) | wfgarnett3 | Lounge | 7 | 2002-11-25 06:34 |