SICP 問題 1.25 （冪剰余と普通の剰余の違い)

お仕事が忙し過ぎて体がもたん。。やる気が。。

【問題】
Alyssa P. Hacker は expmod を書くのに多くの余分なことをやったと不満で、結局ベキ乗計算法は知っているから、

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

と単純に書けるはずだと言った。
これは正しいか。
これも高速素数テストと同じに使えるか。

【解答】
さて、この問題。
素数性のテストでさんざん俺が困ったやつですよ。
冪剰余を知らなくて、moduloの展開せずにフツーに書いたらこうなった。

計算して得られる結果は正しいはず。
どういう意味で「高速素数テストと同じに使えるか」と問われると、
「冪剰余」のアルゴリズムがあるぐらいだから問題の計算方法だと遅いんだろうなぁ。
確認めんどい。。