mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2019-05-05, 21:16   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

5×571 Posts
Default 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
ATH is offline   Reply With Quote
Old 2019-05-05, 21:23   #2
GP2
 
GP2's Avatar
 
Sep 2003

2,579 Posts
Default

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.
GP2 is offline   Reply With Quote
Old 2019-05-05, 21:38   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

182210 Posts
Default

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
a1call is offline   Reply With Quote
Old 2019-05-05, 21:40   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

13×17×41 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2019-05-06, 03:22   #5
rudy235
 
rudy235's Avatar
 
Jun 2015
Vallejo, CA/.

22·239 Posts
Default

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 View Post
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.
rudy235 is offline   Reply With Quote
Old 2019-05-06, 03:42   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

2·911 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2019-05-06, 03:45   #7
rudy235
 
rudy235's Avatar
 
Jun 2015
Vallejo, CA/.

22×239 Posts
Default

Quote:
Originally Posted by a1call View Post
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*
rudy235 is offline   Reply With Quote
Old 2019-05-06, 04:07   #8
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

2×911 Posts
Default

Quote:
Originally Posted by rudy235 View Post
You're right that's how they do it. My comment was a bit *tongue in cheek*
Acknowledged. Apologies for missing that.
a1call is offline   Reply With Quote
Old 2019-05-06, 11:04   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

29·47 Posts
Default

Quote:
Originally Posted by rudy235 View Post
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).
R. Gerbicz is offline   Reply With Quote
Old 2019-05-07, 14:41   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

13·19·23 Posts
Default

Carmichael numbers are too easy. What is the largest non-Carmichael number that is known to be b-prp?
henryzz is offline   Reply With Quote
Old 2019-05-07, 15:28   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

5·571 Posts
Default

Quote:
Originally Posted by GP2 View Post
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
ATH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Composite being Prime kruoli FactorDB 5 2018-02-16 16:54
S_N cycles in LL done on composite M(p) tichy Math 1 2010-12-23 16:47
The composite conjecture Carl Fischbach Miscellaneous Math 8 2010-07-02 08:03
Composite checkerboard Kees Puzzles 14 2007-11-20 15:16
F10,21=10^(2^21)+1 is composite 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

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.