Algoritmos Matemáticos para calcular números primos - Algoritmo de Brillhart, Lehmer & Selfridge

Em 1927, Lehmer tornou o algoritmo de Lucas datado de 1891 mais prático, mas este foi ainda tornado mais flexivel por Brillhart, Lehmer & Selfridge em 1975: Seja N>1. Assuma-se que para cada factor primo q de N-1 existe um inteiro a = a(q)>1 tal que: 1. a^N-1 | | 1 (mód. N). 

        2. a^(N-1)/q | | 1 (mód.N).

Então N é um número primo.

Defeitos do algoritmo: mais uma vez, é necessário conhecer os factores primos de N-1, mas poucas congruências têm de satisfeitas.