Números primos de Java BigInteger

Question

Estoy tratando de generar un número primo aleatorio del tipo BigInteger, es decir, entre un valor mínimo y máximo que proporciono.

Soy consciente de BigInteger.probablePrime (int bitlength, random), pero no estoy seguro de cómo o incluso si la longitud de bit se traduce en un valor máximo / mínimo del primo emitido.

Gracias, Steven1350

Answer 1

BigInteger.probablePrime (bitLength, random) devolverá una prima (probable) de la longitud de bit especificada. Eso se traduce en un valor máximo de 2 ^ bitlength - 1 y un mínimo de 2 ^ (bitlength - 1). Por mucho que lo odie como respuesta, probablemente sea su mejor apuesta a menos que quiera comenzar a profundizar en la teoría de los números.

Lo que tendrías que hacer es averiguar las longitudes de bits que requiere tu rango, luego pasarlas a probablePrime () hasta que obtengas un prime que esté en el rango correcto.

Answer 2

La respuesta de jprete está bien si su relación max / min no está cerca de 1.

Si tiene un rango estrecho, su mejor opción es probablemente hacer algo como lo siguiente:

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

La densidad de primos es bastante alto en general, básicamente es 1 en log (x), por lo que no debería tener que repetir muchas veces para encontrar un número primo. (como ejemplo: para los números alrededor de 10 ²³ , uno de cada 52 enteros en promedio es un número primo. El código anterior solo molesta con 2 de cada 6 números, por lo que terminará bucle un promedio de 17 veces para números alrededor de 10 ²³ .)

Solo asegúrese de tener una buena prueba de primalidad, y Java BigInteger la tiene.

Como ejercicio para el lector, extienda la función anterior para que filtre más números compuestos antes de tiempo usando 30k + x (módulo 30, hay 22 módulos que siempre son compuestos, solo 8 restantes podrían ser primos) , o 210k + x.

editar: ver también Patente de EE. UU. # 7149763 (OMFG !!!)