Number-theoretic Methods
Certain number-theoretic methods exist for testing whether a number is prime, such as the Lucas test and Proth's test. These tests typically require factorization of n + 1, n − 1, or a similar quantity, which means that they are not useful for general-purpose primality testing, but they are often quite powerful when the tested number n is known to have a special form.
The Lucas test relies on the fact that the multiplicative order of a number a modulo n is n − 1 for a prime n when a is a primitive root modulo n. If we can show a is primitive for n, we can show n is prime.
Read more about this topic: Primality Test
Famous quotes containing the word methods:
“The ancient bitter opposition to improved methods [of production] on the ancient theory that it more than temporarily deprives men of employment ... has no place in the gospel of American progress.”
—Herbert Hoover (1874–1964)