SICPを読む(38) 問題 2.5 べき乗の逆算。

問題を読んでも問題の意味が掴めなかったので、答えを見た。答えを見てもさっぱりわからなかったので放置していたけど、もう一度答えを見ていたらやっと掴めた!!

まずは、consの定義。

(define (cons a b)
  (* (expt 2 a) (expt 3 b)))

consを実行してみると、

(cons 2 3) ; (* 4 27) -> 108

4は2で割り切れる。27は3で割り切れる。2と3は素数なので掛け合わせても復号化が可能な暗号が出来上がる。

やるべき事は、べき乗の逆算をすればいいということがわかる。

プログラムを見てみる。変数は基数baseのn乗とした。

(define (cons a b)
  (* (expt 2 a) (expt 3 b)))

(define (pair z base)
  (define (iter z n)
    (if (= (remainder z base) 0)  ; 割り切れなくなるまで
        (iter (/ z base) (+ n 1)) ; zをbaseで割りつづける
        n))                       ; 割り切れなかったらnを返す
  (iter z 0))

(define (car z)
  (pair z 2))
(define (cdr z)
  (pair z 3))

(car (cons 2 3)) ; 2

問題は、carを求める場合、2のn乗かを求めなければならない点。

計算回数nにメモしておいて、割り切れなくなったら計算回数nを返すようにする。

iterのtraceを見るとよくわかる。

|(iter 108 0)
|(iter 54 1)
|(iter 27 2)
|2
2

27が出て割り切れなくなったら、計算回数2を返している。

これで元の結果が出る。

ここからわかることは、

(define (cons a b)
  (* (expt 3 a) (expt 5 b)))

と素数であれば暗号化、復号化が可能である。と定義出来る。

素数ってすげぇぇぇ!!

ようやくわかったよ(涙

追記

素数じゃなくても、互いに素であれば大丈夫。

(define (cons a b)
  (* (expt 4 a) (expt 9 b)))

(gcd 4 9) ; 1 ← 互いに素

これでもオケ。