A factored part of n − 1 large enough to force primality
If a prime power qe divides n − 1 and a suitable base exists, then every prime factor of n is congruent to 1 modulo qe. Accumulating enough such constraints — a factored part exceeding √n — forces n to be prime. The base and the factorisation together form a short certificate that anyone can verify with a few modular exponentiations.
Learning objectives
- State the Pocklington criterion and the size condition on the factored part.
- Construct and verify an n − 1 certificate.
- Apply the dual n + 1 test using Lucas sequences.
- Recognise the numbers of special form where these tests excel.
- Explain why the method fails for general large numbers.
Section 01The Pocklington criterion
Suppose qe divides n − 1 and there is a with
Then every prime factor of n is congruent to 1 modulo qe. Collecting such conditions for enough prime powers gives a divisor F of n − 1 such that every prime factor of n is 1 modulo F; if F > √n, then n has no prime factor below its own square root and is therefore prime.
- Factor n − 1 as far as feasible: n − 1 = F · U with F fully factored and gcd(F, U) = 1.
- Require F > √n. If the factored part is too small, the method does not apply.
- For each prime q dividing F, find a base aq satisfying both conditions above.
- Verify aqn−1 ≡ 1 (mod n) for each.
- Conclude n is prime. The certificate is the list of (q, aq) together with primality certificates for each q, applied recursively.
Each q is smaller than n, so proving its primality is a strictly smaller problem. The recursion bottoms out at small primes verifiable by trial division, giving a finite tree that constitutes the whole certificate.
Section 02The n + 1 test
The dual test uses Lucas sequences in place of powers. Where the n − 1 test works in the multiplicative group of Fn, the n + 1 test works in the norm-one subgroup of the quadratic extension, whose order is n + 1 when n is prime and the discriminant is a non-residue.
| n − 1 test | n + 1 test | |
|---|---|---|
| Group used | Fn×, order n − 1 | Norm-one subgroup of Fn², order n + 1 |
| Arithmetic | Modular exponentiation | Lucas sequences |
| Requires | Factored part of n − 1 exceeding √n | Factored part of n + 1 exceeding √n |
| Special case | Proth numbers k·2m + 1 | Mersenne and Lucas–Lehmer numbers |
When neither n − 1 nor n + 1 has a large enough factored part alone, the two can be combined: factored parts F− and F+ jointly constrain the possible prime factors, and a product exceeding roughly n1/3 can suffice with additional conditions.
Section 03Where these tests excel and where they fail
Proth numbers
For n = k·2m + 1 with k small, n − 1 is completely factored by construction. Proth's theorem gives a single-base test — the basis of much large-prime searching.
Mersenne numbers
For n = 2p − 1, the Lucas–Lehmer test is a specialised n + 1 test requiring exactly p − 2 squarings.
Factorial and primorial primes
n ± 1 is highly composite by construction, giving a large factored part for free.
General large n
Factoring n − 1 is as hard as factoring anything else of that size, so for a random large n the required factored part is unobtainable.
Cryptographic primes
Deliberately chosen so that n − 1 has a large prime factor, which is exactly the case where partial factorisation does not help.
Elliptic curve proving
ECPP removes the dependence on factoring n ± 1 by replacing the fixed group with a curve group whose order can be resampled.
ReferenceFrequently asked questions
Why does the factored part need to exceed the square root?
Because the conditions force every prime factor of n to be at least F + 1. If F exceeds √n then n cannot have two such factors, and since it has at least one, it is prime.
How is a certificate verified?
By repeating the modular exponentiations and GCD checks — a handful of operations per prime — and recursively verifying the certificates of the auxiliary primes. Verification is orders of magnitude cheaper than the original search.
What is Proth's theorem?
For n = k·2^m + 1 with k odd and k less than 2^m, n is prime if and only if there is a base a with a^((n-1)/2) congruent to −1 modulo n. It is the n − 1 test specialised to a form where the factorisation is known in advance, and it makes testing a single exponentiation.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.