Java BigIntegerの素数

Question

BigInteger型のランダムな素数、つまり、提供する最小値と最大値の間の乱数を生成しようとしています。

BigInteger.probablePrime（int bitlength、random）は知っていますが、ビット長が出力される素数の最大/最小値に変換される方法や場合でもわかりません。

ありがとう、 Steven1350

Answer 1

BigInteger.probablePrime（bitLength、random）は、指定されたビット長の（推定）プライムを返します。これは、最大値2 ^ bitlength-1と最小値2 ^（bitlength-1）に変換されます。私が答えとしてそれを嫌うのと同じくらい、それはおそらくあなたが数論を掘り下げ始めたくない限りあなたの最善の策です。

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

Answer 2

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

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

// 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);

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

適切な素数性テストがあり、Java BigIntegerにあることを確認してください。

読者向けの演習として、上記の関数を拡張して、30k + xを使用して事前により多くの合成数を除外します（モジュロ30、常に合成される22のモジュラスがあり、残り8つだけが素数になります） 、または210k + x。

編集：米国特許＃7149763 （OMFG !!!）

も参照してください。 >