Primality Testing
There is another way the Jacobi and Legendre symbols differ. If the Euler criterion formula is used modulo a composite number, the result may or may not be the value of the Jacobi symbol.
So if it's not known whether a number n is prime or composite, we can pick a random number a, calculate the Jacobi symbol and compare it with Euler's formula; if they differ modulo n, then n is composite; if they're the same modulo n for many different values of a, then n is "probably prime".
This is the basis for the probabilistic Solovay–Strassen primality test and its refinement the Miller–Rabin primality test.
Read more about this topic: Jacobi Symbol
Famous quotes containing the word testing:
“Traditional scientific method has always been at the very best 20-20 hindsight. It’s good for seeing where you’ve been. It’s good for testing the truth of what you think you know, but it can’t tell you where you ought to go.”
—Robert M. Pirsig (b. 1928)