読者です 読者をやめる 読者になる 読者になる

BigIntegerの素数生成メソッドprobablePrimeはどの程度素数生成をミスるのか。

BigIntegerにこんなコンストラクタがあります。

public BigInteger(int bitLength,
int certainty,
Random rnd)

ランダムに生成された (おそらく素数である) 正の BigInteger を、指定したビット数で構築します。
確率を指定する必要がない場合は、このコンストラクタではなく probablePrime メソッドを使用することをお勧めします。

パラメータ:
bitLength - 返される BigInteger のビット長
certainty - 呼び出し側が許容しない確率の尺度。新しい BigInteger が素数である確率は、(1 - 1/2^certainty) より大きい。このインストラクタの実行時間はこのパラメータの値に比例する
rnd - 素数度をテストする候補の選択で使用されるランダムビットのソース

「ランダムに生成された (おそらく素数である) 正の BigInteger」
このおそらく素数ってのが気になります。

中で何をやっているのかとソースを追っていくと「isProbablePrime」という関数でミラーラビン素数判定法を使って素数チェックをしていると分かります。
Source for java.math.BigInteger (GNU Classpath 0.95 Documentation)


ミラーラビン素数判定法についてはWikiでも読みましょう。
ミラー–ラビン素数判定法 - Wikipedia


で、実際どれぐらいミスるのかというのですが「素数である確率は、(1 - 1/2^certainty) より大きい」といわれても実感わかないなーとおもったのでやってみたら
certaintyが1の時でも20万回~50万回に1回ぐらいしか失敗しなかった。。

デフォで使うとcertaintyは100なのでほぼほぼ素数といって問題なさそうですね。