Composite PRP

[ATH]

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?

[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.

[a1call]

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

[Batalov]

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.

[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.

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 < 2¹⁴
If that is the case it is easier to go by the trial division route.

[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.

[rudy235]

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*

[a1call]

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.

[R. Gerbicz]

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:

(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).

[henryzz]

Carmichael numbers are too easy. What is the largest non-Carmichael number that is known to be b-prp?

[ATH]

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 2ⁿ-1 for all n<100,000 (including composite n).