Bir BigInteger asal sayı olup olmadığını bulmak için en hızlı algoritma?

Question

BigInteger öğesinin öncelikli olup olmadığını algılayan bir yöntem yazıyorum. Verilen bir sayının öncelikli olup olmadığını kontrol etmek için aşağıdaki kodu/algoritmayı kullandım. Ancak bu çok yavaştır ve bir sayı 10 rakam uzunluğundaysa uzun zaman alır.

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; 

    } 

BigInteger asal sayı ile çalışmak için daha iyi algoritmalar var mı? Stackoverflow'ta bununla ilgili bir soru bulamadım. Böyle bir soruyla karşılaşırsanız lütfen bize bildirin ya da nasıl çözeceğiniz konusunda bir fikriniz varsa, fikirleriniz çok takdir edilir.

Answer 1

Burada sadece (n) sqrt kadar testini kullanarak ve (Joni en cevabın gibi) Miller-Rabin testi kullanılarak optimize edilmiş sürümü:

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

Tamsayı bir "olası birincil" olup olmadığını kontrol edin. Eğer bunu bilmiyorsanız, bunun kompozit olduğundan emin olun ve yavaş faktorizasyondan kaçının.

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

Ayrıca yalnızca testNumber kare köküne kadar deneme bölünmeleri yapmanız gerekir. Eğer K kompozit ise, en küçük asal çarpanının en fazla sqrt (K) olması gerektiğini bilirsiniz.

Answer 3

Diğer bazı basit geliştirmeler, olası sayı kümenizi, dış döngüdeki yalnızca iki ve tek sayılarla sınırlamak ve yalnızca "dizin" in kareköküne kadar çoğaltmaktır (veya çok zorsa dizin/2 ise) iç döngünüzde hesaplayın.