The Miller-Rabin Test: Probabilistic Primality Testing

The Royal Mint of Prime City must verify that the numbers stamped on coins are prime. For small numbers, trial division works. But for numbers up to 10^18, a faster method is needed. The Miller-Rabin primality test is a probabilistic test that can determine primality with high confidence in O(k * log^2 n) time. "Write n-1 = 2^s * d where d is odd," the Mint Master explains. "For each witness a, compute a^d mod n. If it's 1 or n-1, the test passes. Otherwise, square repeatedly up to s-1 times. If we never reach n-1, n is composite. With enough witnesses, we can be certain." Given an integer n, determine if n is prime using the Miller-Rabin test with deterministic witnesses for n < 10^18. Output "prime" or "composite". Constraints: 2 <= n <= 10^18 Input: 17 Output: prime Input: 15 Output: composite