Números primos BigInteger de Java

Question

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

Conozco BigInteger.probablePrime (longitud de bit int, aleatorio), 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 de salida.

Gracias, Steven1350

Answer 1

BigInteger.probablePrime(bitLength, random) va a devolver un primer (probable) de la longitud de bits especificado. 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, es probablemente tu mejor opción a menos que quieras comenzar a profundizar en la teoría de números.

Lo que tendría que hacer es calcular las longitudes de bits que requiere su rango, y luego pasarlas al probablePrime() hasta que obtenga un primo que esté en el rango correcto. respuesta

Answer 2

de jprete está bien si su relación de máx/mín no está cerca de 1.

Si usted tiene un rango estrecho, lo mejor es, probablemente, sólo para 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); 

El density of primes 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. (solo como un ejemplo: para números alrededor de 10 , uno de cada 52 números 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ía bucleando un promedio de 17 veces para números alrededor de 10 .)

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

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

edición: véase también US patent #7149763 (OMFG !!!)