java - JavaBigInteger素数

Question

BigInteger型の乱数を生成しようとしています。これは、指定した最小値と最大値の間にあります。

BigInteger.probablePrime（int bitlength、random）を知っていますが、ビット長が出力された素数の最大/最小値にどのように変換されるか、または変換されるかどうかはわかりません。

ありがとう、Steven1350

Answer 1

比率max/minが1に近くない場合、jpreteの答えは問題ありません。

範囲が狭い場合、最善の策はおそらく次のようなことをすることです。

// this is pseudocode:
//
// round min down to multiple of 6, max up to multiple of 6
min6 = floor(min/6);
max6 = ceil(max/6);
maybePrimeModuli = [1,5];
do 
{
   b = generateRandom(maybePrimeModuli.length);
   // generate a random offset modulo 6 which could be prime
   x = 6*(min6 + generateRandom(max6-min6)) + b;
   // generate a random number which is congruent to b modulo 6
   // from 6*min6 to 6*max6-1
   // (of the form 6k+1 or 6k+5)

   // the other choices 6k, 6k+2, 6k+3, 6k+4 are composite 
} while not isProbablePrime(x);

素数の密度は全体的にかなり高く、基本的にlog（x）で1であるため、素数を見つけるために何度も繰り返す必要はありません。（例として、10 ²³前後の数値の場合、平均して52の整数ごとに1つが素数です。上記のコードは、6つの数値のうち2つだけを気にするため、平均で17回ループすることになります。 10 ²³前後の数字。）

素数性テストが適切であることを確認してください。JavaBigIntegerには素数性テストがあります。

読者の演習として、上記の関数を拡張して、30k + x（モジュロ30、常にコンポジットである22のモジュラスがあり、プライムになる可能性がある残りの8つのみ）または210kを使用して、より多くの合成数を事前にフィルターで除外します。 +x。

編集：米国特許＃7149763（OMFG !!!）も参照してください。

Answer 2

BigInteger.probablePrime(bitLength, random)指定されたビット長の（可能性のある）素数を返します。これは、最大値が2 ^ bitlength -1、最小値が2 ^（bitlength -1）になります。私が答えとしてそれを嫌うのと同じくらい、あなたが数論を掘り下げ始めたいのでなければ、それはおそらくあなたの最善の策です。

あなたがしなければならないことは、あなたの範囲が要求するビット長を把握し、そしてprobablePrime()あなたが正しい範囲にある素数を取り戻すまでそれらを渡すことです。