Re: Web site about Carmichael numbers

Phil Carmody a écrit :
mm <mm@xxxxxxxxxx> writes:
robert maas, see http://tinyurl.com/uh3t a écrit :
That's not true at all if you use the correct Fermat test, namely
take n-1 power and check if result is 1. For every base which is
not relatively prime to the Carmichael number being tested, the
test will fail. For the smallest Carmichael number (561), that's
nearly 40% of the time.
By definition, a Carmichael number N is pseudoprime for all bases to
which it is relatively prime. So, by definition, if 561 hadn't this
property, it wouldn't be a Carmichael number.

So either your program is buggy or it performs strong pseudoprimality
tests (not pseudoprimality ones).

Yes, but for approximately 40% of the time, the base is "not relatively
prime to the Carmichael number being tested". (It's actually 43%, not "nearly 40%".)

This thread could be called "Total confusion". I just understood (yes,
it occurs from time to time).

Since RM was trying to correct something that is correct, I was
convinced that he was making a mistake, and it helped me to overlook the
"not" in his "which is not relatively prime". :-)

To RM:
If you use the Fermat test "B^N = B (mod N)", there is no need to use
B such that gcd(B,N)=1. And, what the 'OP' wrote on his page, "Some
numbers that are not prime still pass the Fermat test with every number
smaller than themselves. These numbers are called Carmichael numbers.",
is true, since he uses 1 < B < N.
Btw, the test "B^(N-1) = 1 (mod N)" is not more correct than the
previous one. These two tests are different but both are correct.

mm
.

Quantcast