A Fast Monte-Carlo Test for Primality

Let n be an odd integer. Take a random number a from a uniform distribution on the set \1, 2, , n -1\. If a and n are relatively prime, compute the residue a^ (n - 1) /2 (n), where - 1 1 or decide that n is composite. Obviously, if n is prime, the decision made will be correct. We will show below, that for composite n the probability of an incorrect decision is 1 / 2. The number of multiprecision operations needed for the whole procedure is < 6 ₂ n. m-fold repetition using independent random numbers yields a Monte-Carlo test for primality with error probabilities 0 (if n is prime) and < 2^-m (if n is composite) and with multiprecision arithmetic cost < 6m ₂ n.