巨大な数が素数であるかどうかの判定は大変に難しいのです。
素数判定法として有名なところではフェルマーテストというものがあります。
フェルマーの小定理はpが素数でaとpが互いに素であるとき
a^(p-1) mod p = 1
が成立する。故にこれに合格できるなら素数、だったらいいんですけどね……。
このテストをすり抜けてしまう擬素数というものがあります。
特に有名なのがカーマイケル数ですね。一番小さいカーマイケル数は561、3x11x17な合成数です。
で、このカーマイケル数のようなフェルマーテストを通過してしまう擬素数をどうにかしようというのがミラー・ラビンテストです。
大雑把な説明としては拡張リーマン予想が正しければ、の前提でテストを作ったのがゲイリー・ミラー、その拡張リーマン予想が正しい、という前提を外して確率で扱うように改良したのがマイケル・ラビン。なのでミラー・ラビンテスト、です。
で、テストで誤判定が一回あたり1/4とありますが、これは最悪値で殆どの場合は1/10以下です。
ただそれでも誤判定は0にならないので「確率的素数」となるわけです。
逆にこの「拡張リーマン予想が正しい」前提ならば確率的素数ではなく確定で素数と判定できます。ただし桁数が増えるとテスト回数が増えて大変なことになります。
作中で出てきたRSA1024ビットキーに必要な512ビット素数だとおおよそ25万回です。
近年使われる4096ビットキーの場合、2048ビットの素数が必要なのでなんと400万回必要です。やったね（？）
ちなみに拡張リーマン予想の親戚であるリーマン予想ってミレニアム懸賞問題なんですよね。ポアンカレ予想以外解決していないアレです、アレ。
正しいかどうかわかんないし、計算も多いし、僕はミラー・ラビンテストの確率的素数でいいです、はい。