Miller-Rabin code runs for extended period for some numbers. Bug?

Question

I'm still very much a novice coder and in the spirit of trying to improve my skills I'm working on a Miller-Rabin java program that seems to work for the most part. However there are a few numbers that causes the program to run continuously (for many minutes at least).

One such number is 371. I know its composite (because I looked it up). I tried working 371 out using Miller-Rabin theorem and an online modulus calculator that supports big integers and found myself doing many, many calculations, so maybe my code is ok. I'm not sure.

I've gone over my code very carefully for hours and can't find any deviations from the Miller-Rabin process.

I was hoping a fresh set of eyes (or at least more experienced eyes) might help.

EDIT: More Information. I found that it failed testing 49 as well. Since this number is much easier to manually calculate I have shown my working below:

    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

And it keeps outputting b = 8,15,29,8,15,29 over and over. I have it with about 20 different values for 'a' and get the same kind of looping happening ( with different values for b)

I don't know what to try next. Can anyone help me please?

Here is my code:

/**************************************************
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

According to Fermat's little theorem we must have a^(p-1) equals 1 modulo p if p is prime. Therefore, if we write p-1 = s * 2^k with s odd, and calculate a^s and then repeatedly square the result we must reach 1 after at most k squarings if p is prime.

Moreover, we can test the last result that was different from 1. For a prime p it must be congruent to -1 mod p. If it is something else, we do not only know that p is not prime but we have even found a non-trivial factor of p (I write == for congruent mod p):

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

And now, since neither (x + 1) nor (x - 1) is divisible by p but their product is, a non-trivial factor of p is gcd(p, x+1).