SICPを読む(15) 1.2.6 素数の探索

scheme

いにしえの古代より素数の探索が行われてきた。僕も先人に習い、素数の探索を行おうと思う。

力ずくで

まずは、一番単純な素数の探索方法。それは・・・割り切れるかどうか1個づつ試す。

終端は\sqrt{n}なので、探索回数も\sqrt{n}という力業。

; 平方
(define (square x) (* x x))

; 割り切れるかどうか
(define (divides? a b)
 (= (remainder b a) 0))

; 素数を見つける
(define (find-divisor n test-divisor)
 (cond ((> (square test-divisor) n) n)
       ((divides? test-divisor n) test-divisor)
       (else (find-divisor n (+ test-divisor 1)))))

; 最小除数を返す
(define (smalltest-divisor n)
 (find-divisor n 2))

; 素数かどうか
(define (prime? n)
 (= n (smalltest-divisor n)))

メルセンヌ数 - Wikipediaを活用することにした。

(trace find-divisor)
(prime? #b1) ; 2
(prime? #b11) ; 3
(prime? #b111) ; 7
(prime? #b11111) ; 31
(prime? #b1111111) ; 127

2進数で1が並んだ形には素数が多い。

127を調べるのに、11回。力ずくで計算しても、案外少ない手数で調べられる。

確率的アルゴリズムで

フェルマーの小定理 - Wikipedia

むむ・・・

フェルマーの小定理

pを素数とし、aをpの倍数でない整数（aとpは互いに素）とするときに、

a^{n-1} \equiv 1 \pmod{p}

すなわち、aをp-1 乗したものをpで割ったあまりは1になるというもの。

記号がわからん。\equiv←コレ

もう一個。(mod p)←コレ

  • 余りの算数
    • わかりやすい。上のページも必見。
    • あまり。

もう一度読むと。

「aをp-1 乗したものをpで割ったあまりは1になるというもの」

ほうほう。謎が解けた。

フェルマーテスト

フェルマーテストは、 フェルマーの小定理の対偶を用いて確率的素数判定を行うアルゴリズムである。


では、コーディングに入ろう。

; フェルマーの小定理から余りを求める(余剰の余り)
(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))))) ; 1 と n - 1の間の乱数を得る

; times回テストを行う
(define (fast-prime? n times)
 (cond ((= times 0) #t)
       ((fermat-test n) (fast-prime? n (- times 1)))
       (else #f)))

(trace expmod)
(fast-prime? #b1111111 10) ; 127 だと非常に無駄が多い (13 * 10)
(fast-prime? 13466917 10)  ; 数値が大きいと無駄が少なくなる(37 * 10)
  • いきなり逐次平方を使っているので、混乱した。
  • 小さな素数の場合、力業を使った方がずっと少ない。
  • 大きな素数(暗合等)に利用する場合は、非常に有効であることが確認できた。
  • timesにどれくらいの値を入れると正確になるのかイマイチわかってない。

素数のリンク。

素数って深い。