Chronology Current Month Current Thread Current Date
[Year List] [Month List (current year)] [Date Index] [Thread Index] [Thread Prev] [Thread Next] [Date Prev] [Date Next]

Re: [Phys-l] Carmichael numbers agai



On 05/17/2007 03:01 PM, E Muehleisen wrote:

I am confused. If all Carmichael numbers are the product of three primes and 2 is a prime number, it would seem that there is a large number of even Carmichael numbers???

That's missing the point by a wide margin.

The point of Carmichael numbers is that they are not only pseudoprimes,
but extra-strength pseudoprimes.
http://www.chalcedon.demon.co.uk/rgep/carpsp.html

I find it unlikely that any even number would pass for a pseudoprime.

================

Looking at this from a higher level, there is a huuuge difference
between "is" and "is by definition". There is a huuuge difference
between "necessary" and "necessary and sufficient".
-- The property of being expressible as a product of three primes
is a /property/ of /some/ Carmichael numbers.
-- It is not even a /necessary/ property of Carmichael numbers.
-- It is certainly not the /defining/ property of Carmichael numbers.

===============================

Pseudoprimes are of practical importance in some applications. For
one thing, one of the most practical ways of finding large primes
is to pick numbers more-or-less at random and then test them for
primality. And the Euler totient test is an efficient test for
primality ... except for the fact that it passes pseudoprimes as
well as righteous primes. So you need to do some post-processing
to get rid of the pseudoprimes.

RSA and related cryptosystems are among the practical uses of large
primes.