SICP 习题参考答案 1.2

win_hate

1. 
   
2. (define (mr-test n m)
   
3.   (define (pot2 m)
   
4.     (letrec ((f (lambda (e o)
   
5.                   (if (even? o) (f (+ e 1) (/ o 2))
   
6.                       (cons e o)))))
   
7.       (f 0 m)))
   
8.   
   
9.   (define (make-test-fun)
   
10.     (define (second-check b e)
    
11.       (cond ((= (- n 1) b) #t)
    
12.             ((= 1 b) #f)
    
13.             ((= e 1) #f)
    
14.             (else (second-check (modulo (* b b) n) (- e 1)))))
    
15.    
    
16.     (let* ((t (pot2 (- n 1))) (e (car t)) (o (cdr t)))
    
17.       (lambda ()
    
18.         (let* ((r (+ (random (- n 1)) 1)) (b (powmod r o n)))
    
19.           (cond ((= 1 b) #t)
    
20.                 ((= 0 e) #f)
    
21.                 ((= (- n 1) b) #t)
    
22.                 (else (second-check b e)))))))
    
23.   
    
24.   (let ((f (make-test-fun)))
    
25.     (letrec ((loop (lambda (m)
    
26.                      (cond ((= m 0) #t)
    
27.                            ((f) (loop (- m 1)))
    
28.                            (else #f)))))
    
29.       (loop m))))
    

复制代码

对 Carmichael 数试一下效果：

1. 
   
2. >(map (lambda (x) (mr-test x 5)) '(561 1105 1729 2465 2821 6601))
   
3. (#f #f #f #f #f #f)
   

复制代码

======================================================================

理论分析：

• 如果 n 是个素数，a in [0, n). 根据 Fermat 小定理，有 a^(n-1)=1 (mod n)。
  
• n-1 是偶数，可以写成 2^mk 的形式，其中 k 是奇数。于是  a^(n-1)=1 可以改写为  a^(2^m k)。
  
• 设  b=a^k，考虑以下序列
  
  B＝( b, b^2, b^8, ..., b^(2^m k) ) (mod n)
  
  序列中的每个均是其后继模 n 意义下的平方根。
  
• 当 n 为素数时， 模 n 意义下， 1 仅有两个平方根 1 和 -1 (这是 MR 测试用来区分素数、合数的关键。对于合数 n，1 的平方根可以多于两个)。
  
• B 序列可能的模式为
  
  模式 1：(? ? ? ... ? ? ? -1 1 ... 1)
  
  模式 2：(1 1 1 ... 1 1 1 1 1 ... 1)
  
  其中 `?' 为 1, -1 以外的数，而且第一种模式包括 (-1, 1, 1, ..., 1)
  
• mr 测试的大致步骤为，依次计算 B 序列中的数（除了最后一个），
  
  • 如果一上来就是 1，则是模式 2，可以马上返回，概率推断 n 为素数。
  • 如果在途中碰到一个 -1，则是模式 1， 可以马上返回，概率推断 n 为素数。
  • 如果在途中遇到 1（但不是B0)，则不是前述两种模式，必定为合数。
  • 如果在途中一直没有碰到 1, -1，则计算到倒数第二项终止。由于倒数第二项是末项的平方根，但不是 1,-1，所以末项必定不是 1, 从而 n 也必定是个合数。
    

代码说明：

• pot2 返回一对  cons e.o，如果 n=2^m k，则 e=m, k=o.
  
• make-test-fun 的返回值是一个函数，包含了必要的参数。之后每执行其返回值一次，就进行了一次随机的 mr-test.
  
• make-test-fun 中的 second-check 是对序列检查的第二部分（对 B0 的检查比较特殊，之后的检查是 second-check）。
  
• mr-test  的流程为用 make-test-fun 生成测试函数，并绑定在 f 上。用 loop 函数实现循环测试。
  

参考资料：

• 关于 Miller-Rabin 素性测试的一般性描述，可以参考维基百科的词条：[Miller–Rabin primality test]
• 对于 Miller-Rabin 测试的更深入讨论，如失误概率的大小等，可以参考更专业的文献。比如裴定一的 [算法数论].
  

[ 本帖最后由 win_hate 于 2008-9-15 10:50 编辑 ]

win_hate

这小节完了，在这里留个空间，以备后用。

win_hate

Fermat 小定理非常有名，它是素性判定的一件利器。Fermat 数也很有名， Fermat 声称所有 Fermat 数都是素的，特别地， F_5 是一个素数。下面我们把 Fermat 小定理用到 Fermat 数上：

1. 
   
2. >(define f5 (+ 1 (pow 2 32)))
   
3. >(powmod 2 (- f5 1) f5)
   
4. 1
   

复制代码

Oops

再来

1. 
   
2. >(powmod 3 (- f5 1) f5)
   
3. 3029026160
   

复制代码

f5 不是一个素数！

虽然上面的计算不太适合手工进行，但却远非不可行的。那个时代的数学家虽然没有计算机，但那也导致了他们精于手工计算。以 Fermat 的能力，他确可以进行这种检验。Fermat 为什么不对 F5 进行检验呢？要么是他太自信了，要么就是他根本没注意到 Fermat 小定理还可以进行素性测试，我比较倾向于后一种推测。

Fermat 数列堪称史上最阴险之数列。它的前 5 个，规模比较小，适合手工分解，全是素数。但从第 6 个开始，这些数的规模急剧增长，变得不适合手工分解，但似乎都是合数！这分明就是为 Fermat 准备的一个陷阱。

Fermat 死于 1665  年，直到 100 多年后(1772)，Euler 才发现了 F5 的分解式。其方法很巧妙，大大减少了因子的测试，但利用了 Feramt 数的特征，并不是一个通用的分解方法。

[ 本帖最后由 win_hate 于 2008-9-15 11:32 编辑 ]