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

[url]https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test[/url]
[url]https://arxiv.org/abs/1509.00864[/url]



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?

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.

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

[url]https://en.m.wikipedia.org/wiki/Carmichael_number[/url]

There was [URL="https://primes.utm.edu/primes/page.php?id=118946#comments"]this one[/URL] - 1024 · 3[SUP]1877301[/SUP] + 1.
An excellent PRP in many bases, [I]resisted[/I] 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.

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=a1call;515874][url]https://en.m.wikipedia.org/wiki/Carmichael_number[/url][/QUOTE]

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[SUP]14[/SUP]
If that is the case it is easier to go by the trial division route.

Here is their paper:

[B]A new algorithm for constructing large Carmichael numbers[/B]

[url]https://www.semanticscholar.org/paper/A-new-algorithm-for-constructing-large-Carmichael-L%C3%B6h-Niebuhr/12e8343a0cdab51655a9ac77a4e792bc3eb6f90a[/url]

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.

[QUOTE=a1call;515911]Here is their paper:

[B]A new algorithm for constructing large Carmichael numbers[/B]

[url]https://www.semanticscholar.org/paper/A-new-algorithm-for-constructing-large-Carmichael-L%C3%B6h-Niebuhr/12e8343a0cdab51655a9ac77a4e792bc3eb6f90a[/url]

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.[/QUOTE]

You're right that's how they do it. My comment was a bit *tongue in cheek*

[QUOTE=rudy235;515912]You're right that's how they do it. My comment was a bit *tongue in cheek*[/QUOTE]

Acknowledged. Apologies for missing that.:smile:

[QUOTE=rudy235;515910]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]

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 >
[/CODE]
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).

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

[QUOTE=GP2;515870]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.[/QUOTE]

There are no composite 3-PRP of the form 2[SUP]n[/SUP]-1 for all n<100,000 (including composite n).