Miller-Rabin法を使った素数判定アルゴリズム

MillerRabinPrimalityTest.fsx

/// Miller-Rabin法を使った素数判定
let isPrime n =
    let modPow x k m =
        let rec loop result x k m =
            if k = 0L then result else
            let result = if k &&& 1L = 0L then result else result * x % m
            let k = k / 2L
            let x = x * x % m
            loop result x k m
        loop 1L x k m
    if n < 2 then false else
    let nL = int64 n
    let d, s = (n - 1, 0) |> Seq.unfold (fun (d, s) -> Some((d, s), (d / 2, s + 1))) |> Seq.find (fun (d, _) -> d % 2 <> 0)
    let rec check = function
        | [] -> true
        | a::_ when a = nL -> true
        | a::rest when modPow a (int64 d) nL = 1L -> check rest
        | a::rest when Seq.init s id |> Seq.exists (fun r -> modPow a (int64 d * (1L <<< r)) nL = nL - 1L) -> check rest
        | _ -> false
    check [2L; 7L; 61L]