20190505, 21:16  #1 
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 2PRP.
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 3PRP 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 20190505 at 21:17 
20190505, 21:23  #2 
Sep 2003
2,579 Posts 
If we ever actually find a Mersenne number that is 3PRP but composite, that will be a much bigger deal than merely finding another hohum Mersenne prime.

20190505, 21:38  #3  
"Rashid Naimi"
Oct 2015
Out of my Body
1822_{10} Posts 
Quote:


20190505, 21:40  #4 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3
13×17×41 Posts 
There was this one  1024 · 3^{1877301} + 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. 
20190506, 03:22  #5  
Jun 2015
Vallejo, CA/.
2^{2}·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:
If that is the case it is easier to go by the trial division route. 

20190506, 03:42  #6 
"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. 
20190506, 03:45  #7  
Jun 2015
Vallejo, CA/.
2^{2}×239 Posts 
Quote:


20190506, 04:07  #8 
"Rashid Naimi"
Oct 2015
Out of my Body
2×911 Posts 

20190506, 11:04  #9  
"Robert Gerbicz"
Oct 2005
Hungary
29·47 Posts 
Quote:
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 > 

20190507, 14:41  #10 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
13·19·23 Posts 
Carmichael numbers are too easy. What is the largest nonCarmichael number that is known to be bprp?

20190507, 15:28  #11 
Einyen
Dec 2003
Denmark
5·571 Posts 
There are no composite 3PRP of the form 2^{n}1 for all n<100,000 (including composite n).
Last fiddled with by ATH on 20190507 at 15:28 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Composite being Prime  kruoli  FactorDB  5  20180216 16:54 
S_N cycles in LL done on composite M(p)  tichy  Math  1  20101223 16:47 
The composite conjecture  Carl Fischbach  Miscellaneous Math  8  20100702 08:03 
Composite checkerboard  Kees  Puzzles  14  20071120 15:16 
F10,21=10^(2^21)+1 is composite  Shaopu Lin  Factoring  2  20041031 13:48 