ミラー–ラビン素数判定法

『応用代数学入門―暗号・符号・バーコードの仕組みが分かる』の第7章「フェルマーの定理とオイラーの定理」では素数の判定法としてミラーの判定法、ラビンの確率的判定法が紹介されています。難しくて中々理解できずにいますが、息抜きにRubyのPrime#prime?メソッドはどう実装されているのかを調べてみると、案外、地道な判定法を用いていることが分かりました。

lib/prime.rb

  # Returns true if +self+ is a prime number, else returns false.
  def prime?
    return self >= 2 if self <= 3
    return false if self % 2 == 0 or self % 3 == 0
    (5..(self**0.5).floor).step(6).each do |i|
      if self % i == 0 || self % (i + 2) == 0
        return false
      end
    end
    true
  end

この方法だと、判定したい数が非常に大きいときに効率が悪いような気がします。なぜ、Rubyではミラー–ラビン素数判定法などのアルゴリズムを採用していないのでしょうか?判定ミスがないようにということなのでしょうか?

実験

Ruby 2.3.0のprime?メソッドとミラー–ラビン素数判定法を使った場合の速度にどのくらいの差があるのか実験してみました。

結果

$ ruby prime_test.rb
                 user     system      total        real
Original     0.250000   0.000000   0.250000 (  0.244493)
Miller       0.050000   0.000000   0.050000 (  0.052098)

予想通り、上記のような性能差がありました。dataとして、193428131138340667952988161という巨大な数も判定したかったのですが、ミラー–ラビン素数判定法では判定できたのに対し、オリジナルのprime?メソッドでは時間がかかりすぎて計測することができませんでした。