Schnellster Algorithmus, um herauszufinden, ob ein BigInteger eine Primzahl ist oder nicht?

Question

Ich schreibe eine Methode, die erkennt, ob ein BigInteger Prime ist oder nicht. Ich habe den folgenden Code/Algorithmus verwendet, um zu überprüfen, ob eine gegebene Zahl prim ist oder nicht. Aber das ist extrem langsam und dauert lange, wenn eine Zahl beispielsweise 10 Ziffern lang ist.

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; 

    } 

Gibt es bessere Algorithmen für die Arbeit mit der BigInteger-Primzahl? Ich konnte in Stackoverflow keine diesbezügliche Frage finden. Wenn Sie auf eine solche Frage gestoßen sind, lassen Sie es mich bitte wissen oder wenn Sie eine Idee haben, wie Sie diese lösen können, dann werden Ihre Ideen sehr geschätzt.

Answer 1

Hier ist eine optimierte Version Prüfung mit nur bis sqrt (n) und mit dem Miller-Rabin-Test (wie von Joni Antwort):

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

Überprüfen Sie, ob die ganze Zahl a ist „wahrscheinlich Primzahl.“ Wenn Sie nicht sicher sind, dass es zusammengesetzt ist, vermeiden Sie die langsame Faktorisierung.

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

Auch Sie müssen nur bis zur Quadratwurzel testNumber Studie Divisionen nur machen. Wenn K zusammengesetzt ist, wissen Sie, dass der kleinste Primfaktor höchstens sqrt (K) sein muss.

Answer 3

Einige andere einfache Verbesserungen wären, Ihre Menge von möglichen Zahlen auf nur zwei und ungerade Zahlen in Ihrer äußeren Schleife zu begrenzen und auch nur bis zur Quadratwurzel von "index" zu iterieren (oder Index/2 wenn zu schwer zu berechnen) in Ihrer inneren Schleife.