Numeri primi Java BigInteger

Question

Sto cercando di generare un numero primo casuale di tipo BigInteger, compreso tra un valore minimo e massimo che fornisco.

Sono a conoscenza di BigInteger.probablePrime (int bitlength, random), ma non sono sicuro di come o anche se la lunghezza di bit si traduce in un valore max / min del primo emesso.

Grazie, Steven1350

Answer 1

BigInteger.probablePrime (bitLength, random) restituirà un primo (probabile) della lunghezza di bit specificata. Ciò si traduce in un valore massimo di 2 ^ lunghezza bit - 1 e un minimo di 2 ^ (lunghezza bit - 1). Per quanto lo odi come una risposta, è probabilmente la soluzione migliore a meno che tu non voglia iniziare ad approfondire la teoria dei numeri.

Quello che dovresti fare è capire le lunghezze dei bit richieste dal tuo intervallo, quindi passarle a probablePrime () fino a quando non ottieni un numero primo nell'intervallo giusto.

Answer 2

La risposta di jprete va bene se il rapporto max / min non è vicino a 1.

Se hai un raggio ristretto, la tua scommessa migliore è probabilmente quella di fare qualcosa del tipo:

// 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 di primes è abbastanza alto nel complesso, è praticamente 1 nel log (x), quindi non dovresti ripetere troppe volte per trovare un numero primo. (solo come esempio: per numeri intorno a 10 ²³ , uno su 52 numeri interi in media è un numero primo. Il codice sopra infastidisce solo con 2 numeri su 6, quindi finiresti eseguendo il ciclo in media di 17 volte per numeri intorno a 10 ²³ .)

Assicurati di avere un buon test di primalità e Java BigInteger ne ha uno.

Come esercizio per il lettore, estendi la funzione sopra in modo da filtrare più numeri compositi in anticipo usando 30k + x (modulo 30, ci sono 22 moduli che sono sempre composti, solo 8 rimanenti che potrebbero essere primi) o 210k + x.

modifica: vedi anche brevetto USA n. 7149763 (OMFG !!!)