CG@CPPBLOG

/*=========================================*/

隨筆 - 76, 文章 - 39, 評(píng)論 - 137, 引用 - 0

數(shù)據(jù)加載中……

我的SICP習(xí)題答案（1.24~1.28）

1.24
對(duì)于Fermat檢查，因?yàn)榫哂衛(wèi)og n 的增長(zhǎng)階，所以對(duì)于 n^2 和 n 的檢查的時(shí)間比理論上應(yīng)該是 2：1，實(shí)際上，經(jīng)過測(cè)試也比較接近，當(dāng)n比較大時(shí)。
若與預(yù)計(jì)不符，可能因?yàn)?n 比較小，或者字長(zhǎng)發(fā)生變化，比如 n > 2^32 （參見下題）

1.25
僅從理論分析，Alyssa 的改動(dòng)不會(huì)引起增長(zhǎng)階的變化，但實(shí)際上當(dāng) Fermat 檢查的 n 稍微大一點(diǎn)，速度就會(huì)很慢。主要原因就是 base^exp 是一個(gè)非常大的數(shù)，可能遠(yuǎn)遠(yuǎn)超過一個(gè)32位機(jī)字的表示范圍 2^32 ，在 scheme 里可能用若干個(gè) 32-bit 靠軟件實(shí)現(xiàn)運(yùn)算，這將導(dǎo)致計(jì)算急速增長(zhǎng)。無論是傳遞、運(yùn)算還是求模。
實(shí)際上 1.22、1.23、1.24 的幾個(gè)題目可能都會(huì)遇到字長(zhǎng)變化引起的計(jì)算速度突變。

1.26
Fermat 檢查正是因?yàn)?連續(xù)求平方的求冪方法，使得的增長(zhǎng)階變?yōu)?log n，而這均來源于 b^(2n) = (b^n)^2，Louis 的方法讓求冪又變成了連乘，b^(2n) = b^n*b^n = (b*b*...*b)*(b*b*...*b)，求冪的增長(zhǎng)階變成了 O(n)，F(xiàn)ermat 檢查的增長(zhǎng)階自然也變成了 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
首先來看，F(xiàn)ermat 小定理的一個(gè)變形：

p 是素?cái)?shù), 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

這個(gè)變形就是題目中提到的，這個(gè)形式和費(fèi)馬小定理是等價(jià)的（但是奇怪的是，我沒有發(fā)現(xiàn)已知的幾個(gè)Carmichael數(shù)能夠躲過這個(gè)變形的檢查，有待研究①）

再來看，miller-rabin 素性測(cè)試的原理：

p 是素?cái)?shù)， 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 是素?cái)?shù)，所以
a = 1 或者 a = p-1 （這兩個(gè)叫做 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))

① 對(duì)于 Carmichael 數(shù) n ，實(shí)際上不能完全通過 a^(n-1)%n = 1 的檢查，除非 a 與 n 互素，當(dāng) a 為 n 的素因子時(shí)，不能通過，比如 Carmichael 第一個(gè) 561 = 3*11*17，而 3^560%561 = 375 ≠ 1 。可以程序驗(yàn)證這個(gè)。所以我認(rèn)為，a^(n-1)%n = 1 的檢查比 a^n%n = a 的檢查更嚴(yán)格，是不是不存在合數(shù)通過完全的 a^(n-1)%n = 1 的檢查呢？我不敢說。但把這個(gè)結(jié)論暫時(shí)記在這里，希望能得到幫助或者反駁。2008-04-02 23:56

posted on 2008-03-31 00:21 cuigang 閱讀(1571) 評(píng)論(2) 編輯收藏引用所屬分類: Lisp/Scheme 、我的SICP答案

評(píng)論

# re: 我的SICP習(xí)題答案（1.24~1.28）回復(fù) 更多評(píng)論

a^(n-1)%n = 1 跟 a^n%n = a 應(yīng)該是完全等價(jià)的吧？

2009-03-25 21:10 | pgw

# re: 我的SICP習(xí)題答案（1.24~1.28）回復(fù) 更多評(píng)論

@pgw

好吧。。我錯(cuò)了

2009-03-25 21:42 | pgw

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 我的SICP習(xí)題答案（2.36~2.39）我的SICP習(xí)題答案（2.33~2.35）我的SICP習(xí)題答案（2.27~2.32）我的SICP習(xí)題答案（2.24~2.26）我的SICP習(xí)題答案（2.17~2.23）我的SICP習(xí)題答案（2.01~2.08）我的SICP習(xí)題答案（1.40~1.44）我的SICP習(xí)題答案（1.35~1.39）我的SICP習(xí)題答案（1.34）我的SICP習(xí)題答案（1.29~1.33）

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: 我的SICP習(xí)題答案（1.24~1.28）回復(fù) 更多評(píng)論

# re: 我的SICP習(xí)題答案（1.24~1.28）回復(fù) 更多評(píng)論

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

CG@CPPBLOG

我的SICP習(xí)題答案（1.24~1.28）

評(píng)論

導(dǎo)航

留言簿(5)

隨筆分類(100)

隨筆檔案(76)

文章分類(38)

文章檔案(39)

Others

SICP

Wiki

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

CG@CPPBLOG

我的SICP習(xí)題答案（1.24~1.28）

評(píng)論

# re: 我的SICP習(xí)題答案（1.24~1.28） 回復(fù) 更多評(píng)論

# re: 我的SICP習(xí)題答案（1.24~1.28） 回復(fù) 更多評(píng)論

導(dǎo)航

留言簿(5)

隨筆分類(100)

隨筆檔案(76)

文章分類(38)

文章檔案(39)

Others

SICP

Wiki

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

# re: 我的SICP習(xí)題答案（1.24~1.28）回復(fù) 更多評(píng)論

# re: 我的SICP習(xí)題答案（1.24~1.28）回復(fù) 更多評(píng)論