巨大素数の生成

暗号の話とかをやっていると巨大な素数がわりとよくでてきますが、いざ実装しようとしたときに、巨大な素数ってどうやって作るのが良いんでしょうか。
もちろんエラトステネスの篩で扱える範囲は軽く超えます。となれば確率的な素数判定を利用するんでしょう。

どうも、単にランダムな巨大整数を取ってきて素数判定にかけ、合格するまでそれを繰り返すという方法が取られることが多いようなのですが、「ランダムに取ってくる」というあたりに工夫の余地がありそうです。1の位が偶数でも5でもなく、各位の数の和が3の倍数でなく…みたいなアドホックな性質を持つ特定のビット数の乱数生成をやったりできるのかな、と想像。

なんでこんな記事を書いたかというと、JavaのBigIntegerのライブラリを眺めていたら、BigInteger.probablePrime などというものを見つけたからです。これ見ると、乱数ジェネレータが別売りなので特化させることができそうなんですよね。