There is no single best primality test for every input. The right method depends on the size and form of the number, whether one candidate or a whole range is being tested, and whether a probable-prime result is enough or a mathematical proof is required. If only the result for one supported integer is needed, the prime number checker provides the direct prime-or-composite answer. The methods below explain what lies behind that type of computation.
Primality testing is a decision problem
A prime number has exactly two positive divisors, 1 and itself. A composite integer has at least one nontrivial divisor. That creates an asymmetry in testing.
To prove that 221 is composite, it is enough to find one factor: 221 = 13 × 17. To prove that a candidate is prime by direct division, every possible divisor that could matter must be ruled out. Faster primality tests avoid checking divisors one by one.
Trial division: the exact baseline
Trial division is the most direct primality test. For an integer n, test possible divisors and stop if one divides n evenly. There is no need to test all integers below n. If n = a × b is composite, at least one of a or b must be at most √n.
For 97, √97 ≈ 9.85. Testing the prime divisors 2, 3, 5, and 7 is enough. None divides 97, so 97 is prime.
This method is exact and easy to verify, but it scales poorly. The issue becomes clearer when input size is measured in bits. A 60-bit integer can be close to 260, while its square root is close to 230. Even a square-root limit can therefore leave an enormous search space.
Small-prime filtering before a heavier test
Fast implementations usually reject easy composites first. Even numbers above 2 disappear immediately. The same idea applies to divisibility by 3, 5, 7, 11, and other small primes.
This is best viewed as preprocessing, not as a complete large-number strategy. A candidate that survives small-prime division has only shown that it has no small factor. It may still be composite.
Fermat testing and the pseudoprime problem
Fermat’s little theorem gives a tempting primality condition. If p is prime and a is not divisible by p, then:
This leads to the Fermat primality test: choose a base a and check whether the congruence holds for a candidate n. If it fails, n is composite. If it passes, the result is weaker than a proof of primality.
Why 561 matters
The number 561 = 3 × 11 × 17 is composite, yet it satisfies the Fermat congruence for every base coprime to 561. Numbers with this property are called Carmichael numbers.
That example exposes the limitation of a simple Fermat test. A composite can imitate prime behavior under the tested congruence. The test can prove compositeness when it fails, but a pass does not by itself prove primality.
Miller–Rabin: a practical general-purpose test
Miller–Rabin strengthens the Fermat idea by checking more structure in the modular powers. It is one of the standard choices for testing large ordinary integers because each round is fast and a failed round proves compositeness.
Writing n − 1 as a power of two times an odd number
For an odd candidate n > 2, write:
A base a is then used to compute modular powers beginning with ad mod n. The value is repeatedly squared modulo n. For a prime candidate, the sequence must follow a pattern forced by arithmetic modulo a prime.
Witnesses and strong pseudoprimes
If the modular sequence violates the required pattern, the chosen base is a witness to compositeness. The number is definitely composite.
If the candidate passes for that base, it is a strong probable prime to base a. Passing one base is not a universal proof for unbounded integers because some composite numbers are strong pseudoprimes to particular bases.
Why repeated rounds raise confidence
For an odd composite number, at most one quarter of the eligible bases can behave as strong liars. With independently chosen random bases, the usual worst-case bound after k rounds is:
This is a worst-case mathematical bound for the randomized form of the test, not a statement that every implementation chooses bases in the same way. The base-selection rule matters.
Deterministic Miller–Rabin on bounded integer ranges
Miller–Rabin is often described simply as a probabilistic test. That description is incomplete for fixed-width integers.
If the input is restricted to a known upper bound, a fixed set of bases can be chosen so that every composite number in that range is caught. Under those conditions, the procedure is deterministic over that bounded domain.
This is especially useful for 32-bit and 64-bit integer software. An unsigned 64-bit value is at most:
A validated base set for a stated bound can test that bounded domain without random choice. The exact bases are not interchangeable: a set proved for one limit must not be assumed valid beyond that limit.
Baillie–PSW combines two different probable-prime ideas
Baillie–PSW is a hybrid probable-prime test. In its common form, it combines a strong probable-prime test with a Lucas probable-prime test. The two components examine different arithmetic behavior, so the combination is much harder for a composite candidate to pass than a simple one-base screen.
The method is useful for large arbitrary-precision integers when a fast high-confidence result is wanted. It is also a good example of how real number-theory software can combine methods rather than relying on one test alone. A typical pipeline may use small trial divisions first, then a Baillie–PSW test, and then additional Miller–Rabin rounds when more probabilistic assurance is requested.
Baillie–PSW should still be described as a probable-prime test, not as a general primality proof.
AKS and deterministic polynomial-time primality
The AKS primality test, introduced by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, showed that primality can be decided by an unconditional deterministic algorithm whose running time is polynomial in the length of the input.
That result matters because the input length is about log2(n) bits, not n itself. Trial division through √n is therefore poor when measured against bit length, even though the square-root rule is a major improvement over testing every smaller integer.
The polynomial identity behind AKS
AKS grows from a polynomial version of Fermat-style reasoning. One of its central identities is related to:
For prime n, the identity behaves in a controlled way. The full AKS algorithm adds conditions that make the test exact and computationally bounded.
Probable prime and proven prime are different result levels
The word probable has a technical meaning in primality testing. It does not mean that the program is merely guessing. It means the candidate has passed a test whose mathematical guarantee stops short of a general proof under the chosen setup.
| Result | What has been established | Typical evidence |
|---|---|---|
| Composite | The number is definitely not prime. | A nontrivial divisor or compositeness witness |
| Probable prime | The number passed one or more probable-prime tests. | Miller–Rabin or a hybrid probable-prime test |
| Proven prime | The number satisfies an exact primality argument. | Bounded deterministic test or a primality certificate |
Primality proofs and certificates
For very large integers, it can be useful to produce evidence that another program can verify without repeating the original search in the same way. That evidence is called a primality certificate.
Elliptic Curve Primality Proving, usually shortened to ECPP, is one well-known method. It constructs a chain of mathematical conditions involving elliptic curves and smaller prime claims. Verification can be much easier than discovering the certificate.
APR-CL is another exact method used in computational number theory. The practical choice between proof algorithms depends on integer size, available software, and whether a reusable certificate is needed.
Special-form numbers can use special tests
A general-purpose primality test treats an integer mainly as a value. Some numbers have algebraic forms that allow more specialized methods.
Lucas–Lehmer for Mersenne numbers
A Mersenne number has the form:
If p is composite, then Mp is composite, so a Mersenne prime candidate begins with a prime exponent. For an odd prime p, the Lucas–Lehmer test starts with s0 = 4 and repeatedly applies:
After p − 2 terms, Mp is prime exactly when the final residue is 0. This specialized test is highly effective for its intended form, but it is not a general replacement for Miller–Rabin or other tests on arbitrary integers.
A sieve solves a different problem
The Sieve of Eratosthenes and segmented sieve methods are ideal when the goal is to find many primes across a range. A primality test is designed around one candidate.
Use a primality-testing strategy suited to its size and form.
Use a sieve so work can be shared across the whole interval.
Precomputing a sieve can still help repeated primality checks inside a bounded range, but building a huge sieve just to test one very large integer is usually the wrong computational shape for the task.
How the methods behave on different candidates
| Candidate | What happens | Lesson |
|---|---|---|
| 97 | No prime divisor up to √97 divides it. | Trial division is simple and exact for small inputs. |
| 221 | 13 divides it, so 221 = 13 × 17. | One factor is enough to prove compositeness. |
| 561 | It is composite but passes Fermat tests for bases coprime to 561. | Fermat pseudoprimes show why stronger tests are needed. |
| 231 − 1 | It has Mersenne form and is prime. | Special algebraic form can justify a specialized test. |
Prime number testing methods compared
| Method | Result type | Best fit | Main strength | Main limit |
|---|---|---|---|---|
| Trial division | Exact | Small integers | Simple and directly verifiable | Poor scaling as numbers grow |
| Small-prime filtering | Composite filter | Preprocessing | Rejects easy composites cheaply | Does not settle most surviving candidates |
| Fermat test | Probable prime | Basic screening and study | Simple modular test | Carmichael numbers can pass |
| Miller–Rabin | Probable or bounded deterministic | Large general integers | Fast and well suited to repeated testing | Guarantee depends on bases and input bound |
| Baillie–PSW | Probable prime | Arbitrary-precision screening | Combines different arithmetic tests | Not a general proof certificate |
| AKS | Exact | Complexity theory | Deterministic polynomial-time result | Usually slower than practical alternatives |
| ECPP | Exact proof | Large-prime certification | Produces verifiable proof data | More work than a probable-prime screen |
| Lucas–Lehmer | Exact for its target form | Mersenne candidates | Tailored to Mersenne numbers | Not general-purpose |
| Sieve | Exact over a range | Generating many primes | Shares work across an interval | Not ideal for one huge candidate |
Choosing a test by the actual task
The most useful way to compare primality methods is to start with the computation that needs to be done.
Trial division through
√n is usually enough.A sieve is normally a better fit than independent primality tests.
Small-prime filters followed by a proven deterministic strategy for that bounded range work well.
Probable-prime tests such as Miller–Rabin or Baillie–PSW provide fast screening.
Use an exact proving method that can produce or verify a primality certificate.
Check whether a specialized theorem or test applies before using a general method.
Common errors in primality testing
Stopping after one Fermat pass
A passing Fermat congruence does not prove primality. Carmichael numbers are the standard reason.
Calling every Miller–Rabin test probabilistic
The randomized form is probabilistic, but bounded integer ranges can use fixed validated bases to make the result deterministic inside that range.
Using a fixed base set beyond its proven bound
A deterministic guarantee belongs to a specific range. Extending the input range without rechecking the base strategy can turn an exact method back into an unsupported assumption.
Assuming polynomial time means fastest
AKS has a polynomial running-time guarantee in input length. That does not make it the normal speed choice for ordinary prime checking.
Factoring a number when compositeness is the only question
Full factorization can be much harder than proving a number composite. One factor or one valid witness is enough.
Using a sieve for one enormous candidate
Sieves are designed to process ranges. A large isolated integer calls for a primality test instead.
What a reliable prime test should communicate
A useful primality result should make its level of certainty clear. Composite means the candidate has been disproved. Probable prime means it passed a stated testing strategy. Proven prime means an exact argument establishes primality.
The method should also match the number. Small integers favor direct divisibility checks. Fixed-width integers can use bounded deterministic techniques. Large arbitrary-precision candidates benefit from fast probable-prime tests, while proof-oriented work can use certificates. Special forms such as Mersenne numbers may have their own exact tests.
That distinction explains why modern prime testing is not just a faster version of trial division. It uses different mathematical evidence for different computational goals while preserving the same definition of a prime number.