Java BigInteger простые числа - PullRequest
Новая
       32

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

7 голосов
/ 26 ноября 2009

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

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

Спасибо, Steven1350

Ответы [ 2 ]

3 голосов
/ 26 ноября 2009

jprete ответит хорошо, если ваше соотношение макс / мин не близко к 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 23 одно из каждых 52 целых чисел в среднем является простым числом. Приведенный выше код беспокоит только 2 из каждых 6 чисел, так что вы в конечном итоге зацикливаетесь в среднем 17 раз для чисел около 10 23 .)

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

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

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

2 голосов
/ 26 ноября 2009

BigInteger.probablePrime(bitLength, random) будет возвращать (вероятное) простое число указанной длины в битах. Это означает максимальное значение 2 ^ длина волны - 1 и минимальное значение 2 ^ (длина волны - 1). Как бы я ни ненавидел это как ответ, это, вероятно, ваш лучший выбор, если вы не хотите углубляться в теорию чисел.

То, что вам нужно сделать, это выяснить длину в битах, к которой обращается ваш диапазон, а затем передать их в probablePrime(), пока не получите простое число, которое находится в нужном диапазоне.

...