咨询SICP中费马测试注释含义与随机算法安全使用时机

背景说明 #

SICP中的费马测试相关内容 #

正文引用：

遗憾的是，这一论断并不完全正确。确实存在能“骗过费马测试”的数：即非素数n，却满足对所有小于n的整数a，aⁿ与a模n同余的性质。这类数极为罕见，因此费马测试在实践中相当可靠。[47]

对应的脚注内容：

能“骗过费马测试”的数被称为卡迈克尔数，除了知道它们极为罕见外，人们对其了解甚少。在100,000,000以内有255个卡迈克尔数，最小的几个是561、1105、1729、2465、2821和6601。在测试随机选取的极大数的素性时，碰到能骗过费马测试的数的概率，低于宇宙射线导致计算机在执行“正确”算法时出错的概率。因前者认定算法不足却不因后者否定算法，这体现了数学与工程学的差异。

费马测试的Lisp实现代码：

; 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)))

维基百科相关引用：

在某些情况下，概率算法是解决问题的唯一实用手段。

问题解答 #

1. 从概率角度看，何时可安全使用随机算法？ #

当随机算法的出错概率被控制到远低于系统中其他不可控风险导致的错误概率时，就可以安全投入使用。具体要满足两个核心条件：

• 算法的出错概率可通过重复执行等手段被压低到可接受的阈值以下，比如费马测试可以通过多次随机选取底数测试，把误判概率降到极低；
• 此时算法的理论出错概率要比硬件故障、环境干扰（比如宇宙射线）这类无法完全避免的系统固有错误概率还要小，也就是说，算法本身的风险已经可以忽略不计，不会成为系统中最薄弱的环节。

2. SICP中第一则脚注的最后一句话具体含义是什么？ #

这句话点明了数学与工程学的核心差异：

• 数学领域追求绝对的正确性，只要存在理论上的例外（比如卡迈克尔数能骗过费马测试），就会认定这个算法存在缺陷，不是完美的解决方案；
• 工程领域更看重实践中的可靠性，只要算法出错的概率比计算机执行“完全正确”算法时因硬件/环境问题出错的概率还低，这种理论上的瑕疵就不会成为否定算法实用性的理由——毕竟工程中没有绝对的零风险，只要风险低到可以接受，高效实用的方案就是最优选择。

内容的提问来源于stack exchange，提问作者An5Drama