CG@CPPBLOG

/*=========================================*/
随笔 - 76, 文章 - 39, 评论 - 137, 引用 - 0
数据加载中……

我的SICP习题答案（1.24~1.28）

1.24
对于Fermat检查，因为具有log n 的增长阶，所以对于 n^2 和 n 的检查的时间比 理论上应该是 2：1， 实际上，经过测试也比较接近，当n比较大时。
若与预计不符，可能因为 n 比较小，或者字长发生变化，比如 n > 2^32 （参见下题）

1.25
仅从理论分析，Alyssa 的改动不会引起增长阶的变化，但实际上当 Fermat 检查的 n 稍微大一点，速度就会很慢。主要原因 就是 base^exp 是一个非常大的数，可能远远超过 一个32位机字的表示范围 2^32 ，在 scheme 里可能用若干个 32-bit 靠软件实现运算，这将导致计算急速增长。无论是传递、运算还是求模。
实际上 1.22、1.23、1.24 的几个题目可能都会遇到字长变化引起的计算速度突变。

1.26
Fermat 检查正是因为 连续求平方的求幂方法，使得的增长阶变为 log n， 而这均来源于 b^(2n) = (b^n)^2，Louis 的方法让求幂又变成了连乘，b^(2n) = b^n*b^n = (b*b*...*b)*(b*b*...*b)，求幂的增长阶变成了 O(n)，Fermat 检查的增长阶自然也变成了 O(n)。

1.27
(define (fermat-test n)
  (fermat-iter (- n 1) n))

(define (fermat-iter a n)
  (cond ((= a 0) #t)
        ((= (expmod a n n) a) (fermat-iter (- a 1) n))
        (else #f)))

1.28
首先来看，Fermat 小定理的一个变形：

p 是素数, 1<a<p, 有 a^p % p = a
==> a^p = kp + a ==> a^p - a = kp ==> a(a^(p-1)-1) = kp ==> a^(p-1) -1 = k'p
==> a^(p-1) % p = 1

这个变形就是题目中提到的，这个形式和费马小定理是等价的（但是奇怪的是，我没有发现已知的几个Carmichael数能够躲过这个变形的检查，有待研究①）

再来看，miller-rabin 素性测试的原理：

p 是素数， 1<a<p, 且 a^2 % p = 1
==> (a^2-1) % p = 0 ==> (a+1)(a-1) % p =0
那么 a+1 % p = 0 或者 a-1 % p =0,
又 a<p 且 p 是素数，所以
a = 1 或者 a = p-1 （这两个叫做 1模n的平凡平方根）

代码如下：
(define (check-nontrivial-sqrt-of-one a n)
  (define (check-1? t)
    (if (and (> a 1)
             (< a (- n 1))
             (= t 1))
        0 t))
  (check-1? (remainder (square a) n)))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         ;(remainder (square (expmod base (/ exp 2) m)) m))
         (check-nontrivial-sqrt-of-one (expmod base (/ exp 2) m) m))
        (else
         (remainder (* base (expmod base (- exp 1) m)) m))))

(define (miller-rabin-test n)
  (define (iter x n)
    (cond ((= x 0) #t)
          ((= (expmod x (- n 1) n) 1) (iter (- x 1) n))
          (else #f)))
  (iter (- n 1) n))

① 对于 Carmichael 数 n ，实际上不能完全通过 a^(n-1)%n = 1 的检查，除非 a 与 n 互素，当 a 为 n 的素因子时，不能通过，比如 Carmichael 第一个 561 = 3*11*17， 而 3^560%561 = 375 ≠ 1 。可以程序验证这个。 所以我认为，a^(n-1)%n = 1 的检查比 a^n%n = a 的检查更严格，是不是不存在合数通过完全的 a^(n-1)%n = 1 的检查呢？我不敢说。但把这个结论暂时记在这里，希望能得到帮助或者反驳。2008-04-02 23:56

posted on 2008-03-31 00:21 cuigang 阅读(1538) 评论(2)  编辑 收藏 引用 所属分类: Lisp/Scheme 、我的SICP答案

评论

# re: 我的SICP习题答案（1.24~1.28）  回复  更多评论   

a^(n-1)%n = 1 跟 a^n%n = a 应该是完全等价的吧？
2009-03-25 21:10 | pgw

# re: 我的SICP习题答案（1.24~1.28）  回复  更多评论   

@pgw

好吧。。 我错了
2009-03-25 21:42 | pgw

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理