Composite PRP

[LaurV]

Originally Posted by GP2

But we test the cofactor to multiple bases

That was a joke, but thanks for the clarification. It was a joke in the sense that even if Jeppe wouldn't find a counterexample, we still could not say anything about the "definitive" primality of the cofactors, until my "assumption" would have been proved theoretically. In this respect, finding or not finding factors which are 3-PRP, has nothing to do with the primality of the cofactors, and the "it's a pity.. blah blah" is a non-sequitur. We know that the chance of the cofactors being composite is astronomically-minuscule( I have to apply for a patent for this contraption!), but yet, it is not proved. Most of us (me included) will bet their life that those numbers a prime. But again, we can joke about it, but more we can't do..

[Dr Sardonicus]

Originally Posted by henryzz

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

It occurred to me to wonder about composite numbers n for which there are very few bases b, 1 < b < n - 1, for which b^n-1 == 1 (mod n). I'm sure this is all well-known, but it's also easy enough that, if extant in the literature, it may be relegated to textbook exercises.

Obviously, if n is even, n-1 is odd, so gcd(n-1,eulerphi(n)) has to be odd. If the gcd is 1, there are no bases b for which n is even a Fermat pseudoprime. The first even integer for which the gcd is greater than 1, is n = 28.

A very simple case for odd n is, for odd prime p, n = 2*p + 1, n - 1 = 2*p. Obviously eulerphi(n) is even, but, if n is composite, will not be divisible by p.

Since n - 1 is only divisible by 2 once, if n is composite then gcd(n-1, eulerphi(n)) = 2. Thus, the only bases b for which b^n-1 == 1 (mod n) must be congruent to 1 or -1 modulo each prime(-power) factor of n.

Since (n - 1)/2 is odd, there is no base b, 1 < b < n - 1, for which n "passes" Miller-Rabin.