No capítulo anterior demonstramos vários critérios de primalidade, Neste capítulo faremos várias considerações quanto ao valor prático deste critério, sendo nosso objetivo dar uma idéia geral do funcionamento dos programas que encontraram os maiores números primos conhecidos. Ao invés de tentarmos acompanhar as fontes da última versão do programa, optaremos inicialmente por nos colocarmos na posição de um programador ou matemático um pouco ingênuo que acaba de aprender que existe este critério e resolveu colocá-lo em prática; veremos assim programas simples que de fato implementam o teste mas nas nossas primeiras tentativas teremos um sucesso bastante relativo. Ao chegarmos ao final do capítulo, entretanto, esperamos ter discutido os principais aspectos matemáticos de uma boa implementação do teste. Veremos que uma das nossas principais preocupações será a de saber multiplicar inteiros rapidamente e os melhores algoritmos para esta tarefa estão baseados na transformada de Fourier discreta. A parte deste capítulo referente a este tema está fortemente baseada no livro de M. Clausen e U. Baum, Fast Fourier Transforms ([CB]).
Nossos programas são escritos em C e foram testados em um Pentium-Linux, com o compilador gcc. Os programas que apresentaremos são pedagógicos e ilustrativos, muito aquém do ideal principalmente em termos de velocidade. Todos os programas podem ser obtidos pela rede; os de nossa autoria estão em ftp://ftp.mat.puc-rio.br/pub/users/nicolau/mersenne/mersenne.tgz.