Код Миллера-Рабина длится некоторое время для некоторых чисел. Ошибка?

Question

Я все еще очень начинающий кодер и в духе попыток улучшить свои навыки. Я работаю над программой Java Miller-Rabin, которая, по-видимому, работает по большей части. Однако есть несколько номеров, которые заставляют программу работать непрерывно (по крайней мере, в течение нескольких минут).

Одним из таких чисел является 371. Я знаю его состав (потому что я его посмотрел). Я пробовал работать 371 с использованием теоремы Миллера-Рабина и калькулятора онлайн-модуля, который поддерживает большие целые числа и обнаружил, что я делаю много-много вычислений, поэтому, возможно, мой код в порядке. Я не уверен.

Я очень внимательно прочитал свой код в течение нескольких часов и не нашел никаких отклонений от процесса Миллера-Рабина.

Я надеялся, что свежий набор глаз (или, по крайней мере, более опытных глаз) может помочь.

EDIT: дополнительная информация. Я обнаружил, что он не прошел тестирование 49. Так как это число намного проще вручную вычислить я показал мой работать ниже:

n = 49 
n-1 = 48 

Find values for k and m: 
48/2^0 = 48 
48/2^1 = 24 
48/2^2 = 12 
48/2^3 = 6 
48/2^4 = 3 
49/2^5 = 1.5 ***not an integer, so use k=4*** 

let a = 2 (a can be 2<a<(n-1) ) 
I used 2 

(n-1)/2^k = m 
48/2^4 = 3 *** m = 3 *** 

*** b0 = a^m mod n *** 
*** b(n) = [b(n)]^2 mod n 
b0 = 2^3 mod 49 = 8 
b1 = 8^2 mod 49 = 15 
b2 = 15^2 mod 49 = 29 
b3 = 29^2 mod 49 = 8 
b4 = 8^2 mod 49 = 15 
b5 = 15^2 mod 49 = 29 

И он продолжает выводить Ь = 8,15,29,8,15,29 снова и снова. У меня есть примерно 20 различных значений для «a» и происходит такое же циклическое событие (с разными значениями для b)

Я не знаю, что попробовать дальше. Может ли кто-нибудь мне помочь?

Вот мой код:

/************************************************** 
I based my code on this explanation on youtube. 
I also compared this explanation to others and found them to be consistent 

https://www.youtube.com/watch?v=qfgYfyyBRcY 


Example: 
is 561 prime? 

n = 561 
subtract 1 from candidate number = 560 

while (answer == int) do 
    560/2^1 = 280 
    560/2^2 = 140 
    560/2^3 = 70 
    560/2^4 = 35 
    560/2^5 = 17.5 xxxxxxx use line above 
end while 

k = 4; m = 35 

choose a =2 or 3 or 4 
in this case I chose a = 2 

b = a^m mod candidate 
while (b != 1 or -1) do 
     b = a^m mod n 

     b0 = 2^35 mod 561 = 263 mod 561 
     b1 = 263^2 mod 561 = 166 mod 561 
     b2 = 166^2 mod 561 = 67 mod 561 
     b3 = 67^2 mod 561 = 1 mod 561 

end while 

NOTE: if bo (and only bo) had been either +1 OR -1, 
n would be prime (it was 263, in this example). 
BUT for b1, b2, and so on, +1 implies composite, -1 probable prime. 


***************************************************/ 


import java.lang.*; 
import java.math.BigInteger; 
import java.util.*; 
import java.util.concurrent.TimeUnit; 

public class myMillerRabin{ 


    // these variables are made global so that their creation has no effect on computation time 
    public static BigInteger number;  // number = (n-1) 
    public static BigInteger candidate;  // number being tested 
    public static Scanner scan = new Scanner(System.in); // scanner for keyboard input 
    public static String input;    // reads in candidate as string and passes it to BigInteger 
    public static long endPrimeTest = 0; // timer end 
    public static long startPrimeTest = 0; // timer start 
    public static BigInteger testForNegOne; // tests for eg. 2 mod 3 = 2 = -1 
    public static String _a;    // var to hold value for 'a'. Often 2 is used, but 'a'' can be: 1<a<(candidate-1) 


    public static void main(String[] args){ 
     System.out.println("Enter a candidate number: "); 

     while(isValidInput() == false){  // wait for valid numerical input 
     System.out.println("Error: Enter valid input!"); 
     } 
     if (candidate.longValue() == 2){ // 2 is prime 
      System.out.println("Two is a prime number."); 
     } 
     else if(candidate.longValue() % 2 == 0){ // evens are not prime 
      System.out.println("Number is even, thus it is NOT prime! "); 
     } 
     else{ 
      isProbablePrime(candidate);  // run the test 
      System.out.println("Time taken : " + (endPrimeTest - startPrimeTest) + " nanoseconds"); 
     } 
    } ////////////end main method 



