Fermat の小定理 - hattorix0's blog

SICP を読んでいる時に、いつもつまってしまうのでまとめてみる。 概要 Fermat の小定理 - P.28 n を素数，a を n より小さい正の任意の整数とすると，a の n 乗は n を法として a と合同である． そして、それをテストするコードが下記である。 (define (square n) (* n n)) (define (even? n) (= (remainder n 2) 0)) ;; gosh用 (define (random n) (use srfi-27) (random-integer n)) (define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* bas

[kiyo_hiko]

SICP1.2.5のフェルマーテストのexpmodの解説