最近在阅读SICP时，有一个脚注写道：
能通过费马测试的数字被称为卡迈克尔数，除了它们极其罕见之外，人们对它们知之甚少。100,000,000 以下有 255 个卡迈克尔数。最小的几个是 561、1105、1729、2465、2821 和 6601。在测试随机选择的非常大的数字的素数时，偶然发现能通过费马测试的值的概率小于宇宙辐射导致计算机在执行“正确”算法时出错的概率。认为算法因第一个原因而不充分，但因第二个原因而不充分，说明了数学和工程学之间的区别。
脚注引用于：
不幸的是，这个断言并不完全正确。确实存在一些能欺骗费马检验的数：数 n 不是素数，但具有这样的性质：对于所有整数 a < n ， an 与 a 模 n 一致。这样的数极其罕见，因此费马检验在实践中相当可靠。[47]
它谈论的是费马检验算法：
; 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)))
维基百科引用了上述内容
在某些情况下，概率算法是解决问题的唯一实用方法。
有人读过这本书吗？能告诉我第一个参考文献的最后一句话是什么意思吗？
也许这个问题不适合在这里问。但由于 SICP 是关于编程的，所以我在这里问了。
这句话有一点幽默。
费马检验法，如果作为解决“ n是不是素数？”这个问题的算法，理论上是错误的。
它是不正确的，因为存在数字n，对于这些数字， n通过了费马检验，但n不是素数，所以该算法的输出是错误的。
然而，作者指出，这样的数字极为罕见：如果n是一个随机数，那么由于理论原因，算法在n上出错的概率低于执行该算法的计算机由于极不可能的物理原因而给出错误结果的概率。
因此，如果因为费马测试不符合正确性的理论定义而称其“不充分”，那么就有点脱离现实了。这里，“第一个原因不充分”是指“由于理论上不正确而不足”，而“第二个原因不充分”是指“由于宇宙射线干扰电子设备，在实践中可能会失败”，除了 NASA 和 CERN 工程师之外，没有工程师关心这一点。
幽默的结论是，数学家并不关心实际执行，而只关心理论上的正确性。
这有点讽刺。如果你在应用程序中使用费马测试，你仍然应该知道卡迈克尔数是存在的，并且如果敌对用户可以选择n，那么费马测试可能不够充分。但如果n是真正随机的，而不是选择的，那么卡迈克尔数的存在对你来说就不重要了。