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 ε < n - 2, and the Jacobi symbol δ = (a /n). If ε = 6, decide that n is prime. If either (a,n) > 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 < 6log ₂ 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⁻ᵐ(if n is composite) and with multiprecision arithmetic cost < 6mlog ₂ n.