Algoritmos Matemáticos para calcular números primos - Algoritmo de Lucas

Estes algoritmos são baseados no Pequeno Teorema de Fermat (para distinguir do  denominado Grande Teorema de Fermat).Que diz que: 
Seja n um número primo então para qualquer número inteiro a,
 tem-se que : a^p  | |a (mód. p)

Algoritmo de Lucas de 1876:

Seja N>1. Assuma-se que existe um inteiro a>1 tal que:

1. a^{N-1| |}1 (mód. N),
2. a^m | |1 (mód. N), para m =1,2, ..., N - 2.

Então N é um número primo.

Defeitos do algoritmo: pode parecer perfeito, mas requer N-2 sucessivas multiplicações por a, e a busca dos resíduos do módulo N : Demasiadas operações.

Algoritmo de Lucas de 1891:

Seja N>1. Assuma-se que existe um inteiro a>1 tal que:

1. a^N-1 | |1 (mód. N).
2. a^m | |1 (mód. N) para cada m<N, tal que m seja divisor de N-1.

Então N é um número primo.

Defeitos apresentados por este algoritmo: requer o conhecimento prévio de todos os factores de N-1, embora seja fácil de aplicar quando N é da forma N= 2ⁿ + 1 ou quando N=3.2ⁿ  + 1.