Classical Primality and Factoring
N+1 Tests and the Lucas-Lehmer Test
Primality tests using the factorisation of one more than the candidate, and the Lucas-Lehmer test for Mersenne numbers.
Engineering / MathematicsClassical Primality and Factoring2 min readKV-MATH-0651
The N+1 tests are the Lucas-sequence duals of Pocklington-Lehmer, using the factorisation of one more than the candidate. The Lucas-Lehmer test for Mersenne numbers is the celebrated special case.
The dual criterion
Where the N-1 test works in the multiplicative group modulo the candidate, the N+1 test works in the quadratic extension, where the relevant group has order one more than the candidate.
Combined tests
When neither one less nor one more can be factored sufficiently, combined criteria use partial factorisations of both. These extend the practical range considerably.
| Available factorisation | Method |
|---|---|
| One less, past the square root | Pocklington-Lehmer |
| One more, past the square root | N+1 test |
| Partial of both | Combined criteria, e.g. Brillhart-Lehmer-Selfridge |
| Neither | Requires a modern general method |
Mersenne numbers
A Mersenne number is one less than a power of two. One more than it is a power of two, which is completely factored by inspection, so the N+1 machinery applies with no factoring work at all.
The Lucas-Lehmer test
For Mersenne numbers with prime exponent, the test reduces to a single recurrence: iterate a squaring map a fixed number of times and check whether the result vanishes.
The Lucas-Lehmer test
- StartBegin with the value four.
- IterateReplace by its square minus two, reduced modulo the Mersenne number.
- RepeatTwo fewer times than the exponent.
- TestThe number is prime exactly when the final value is zero.
Why Mersenne numbers are efficient
Other special forms
Fermat numbers, Proth numbers and generalised Fermat numbers all admit similar specialised tests based on the structure of one more or one less than the candidate. Each rests on the same principle: a known factorisation on one side.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 8.4. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.