Algoritmo più veloce per scoprire se un BigInteger è un numero primo o no?

Question

Sto scrivendo un metodo che rileva se un BigInteger è primo o no. Ho usato il seguente codice/algoritmo per verificare se un dato numero è primo o meno. Ma questo è estremamente lento e richiede molto tempo se un numero indica dieci cifre.

public boolean returnPrime(BigInteger testNumber){ 
     int divisorCounter=1; 
     BigInteger index,i ; 


     for (index= new BigInteger("2"); index.compareTo(testNumber) !=1; index=index.add(new BigInteger("1"))){ 


      System.out.println(index); 
      for(i= new BigInteger("2"); i.compareTo(index) != 1; i=i.add(new BigInteger("1"))){ 
      if((testNumber.mod(i).equals(BigInteger.ZERO))){ 
      divisorCounter++; 

      } 

      if(divisorCounter>2){ 
      return false; 
      } 

      }  

     } 
    return true; 

    } 

C'è qualche algoritmo migliore per lavorare con il numero primo di BigInteger? Non sono riuscito a trovare una domanda relativa a questo in StackOverflow. Se hai trovato questa domanda per favore fammelo sapere o se hai un'idea su come risolvere allora le tue idee sono molto apprezzate.

Answer 1

Ecco una versione ottimizzata utilizzando il test solo fino a sqrt (n) e utilizzando il test di Miller-Rabin (come di risposta di Joni):

public boolean returnPrime(BigInteger number) { 
    //check via BigInteger.isProbablePrime(certainty) 
    if (!number.isProbablePrime(5)) 
     return false; 

    //check if even 
    BigInteger two = new BigInteger("2"); 
    if (!two.equals(number) && BigInteger.ZERO.equals(number.mod(two))) 
     return false; 

    //find divisor if any from 3 to 'number' 
    for (BigInteger i = new BigInteger("3"); i.multiply(i).compareTo(number) < 1; i = i.add(two)) { //start from 3, 5, etc. the odd number, and look for a divisor if any 
     if (BigInteger.ZERO.equals(number.mod(i))) //check if 'i' is divisor of 'number' 
      return false; 
    } 
    return true; 
} 

Answer 2

Verificare se il numero intero è un "primo probabile". Se non lo sei sai per certo che è composito ed eviti la fattorizzazione lenta.

if (!testNumber.isProbablePrime(5)) return false; 

Inoltre è solo bisogno di fare divisioni di prova solo fino alla radice quadrata di testNumber. Se K è composto, si sa che il suo fattore primo minimo deve essere al massimo sqrt (K).

Answer 3

Alcuni altri semplici miglioramenti consisterebbero nel limitare il numero di possibili numeri a soli due numeri dispari nel ciclo esterno e anche solo per scorrere fino alla radice quadrata di "indice" (o indice/2 se troppo difficile per calcola) nel tuo ciclo interno.