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:
“Generalization, especially risky generalization, is one of the chief methods by which knowledge proceeds... Safe generalizations are usually rather boring. Delete that “usually rather.” Safe generalizations are quite boring.”
—Joseph Epstein (b. 1937)