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:
“Bourbon’s the only drink. You can take all that champagne stuff and pour it down the English Channel. Well, why wait 80 years before you can drink the stuff? Great vineyards, huge barrels aging forever, poor little old monks running around testing it, just so some woman in Tulsa, Oklahoma can say it tickles her nose.”
—John Michael Hayes (b.1919)