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

Question

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

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

Спасибо, Стивен1350

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

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

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

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

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