>> Otherwise, n is definitely composite — no fooling This assertion is false if I understood the test correctly. Take n = 5, a = 2. a ^ ((n - 1) / 2) = 2 ^ (

>> Otherwise, n is definitely composite — no fooling This assertion is false if I understood the test correctly. Take n = 5, a = 2. a ^ ((n - 1) / 2) = 2 ^ ((5 - 1) / 2) = 2 ^ 2 = 4 and 4 mod 5 = 4. Therefore the test will say 5 is composite.