mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Probability & Probabilistic Number Theory

Reply
 
Thread Tools
Old 2017-11-25, 16:48   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3·641 Posts
Default 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...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.
a1call is offline   Reply With Quote
Old 2017-11-25, 16:57   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
http://www.primenumbers.net/prptop/prptop.php comes up on quick google search. there's probablya table somewhere on primes.utm.edu
science_man_88 is offline   Reply With Quote
Old 2017-11-25, 17:08   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3·641 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2017-11-25, 17:09   #4
GP2
 
GP2's Avatar
 
Sep 2003

29·89 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
http://www.primenumbers.net/prptop/prptop.php comes up on quick google search. there's probablya table somewhere on primes.utm.edu
The primes.utm.edu site only deals with proven primes, not probable primes.

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.
GP2 is offline   Reply With Quote
Old 2017-11-25, 17:13   #5
GP2
 
GP2's Avatar
 
Sep 2003

29·89 Posts
Default

Quote:
Originally Posted by a1call View Post
Is it true that PRP tests are generally as slow as LLR tests? ( I doubt it)
I vaguely recall reading that LL tests are O(p2 log p), but PRP tests on Mersenne exponents are O(p3 log p).

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.
GP2 is offline   Reply With Quote
Old 2017-11-25, 17:18   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

344110 Posts
Default

Quote:
Originally Posted by GP2 View Post
I vaguely recall reading that LL tests are O(p2 log p), but PRP tests on Mersenne exponents are O(p3 log p).

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.
Mersenne cofactors can make full use of working modulo the parent Mersenne, with a final reduction modulo the cofactor at the end of the program run.
paulunderwood is online now   Reply With Quote
Old 2017-11-25, 17:45   #7
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3×641 Posts
Default

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
a1call is offline   Reply With Quote
Old 2017-11-25, 17:53   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·31·37 Posts
Default

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
paulunderwood is online now   Reply With Quote
Old 2017-11-25, 19:37   #9
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3·641 Posts
Default

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
a1call is offline   Reply With Quote
Old 2017-11-25, 21:35   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23A316 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Edit: I should add that taking modulo Eisenstein numbers is also fast.
Have you run any comparisons?
Batalov is offline   Reply With Quote
Old 2017-11-25, 21:45   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

65618 Posts
Default

Quote:
Originally Posted by Batalov View Post
Have you run any comparisons?
No.
paulunderwood is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
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

All times are UTC. The time now is 04:01.

Thu Oct 22 04:01:35 UTC 2020 up 42 days, 1:12, 0 users, load averages: 1.90, 1.68, 1.60

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.