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:
“Today so much rebellion is aimless and demoralizing precisely because children have no values to challenge. Teenage rebellion is a testing process in which young people try out various values in order to make them their own. But during those years of trial, error, embarrassment, a child needs family standards to fall back on, reliable habits of thought and feeling that provide security and protection.”
—Neil Kurshan (20th century)