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 (* base (expmod base (- exp 1) m))
                          m))))

(define (fermat-test n)
        (define (try-it a)
                (= (expmod a n n) a))
        (try-it (+ 1 (random (- n 1)))))

このコードの expmod が難しい。
後で参照する度に「何やってるんだっけ？」って話になって、時間をロスしてしまう。

Fermat の小定理を数式にする

まずは、素直に数式にする。
$a^n \bmod n = a \bmod n$ --- (1)
a は n より小さい正の任意の整数であるから
$a \bmod n = a$ --- (2)
よって、(2)を(1)の右辺に当てはめ
$a^n \bmod n = a$ --- (3)
になる。

問題点

(3)の左辺は計算し求める必要があるが、素直に $a^n$ を算出した後に n で
割った剰余を求めようとすると、n が大きい時に計算量がとんでもないことになる。
例えば n が 100000 である時、a が取り得る最大数は 99999 だが、
$a^n$ つまり $99999^{100000}$ は 50 万桁にもなってしまう。
それに n で割った剰余を求めないといけないのだ。
もっと大きな数の素数性を調べる時は、これが指数的に増えるのだから、
いくらコンピュータと言えども処理が追いつかない*1。

どうするか

解決に必要な情報は、本にすべて提示されている。

武器その 1 「逐次平方」

P.25 では、逐次平方を次のように定義した。

n は 0: $b^{n} = 1$
n は偶数: $b^{n} = (b^{n/2})^{2}$
n は奇数: $b^{n} = b \cdot b^{n-1}$

武器その 2 「剰余演算」

脚注 46 より抜粋 - P.29
任意の整数 x, y と m について， $x \times y \bmod m$ の剰余は， $x \bmod m$ と $y \bmod m$ の剰余を別々に計算し，その結果を掛け合わせ，更に積の $\bmod m$ の剰余をとればよい

これにより、次のような式が成り立つ。
[tex:(x \times y) \bmod m = *2 \bmod m] --- (4)

必要な武器は以上。

解決法

(3)を逐次平方を用いて表す。
またその時に、(2)及び(4)も用いて式を展開する。
これが解決法で且つ、expmod の行っていることである*3。

n は 0: $a^{n} \bmod n = 1$
n は偶数: $\begin{eqnarray}a^{n} \bmod n &=& (a^{\frac{n}{2}})^{2} \bmod n \\ &=& (a^{\frac{n}{2}} \bmod n)^{2} \bmod n\end{eqnarray}$
n は奇数: [tex:\begin{eqnarray}a^{n} \bmod n &=& (a \cdot a^{n-1}) \bmod n \\ &=& *4 \bmod n \\ &=& (a \cdot (a^{n-1} \bmod n)) \bmod n \end{eqnarray}]

これにより、なるべく小さい数であるうちに剰余を出すことが出来るので、前述のような問題は起きなくなる。
また、逐次平方を使うので、対数ステップで処理できる。

*1:問題 1.25 は、まさにこれを行っている

*2:x \bmod m) \cdot (y \bmod m

*3:ちなみに fermat-test では、a は n より小さい正の任意を生成し、(3)をテストしている

*4:a \bmod n) \cdot (a^{n-1} \bmod n