Given below is a Monte-Carlo (randomized) algorithm isPrime for testing primality of odd integers greater than 4. Will this algorithm ever return true for n = 15 (i.e., will it ever incorrectly report that 15 is a prime number)? For n = 15 and ALL possible values of b between 2 and 13, trace this algorithm by hand or write a program (in any language) that tests the algorithm. Also, what does this algorithm return for n = 27 and b = 18? Your homework submission must include your hand traces or your source code and output for all of the specified test cases.

isPrime(n):

// Test n for primality

b = RANDOM(2, n-2);

if (isStronglyPseudoprime(n, b))

return true;

else return false;

isStronglyPseudoprime(n, b): let s be a positive integer and let t be a positive odd integer such that n-1 = 2s * t; if ((bt 1) mod n == 0) or (there exists i such that 0 i < s and (b(2^i) * t + 1) mod n == 0) return true; else return false;