    public static boolean isProbablePrime(BigInteger x){ 
     boolean test1, test2, test3; 
     int twoToK = 0x0001; // 2^0 = 1 
     BigInteger two = new BigInteger("2"); 
     long testCand = x.longValue(); 
     BigInteger aExp, b, modTest; 

     number = x.subtract(BigInteger.ONE); 
     System.out.println("n - 1: " + number);  // used for testing 
     System.out.println("candidate as bigint: " + candidate.intValue()); // used for testing 

     System.out.println("Enter an iterator: 2 is usually fine..."); 
     _a = scan.next(); 
     BigInteger a = new BigInteger(_a); 
     int k = 0; 
     BigInteger m; 
     int _m = 0; 

     startPrimeTest = System.nanoTime(); // start timer 

    // this increases the powers of 2 (starting with 2^0)that are divided by 
    // to obtain the values of k and m 
    while((number.intValue() % twoToK)== 0){ 
      _m = number.intValue()/twoToK; 
      System.out.println("Value of m: " + number.intValue()/twoToK); 
      System.out.println("twoToK : "+ twoToK); 
     twoToK = twoToK << 1; // Bitshift left to increase power of 2 
     k++;  // this final value of will be one more than the one we want 
    } 
    k--;   // obtain value of k 
    System.out.println("k = " + k);  // used for testing 
    System.out.println("m = " + _m); // used for testing 

     String mString = String.valueOf(_m); 
     m = new BigInteger(mString); 

     aExp = a.pow(k); 
     System.out.println("a: " + a + " k: " + k);  // used for testing 
     System.out.println("twoExp: "+ aExp);    // used for testing 

     b = a.modPow(m,candidate); 
     System.out.println("b= "+ b + " mod " + candidate.intValue()); // used for testing 

     // tests for a congruence of -1 eg: 2mod3 = 2 = -1 
     testForNegOne = candidate.subtract(b); 

     System.out.println("Test for neg one: " + testForNegOne.intValue()); // used for testing 

     // if initial test is 1 OR -1, then prime 
     test1 = b.equals(BigInteger.ONE); 
     test2 = b.equals(BigInteger.ONE.negate()); 
     // test for: a^m mod candidate (congruent to) -1 
     test3 = testForNegOne.equals(BigInteger.ONE); 
     System.out.println("Test for +1 initial test: "+test1); // used for testing 
     System.out.println("Test for -1 initial test: "+test2); // used for testing 
     System.out.println("Test for -1 Congruence: " + test3); // used for testing 

     // if test1, 2, or 3 return true for b0, then candidate is a probable prime 
     if(test1 == true || test2 == true || test3 == true){ 
      System.out.println("Candidate is probable prime"); 
      endPrimeTest = System.nanoTime(); 
      return true; 
     } 
     else{ // otherwise keep testing 
      while(!test1 && !test2 && !test3){ 
       b = b.modPow(two, candidate); 
       modTest = candidate.subtract(b); 
       System.out.println("b = " + b + ", -" + modTest); 
       test3 = modTest.equals(BigInteger.ONE); 
       test1 = b.equals(BigInteger.ONE);  // is b == 1 
       test2 = b.negate().equals(BigInteger.ONE); // is b== -1 
       System.out.println("TEst 1: "+ test1); 
       System.out.println("TEst 2:" + test2); 
       System.out.println("Test 3:" + test3); 
       System.out.println("B: " + b); 

      // sleep used for testing purposes 
      /* 
       try { 
        Thread.sleep(1000); 
        } 
        catch(InterruptedException ex) { 
         Thread.currentThread().interrupt(); 
       } 
       */ 
     } 
     if (test1){  // if bn = 1, then the number is composite  
      System.out.println("Implied Composite"); 
      endPrimeTest = System.nanoTime(); 
      return false; 

     } 
     else{   // if test2 or test3 are true, then candidate is a probable prime 
      System.out.println("Probably Prime"); 
      System.out.println("b= "+ b.intValue()); 
      endPrimeTest = System.nanoTime(); 
      return true; 
    } 
    } 
} 

// Method to check input to see if it is a valid integer input 
public static boolean isValidInput(){ 
    try{ 
     input = scan.next(); 
     candidate = new BigInteger(input); 
    } 

    catch (NumberFormatException exception){ 
     //System.out.println("Bad input detected"); // used for debugging 
     return false; 
    } 
    return true; 
} // end isValidInput method 


} 

Answer 1

Согласно Fermat's little theorem мы должны иметь^(р-1) равно 1 по модулю р, если р первична. Поэтому, если мы пишем p-1 = s * 2^k с s нечетным и вычислим a^s, а затем многократно квадратируем результат, мы должны достичь 1 после максимум k квадратилей, если p является простым.

Кроме того, мы можем протестировать последний результат, отличный от 1. Для простого p он должен быть сравним с -1 mod p. Если это что-то другое, мы не только знаем, что р не является простым, но мы даже нашли нетривиальный фактор р (я пишу == для конгруэнтно по модулю р):

x^2 == 1 
x^2 - 1 == 0 
(x + 1) * (x - 1) == 0 

И теперь, так как ни (x + 1), ни (x - 1) не делится на p, но их произведение является нетривиальным фактором p, равным gcd (p, x + 1).