Recently when reading SICP, one footnote says:
Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a ``correct'' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering.
The footnote is referred to in:
Unfortunately, this assertion is not quite correct. There do exist numbers that fool the Fermat test: numbers n that are not prime and yet have the property that an is congruent to a modulo n for all integers a < n. Such numbers are extremely rare, so the Fermat test is quite reliable in practice. [47]
It is talking about Fermat test algorithm:
; calculate: a^n mod n
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
; check `times` count although it will fail for Carmichael numbers.
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))
Wikipedia has the above as the reference when saying
In some cases, probabilistic algorithms are the only practical means of solving a problem.
Could someone having read this book tell me what the last sentence of the 1st reference mean?
Maybe this problem is not appropriate to ask here. But since SICP is about programming, I asked here.
There is a bit of humour in that quote.
The Fermat test, if taken as an algorithm to solve the problem "Is n a prime number?", is theoretically not correct.
It is not correct, in the sense that there exists numbers n for which n passes the Fermat test but n is not prime, so the output of the algorithm is wrong for these numbers.
However, the author points out that such numbers are extremely rare: if n is a random number, then the probability that the algorithm is wrong on n for theoretical reasons is lower than the probability that a computer executing the algorithm would give the wrong result for absurdly-unlikely physical reasons.
So, to call the Fermat test "inadequate" because it doesn't fit the theoretical definition of correctness, one has to be a bit disconnected from reality. Here, "inadequate for the first reason" refers "inadequate because not theoretically correct", and "inadequate for the second reason" means "could fail in practice due to cosmic rays interfering with the electronics", something that no engineer cares about except perhaps NASA and CERN engineers.
The humorous conclusion is that a mathematician doesn't care about practical execution, but only about theoretical correctness.
This is all a bit tongue-in-cheek. If you use the Fermat test in an application, you should still be aware that the Carmichael numbers exist and that if an adversarial user can choose n, then the Fermat test can be inadequate. But if n is truly random, not chosen, then the existence of Carmichael numbers shouldn't matter to you.