SICP 読み (11)

scheme SICP

なかなか前に進まない。一歩進んで二歩下がった挙句に (以下略

Fermat テストについて (続)

  • ある二つの数を同一の数 n で割った時、同じ剰余を持てば、_n を法として合同_という
  • 数 a を n で割った剰余を_ n を法とした a の剰余_とか_ n を法とした a _という

上記を踏まえ、以下。

n を素数、a を n より小さい正の任意の整数とすると、a の n 乗は n を法として a と合同である。

となる、と。まだ意味分からんな。
n が素数だとしたら a の n 乗を n で割った剰余と a を n で割った剰余は等しい、という事か。それを踏まえて以下のコードを見るに

(define (expmod base exp m)
 (cond ((= exp 0) 1)
       ((even? exp)
        (remainder (square (expmod base (/ exp 2) m)) m))
       (else
        (remainder (* base (expmod base (- exp 1) m)) m))))

上記は、SICP によると

ある数のべき乗の別の数を法とした剰余を計算する手続き

とある。scheme のコードは目に慣れた、と思っていたんですが、上記コードは理解に時間がかかっております。頭弱いよう。

つづき

問題 1.25 にもあるんですが、何故に (expmod 3 5 5) が (remainder (* 3 3 3 3 3) 5) になってないんだろう。

置き換えモデルで試してみた。

(expmod 3 5 5)
(remainder (* 3 (expmod 3 4 5)) 5)
(remainder (* 3 (remainder (square (expmod 3 2 5)) 5)) 5)
(remainder (* 3 (remainder (square (remainder (square (expmod 3 1 5)) 5)) 5)) 5)
(remainder (* 3 (remainder (square (remainder (square (remainder (* 3 (expmod 3 0 5)) 5)) 5)) 5)) 5)
(remainder (* 3 (remainder (square (remainder (square (remainder (* 3 1) 5)) 5)) 5)) 5)
(remainder (* 3 (remainder (square (remainder (square (remainder 3 5)) 5)) 5)) 5)
(remainder (* 3 (remainder (square (remainder (square 3) 5)) 5)) 5)
(remainder (* 3 (remainder (square (remainder 9 5)) 5)) 5)
(remainder (* 3 (remainder (square 4) 5)) 5)
(remainder (* 3 (remainder 16 5)) 5)
(remainder (* 3 1) 5)
(remainder 3 5)
3

うーん。分かりにくいなぁ。たしかに書いてある通りの処理をしてはいるんですが、何故に_別の数を法とした剰余_を計算する手続きが必要なんでしょうか。

上記手続きを式にしてみるか。

;; 3 ^ 5 を 5 で割った剰余の取得
(expmod 3 5 5) 

;; 3 ^ 4 を 5 で割った剰余に 3 を掛けた値を 5 で割った剰余の取得
(remainder (* 3 (expmod 3 4 5)) 5)

ぬ。ってコトは (expmod 3 4 5) と (remainder (square (expmod 3 2 5)) 5) は同値になるのか。なんでだろ。
3 の二乗を 5 で割った剰余は 4。4 ^ 2 は 16 で 5 で割った剰余は 1 か。

((* 3 3 3 3 3) modulo 5) = ((* 3 ((* 3 3 3 3) modulo 5)) modulo 5)

で

((* 3 3 3 3) modulo 5) = ((square ((* 3 3) modulo 5)) modulo 5)

になるんか。ちなみに modulo 演算子 の左辺を比べてみると

(* 3 3 3 3 3) ;; => 243 
(* 3 (remainder (* 3 3 3 3) 5)) ;; => 3

両方ともに 5 で割った剰余は 3 (当たり前
あるいは

(* 3 3 3 3) ;; => 81
(square (remainder (* 3 3) 5)) ;; => 16

これも両方 5 で割った剰余は 1 (当たり前
もう少し見てみよう。

((* 3 3) modulo 5) = ((square (3 modulo 5)) modulo 5)

これは分かり易い。modulo 演算子の左辺は同一の値。

トレイスもかけてみた。

guile> (expmod2 3 5 5)
[expmod2 3 5 5]
|  [fast-expt 3 5]
|  |  [fast-expt 3 4]
|  |  |  [fast-expt 3 2]
|  |  |  |  [fast-expt 3 1]
|  |  |  |  |  [fast-expt 3 0]
|  |  |  |  |  1
|  |  |  |  3
|  |  |  9
|  |  81
|  243
3
3
guile> (expmod 3 5 5)
[expmod 3 5 5]
|  [expmod 3 4 5]
|  |  [expmod 3 2 5]
|  |  |  [expmod 3 1 5]
|  |  |  |  [expmod 3 0 5]
|  |  |  |  1
|  |  |  3
|  |  4
|  1
3
3

くりかえし、というか再帰呼び出しが一回多いな。戻り値の桁も少ない。ってか、この位の感想しかないあたり、痴呆気味だよ。

ただ、不思議なのは

(square (remainder (* 3 3) 5))

を 5 で割った剰余が

(* 3 3 3 3)

を 5 で割った剰余と同じ、な事です。何か法則みたいなナニがあるのか。

1.25 は答えに辿り着くまで、相当遠いな。

追記

微妙な記述を修正。しかしワケ分かんねぇ。