mersenneforum.org > Math Composite PRP
 Register FAQ Search Today's Posts Mark Forums Read

 2019-05-05, 21:16 #1 ATH Einyen     Dec 2003 Denmark 5×571 Posts Composite PRP What is the largest PRP (by any PRP test) known to be composite? Except the trivial cases like: Any Mersenne number is a 2-PRP. The largest one I can think of is this: 3,317,044,064,679,887,385,961,981 which is SPRP to the first 13 prime bases: 2 to 41 https://en.wikipedia.org/wiki/Miller...primality_test https://arxiv.org/abs/1509.00864 If we find a Mersenne Prime candidate with a single 3-PRP test on a lets say 90M exponent, what is the probability it is prime and the probability it is composite? Last fiddled with by ATH on 2019-05-05 at 21:17
 2019-05-05, 21:23 #2 GP2     Sep 2003 2,579 Posts If we ever actually find a Mersenne number that is 3-PRP but composite, that will be a much bigger deal than merely finding another ho-hum Mersenne prime.
2019-05-05, 21:38   #3
a1call

"Rashid Naimi"
Oct 2015
Out of my Body

182210 Posts

Quote:
 Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with 1,101,518 factors and over 16 million digits.
https://en.m.wikipedia.org/wiki/Carmichael_number

 2019-05-05, 21:40 #4 Batalov     "Serge" Mar 2008 Phi(3,3^1118781+1)/3 13×17×41 Posts There was this one - 1024 · 31877301 + 1. An excellent PRP in many bases, resisted to be proven (returned 'composite'; and even was removed from the UTM list as a composite), but that helped to find a bug. It was prime, after all.
2019-05-06, 03:22   #5
rudy235

Jun 2015
Vallejo, CA/.

22·239 Posts

Quote:

Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with 1,101,518 factors and over 16 million digits.

Quote:
 Originally Posted by a1call https://en.m.wikipedia.org/wiki/Carmichael_number
Ok Wait a minute if it has so many factors and and is over 16 Million Digits it means at least one of the factors is < 214
If that is the case it is easier to go by the trial division route.

 2019-05-06, 03:42 #6 a1call     "Rashid Naimi" Oct 2015 Out of my Body 2·911 Posts Here is their paper: A new algorithm for constructing large Carmichael numbers https://www.semanticscholar.org/pape...e792bc3eb6f90a I assume (without having read the paper) that they construct the numbers by multiplying the prime factors together, which in turn gives the astronomically high number of factor combinations.
2019-05-06, 03:45   #7
rudy235

Jun 2015
Vallejo, CA/.

22×239 Posts

Quote:
 Originally Posted by a1call Here is their paper: A new algorithm for constructing large Carmichael numbers https://www.semanticscholar.org/pape...e792bc3eb6f90a I assume (without having read the paper) that they construct the numbers by multiplying the prime factors together, which in turn gives the astronomically high number of factor combinations.
You're right that's how they do it. My comment was a bit *tongue in cheek*

2019-05-06, 04:07   #8
a1call

"Rashid Naimi"
Oct 2015
Out of my Body

2×911 Posts

Quote:
 Originally Posted by rudy235 You're right that's how they do it. My comment was a bit *tongue in cheek*
Acknowledged. Apologies for missing that.

2019-05-06, 11:04   #9
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

29·47 Posts

Quote:
 Originally Posted by rudy235 Quote: Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with 1,101,518 factors and over 16 million digits.
Smaller number, but with a compact formula:
Code:
(13:03) gp > n=4142384337001350354048000*2^3000+85926168257054400*2^2000+530295120*2^1000+1;
(13:03) gp > isprime(n)
%36 = 0
(13:03) gp > lift(Mod(2,n)^n)
%37 = 2
(13:03) gp > lift(Mod(3,n)^n)
%38 = 3
(13:03) gp > lift(Mod(5,n)^n)
%39 = 5
(13:03) gp > lift(Mod(7,n)^n)
%40 = 7
(13:03) gp >
it is a Carmichael number, so composite and PRP for all base relative prime to n. (factorization of these numbers is easy, even without giving out the above form).

 2019-05-07, 14:41 #10 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT) 13·19·23 Posts Carmichael numbers are too easy. What is the largest non-Carmichael number that is known to be b-prp?
2019-05-07, 15:28   #11
ATH
Einyen

Dec 2003
Denmark

5·571 Posts

Quote:
 Originally Posted by GP2 If we ever actually find a Mersenne number that is 3-PRP but composite, that will be a much bigger deal than merely finding another ho-hum Mersenne prime.
There are no composite 3-PRP of the form 2n-1 for all n<100,000 (including composite n).

Last fiddled with by ATH on 2019-05-07 at 15:28

 Similar Threads Thread Thread Starter Forum Replies Last Post kruoli FactorDB 5 2018-02-16 16:54 tichy Math 1 2010-12-23 16:47 Carl Fischbach Miscellaneous Math 8 2010-07-02 08:03 Kees Puzzles 14 2007-11-20 15:16 Shaopu Lin Factoring 2 2004-10-31 13:48

All times are UTC. The time now is 07:25.

Sun Jul 12 07:25:42 UTC 2020 up 109 days, 4:58, 0 users, load averages: 1.56, 1.78, 1.72