Haskell

はじめに SICPを読んでたらフェルマーテストについて書いてあって、ほんとにこれ速いのかやってみようと思った話です。 ソースはfermat_test.hsからダウンロード! フェルマーテストとは フェルマーの小定理はご存知ですよね？ $p$を素数のとき、$a$を$p$と互いに素な整数に対して、 $$a ^ p \equiv a \pmod{p}$$ が成り立つ。 これの対偶を考えます。 整数$n$について、$n$と互いに素な整数$a$に対して、 $$ a ^ n \not \equiv a \pmod{n} $$ が成り立つとき、整数$n$は合成数である。 これによって、ある数が素数であることは示せないが合成数であることを速く示すことはできます。 実装 部品を 1 つ 1 つ揃えていきます。 互いに素 最小公倍数を求める関数を考えます。 gcd' :: Integer -> Integer -> Integer gcd' n 0 = n gcd' n m = gcd' m (n `mod` m) これを用いて、 gcd' n m == 1 とすれば$n, m$は互いに素です。 (Haskell には標準で gcd があるのでそれを使っても良い) $a^{n-1} \pmod{n}$を求める いわゆる、$a^7 = a * (a^3)^2 = a * (a * a^2)^2$として計算量をへらすやつを使います。 途中で$\pmod{n}$を挟みます。...