Números primos de Java BigInteger
-
05-07-2019 - |
Pregunta
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
Solución
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.
Otros consejos
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 23 , 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 23 .)
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 !!!)