Article Outline
在 SICP 1,3 节的时候有提到判断素数的方法。 朴素的素数判定，地球的同学都知道的，如果数 n 除 1 以外的最小因数是他自己，那么n就是素数。
(define (remainder num divisor)
(- num (* divisor (round (/ num divisor)))))
;return the smallest divisor of n
(define (smallest-divisor n)
;find a divisor(for 2 to n) of n
(define (find-divisor n test-divisor)
(cond ((< n (sqrt test-divisor)) n)
((= (remainder n test-divisor) 0) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(find-divisor n 2))
;check n is prime or not
(define (prime? n)
(= n (smallest-divisor n )))但这个方法很慢，它的阶是O(n)。
下面 SICP 给出了费马小定理：
如果一个数 n 是一个素数，而对而对任意 a<n，有 a^n≡a(mod n)
可惜哈，它的逆定理不成立，不过不代表不可用。我们可以挑选小于 n 的数 a，做上文所述的测试。如果满足 a^n≡a(mod n)，那么 n 很可能是一个素数。而挑选越多的 a 对 n 进行测试，n 是素数的可能性也越大。所以这是一个人品算法，只要测试的数量足够，那么 n 不是素数的概率就会变得很小。
于是我们有了 fermat 测试的程序。不用担心求 a^n 的效率问题，因为比较好解决：
试看：
a^n = (a^(n/2))^2; 当n为偶数
a^n = a* a^(n-1); 当n为奇数总是成立的，所以几乎每次作乘法的时候，n 就增加了一倍。放到数轴看一看，其实这是二分法。所以时间复杂度得到降低。所以大概知道为什么编程语言提供了求 n 次幂的函数 pow 总是比自己写的 a*a*a… 快了。
但是不应该直接使用语言自带的 pow 函数。原因是我们的目标不是 a 的 n 次幂，而是想知道 a 的 n 次幂对 m 取模是否等于 a 对 m 取模。简化一下，即只需判断这个表达式是否成立：a^n mod m = a。如果直接表达成 pow(a, n) % m == a 计算机会郁闷，因为 pow(a, n) 的值会很大。所以应该采用类似的技术：
a^n mod m = ((a^(n / 2))^2) mod m; 当n为偶数
a^n mod m = (a* a^(n-1)) mod m; 当n为奇数这样，每次计算得到的值都不比 m 大了，避免过大的数参与计算。于是很容易有了以下程序
(define (remainder num divisor)
(- num (* divisor (round (/ num divisor)))))
(define (expmod base exps m)
(define (square n) (* n n))
(cond ((= exps 0) 1)
((even? exps)
(remainder (square (expmod base (/ exps 2) m))
m))
(else
(remainder (* base (expmod base (- exps 1) m))
m))))
;fermat test, check n. if (a^n) mod n == a then in all probability n is a prime
(define (fermat-test n)
(define (try-it a)
(= a (expmod a n n)))
;(= a (remainder (expt a n) n)))
(try-it (+ 1 (random (- n 1)))))
;get prime by fermat-test. test n is prime or not, try times time
(define (fermat-prime? n times)
(cond ((= 0 times) #t)
((fermat-test n) (fermat-prime? n (- times 1)))
(else #f)))但是，总有一些不完美。
存在一种数叫 Carmichael 数，能骗过费马测试。在 2 到 10000 这个区间内有这么几个：
561，1105，1729，2465，2821，6601，8911
这些钉子户是合数，但是不管你用什么 a 去测试，他们都可以在费马测试中冒充素数。他们数量也不少，而分布广，在100 000 000 以内一共有 255 个 Carmichael 数。所以，如果不愿意去记录 Carmichael 数表的话，可以加强我们的素数测试方法。
还好，在练习 1.28中，Miller 和 Rabin 给我们带来了 Miller-Rabin 测试法。该测试法基于 fermat 小定理的一个变形：
如果 n 是素数，对任何 a < n，a^(n-1) ≡ 1(mod n)
要使用 MR 测试法呢，就需要在执行上文 Fermat 测试的平方步骤时检查是否遇到了一个 “1 mod n的非平凡平方根”，如果存在一个 s = a^2; 而且 s <> 1 且 s <> n-1，而且 s^2 mod m = 1，那么这个数n就不是素数了。
Matrix67：Miller-Rabin 素性测试同样是不确定算法，我们把可以通过以a为底的 Miller-Rabin 测试的合数称作以a为底的强伪素数(strong pseudoprime)。第一个以 2 为底的强伪素数为 2047。第一个以 2 和 3 为底的强伪素数则大到 1 373 653。
所以当你测试量足够，那么该方法可以在工业应用中保证安全，下面是我写的1.28题答案
(define (remainder num divisor)
(- num (* divisor (round (/ num divisor)))))
(define (mr-expmod base exps m)
(define (square x) (* x x))
(define (check-square-root x n)
(define (check r)
(if (and (not (= x 1)) (not (= x (- n 1))) (= r 1)) 0 r))
(check (remainder (square x) n)))
(cond ((= exps 0) 1)
((even? exps)
(check-square-root(mr-expmod base (/ exps 2) m) m))
(else
(remainder (* base (mr-expmod base (- exps 1) m))
m))))
;Miller-Rabin test, check n. if (a^(n-1)) mod n == 1 then in all probability n is a prime
(define (mr-test n)
(define (try-it a)
(= 1 (mr-expmod a (- n 1) n)))
(try-it (+ 1 (random (- n 1)))))
;get prime by Miller-Rabin-test. test n is prime or not, try times time
(define (mr-prime? n times)
(cond ((= 0 times) #t)
((mr-test n) (mr-prime? n (- times 1)))
(else #f)))
我构造了一些数据，分别求[1000, 1100], [10000, 10100], [100000, 100100], [1000000, 1000100]这些区间的素数，看看它们这些方法的表现如何：
常规方法 常规方法的因数2优化版本 Miller-Rabin测试法
[1000, 1100] 1 ms 1 ms 1 ms
[10000, 10100] 13 ms 8 ms 1 ms
[100000, 100100] 142 ms 78 ms 1 ms
[1000000, 1000100] 1337 ms 830 ms 1 ms这是在我的 intel Core 1 1.83GHz 的机器上跑的结果（Ubuntu 8.04 + DrScheme）。
我还另写了一个 C 语言的版本，运行结果如下：
区间[2, 10000]
$ ./prime
Normal: return 0 cost 10ms
Fermat: return 0 cost 24ms
Miller-Rabin: return 0 cost 28ms区间[200000, 1000000]:
$ ./prime
Normal: return 0 cost 3088ms
Fermat: return 0 cost 824ms
Miller-Rabin: return 0 cost 959ms采用 gprof 分析的结果基本与预期一致，部分分析报告如下：
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
63.55 2.58 2.58 800000 3.23 3.23 is_prime(int)
15.76 3.22 0.64 800005 0.80 0.84 fermat_expmod(long, long, long)
10.10 3.63 0.41 800012 0.51 0.88 mr_expmod(long, long, long)
7.27 3.92 0.29 14813786 0.02 0.02 chk_unusual_square_root(long, long)
1.23 3.98 0.05 main
0.86 4.01 0.04 800000 0.04 0.93 mr_test(long, long)
0.74 4.04 0.03 14813658 0.00 0.00 square(long)
0.25 4.05 0.01 800000 0.01 0.94 mr_is_prime(int)
0.25 4.06 0.01 800000 0.01 0.85 fermat_is_prime(int)
0.00 4.06 0.00 800000 0.00 0.84 fermat_test(long, long)当 n 比较小的时候效果不好的原因我猜是 C 语言在处理普通递归时花销比较大。而当数据变得庞大时，这种递归上的花销的影响就相对不大了。如果有同学把上面的算法改成迭代形式（我不会改:P）或者是尾递归形式（gcc可以把尾递归形式优化成迭代形式）我想效果更加明显。
