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 01)
        ((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 阅读(1328) 评论(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

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理