Java BigInteger простые числа

Question

Я пытаюсь сгенерировать случайное простое число типа BigInteger, которое находится между минимальным и максимальным значением, которое я предоставляю.

Мне известно о BigInteger.probablePrime(int bitlength, random), но я не уверен, каким образом или даже, если длина битов преобразуется в значение max/min выходного простого числа.

Спасибо Steven1350

Answer 1

BigInteger.probablePrime(bitLength, random) собирается вернуть (вероятное) простое число указанной длины в битах. Это означает максимальное значение 2^ длина волны - 1 и минимальное значение 2^(длина волны - 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);

Плотность простых чисел в целом достаточно высока, в основном она равна 1 в log(x), поэтому вам не нужно повторять слишком много раз, чтобы найти простое число. (просто в качестве примера: для чисел около 10²³ одно из каждых 52 целых чисел в среднем представляет собой простое число. Приведенный выше код беспокоит только 2 из каждых 6 чисел, так что в конечном итоге вы будете в среднем 17 раз за цифры около 10^23.)

Просто убедитесь, что у вас есть хороший тест на первичность, и у Java BigInteger есть такой.

В качестве упражнения для читателя, расширьте вышеупомянутую функцию, чтобы она отфильтровывала больше составных чисел заранее, используя 30k + x (по модулю 30, есть 22 модуля, которые всегда составные, только 8 оставшихся, которые могут быть простыми), или 210k + х.

редактировать: см. также патент США № 7149763 (OMFG!!!)