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

Algoritmo de Pepin para testar a primalidade dos números de Fermat

Como os números de Fermat (Fⁿ  = 2^{2^n} +1) crescem muito rapidamente em função de n, torna-se muito laborioso testar a sua primalidade. No entanto, Pepin obteve em 1877 um algoritmo para testar a primalidade de números de Fermat.

Algoritmo de Pepin:

Seja Fⁿ  = 2^{2^n} +1, com n³2, e k³2. Então as seguintes condições são equivalentes: 

1. Fⁿ é um número primo e (k/ Fⁿ) = -1; 

2.  k^{(Fn -1)/2} -1 (mód.  Fⁿ ).

Este algoritmo é praticamente uma aplicação da fórmula de Euler para os factores de Fⁿ (Euler demonstrou que todos os factores de Fⁿ , com n³2, são da forma k x 2ⁿ⁺²+1 e através do qual descobriu que 641 divide F⁵ : F⁵ = 641 x 6 700 417) . No entanto se Fⁿ é composto, este não nos indica qualquer factor deste.